1 of 10

PROBLEM SOLVING TECHNIQUES

By

​

B. Vinay Kumar

Assistant Professor

Dept. of CSE

PVPSIT, Kanuru.

​

​

PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY

2 of 10

  • Problem: Given a randomly ordered set of n integers, sort them into non-descending order using the Exchange method.
  • Algorithm development: All most all sorting methods rely on exchanging data to achieve the desired ordering.
  • Consider the unsorted array:

​

​

​

​

  • Exchange method key point is “Increased the order in the data”.

​

​

B. Vinay Kumar

Wednesday, January 18, 2023

SORTING BY EXCHANGE

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 10

  • We notice that the first two elements are “out of order”. In the sense 30 will need to appear later than 12.
  • This leads to the configuration below:

​

​

​

​

  • Now continue with the second and third elements.

B. Vinay Kumar

Wednesday, January 18, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 10

  • The order in the array can be increased using the following steps:

​

​

​

  • After applying this idea to all adjacent pairs in our current data set we get the configuration below:

​

​

  • It guarantees that the highest element 41 will be forced into the last position in the array.
  • In effect the last element is at this stage “sorted”.

​

B. Vinay Kumar

Wednesday, January 18, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 10

  • The mechanism for comparing and exchanging adjacent pairs the overall structure of our algorithm becomes:

​

​

​

​

​

  • It only operates on the “unsorted” part of the array.

​

​

​

​

​

​

​

B. Vinay Kumar

Wednesday, January 18, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 10

B. Vinay Kumar

Wednesday, January 18, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 10

B. Vinay Kumar

Wednesday, January 18, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 10

begin

sorted:=false;

i:=0;

while (i<n) and (not sorted) do

begin

sorted:=true;

i:=i+1

for j:=1 to n-i do

if a[j]>a[j+1] then

begin

t:=a[j];

a[j]:= a[j+1];

a[j+1]:=t;

sorted:= false

end

end

end

B. Vinay Kumar

Wednesday, January 18, 2023

Pseudo-code

begin

for i:=1 to n-1 do

for j:=1 to n-i do

if a[j] > a[j+1] then

begin

t := a[j];

a[j] := a[j+1]; a[j+1] := t

end

end

OR

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 10

B. Vinay Kumar

Wednesday, January 18, 2023

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 10

  • Applications:
  • Only for sorting data in which a small percentage of elements are out of order.

​

  • Supplementary problem (5.3.2)
  • Implement a version of the bubblesort that builds up the sorted array from smallest to largest rather than as in the present algorithm.

B. Vinay Kumar

Wednesday, January 18, 2023

PVPSIT (Autonomous)

Problem Solving Techniques