SORTING BY EXCHANGE

​

By

​

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

_{PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY}

• 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”.

​

​

Dept of CSE

2025 - 26

SORTING BY EXCHANGE

PVPSIT (Autonomous)

Problem Solving Techniques

• 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.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

• 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”.

​

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

• 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.

​

​

​

​

​

​

​

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

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

Dept of CSE

2025 - 26

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

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

• 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.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques