Exchanging Sort Algorithms

1. Buble Sort

   In buble sort iterate over the list and change the first with the second if first is greater then second exchange them with third if second greater and move to end like this changing the elements with the next if greater.After you reach end start over until you make no change in a pass.

   Buble Sort first pass

   8 4 3 1 7 6 2

   4 8 3 1 7 6 2

   4 3 8 1 7 6 2

   4 3 1 8 7 6 2

   4 3 1 7 8 6 2

   4 3 1 7 6 8 2

   4 3 1 7 6 2 8

   As we can see the large number at the begining(8) moved to end very quickly but the small number(2) at the end moved only 1 place in 1 pass

   Small number at the end are turtles

   Large number at the begining rabbits

2. Coctail Sort is also known as bidirectional buble sort coctail shaker sort or skaker sort it is a variation of buble sort which sorts from both directions in each pass which eliminates turtle problem because turtles from one side are rabits of the other side.

3. Comb sort is another buble sort variation, it improves buble sort by introducing a gap between swapped elements in buble sort this gap is 1 .In comb sort this gap help turtles move faster and after each pass gap is decremented undil gap becomes 1 and algorithm becomes a buble sort algorithm.The gap is calculated by dividing the lenght of the list by shrink factor(generally 1.3 ,calculated empirically)

Gnome sort is a very easy exchanging algorithm it is also called stupid sort it does not use nested loops it swaps the elements until the left element is smaller than the right.

Let s try it on our sample list

8 4 3 1 7 6 2

4 8 3 1 7 6 2

4 3 8 1 7 6 2

3 4 8 1 7 6 2

3 4 1 8 7 6 2

3 1 4 8 7 6 2

1 3 4 8 7 6 2

1 3 4 7 8 6 2

1 3 4 7 6 8 2

1 3 4 6 7 8 2

1 3 4 6 7 2 8

1 3 4 6 2 7 8

1 3 4 2 6 7 8

1 3 2 4 6 7 8

1 2 3 4 6 7 8