announcements‎ > ‎

2016-01-05 Sorts.java

posted Jan 5, 2016, 6:55 AM by Samuel Konstantinovich   [ updated Jan 5, 2016, 6:55 AM ]
Lets say we have the array:
[1 , 2,  9, 5, 0, 3]

Selection sort: Each pass finds the correct element for the next slot.
Each line represents a completed outer loop:
[1 , 2,  9, 5, 0, 3]  starting array
[0 , 2,  9, 5, 1, 3]  swapped 0 and 1
[0 , 1,  9, 5, 2, 3]  swapped 1 and 2
[0 , 1,  2, 5, 9, 3] swapped 2 and 9
[0 , 1,  2, 3, 9, 5] swapped 5 and 3
[0 , 1,  2, 3, 5, 9] swapped 5 and 3
Done.


Insertion sort: Each pass places the next element in the correct spot
Each line represents a completed outer loop:
[1 , 2,  9, 5, 0, 3]  starting array assume 1 is sorted
[1 , 2,  9, 5, 0, 3]  2 is in the correct place compared to 1. Now 1,2 are sorted
[1 , 2,  9, 5, 0, 3]   9 is in the correct place compared to 1 and 2, now 1,2,9 are sorted.
[1 , 2,  5, 9, 0, 3]   Shift 5 into the correct place, now 1 2 5 9 are sorted.
[0, 1 , 2,  5, 9, 3]   Shift 0 into the correct place, now 0 1 2 5 9 are sorted
[0, 1 , 2, 3, 5, 9]   Shift 3 into the correct place, now 0 1 2 5 9 are sorted
Done.

Bubble Sort: loop from start to end, pushing up the values that need to "bubble" to the top.
Since bubble sort needs to be explained a bit more here is step by step:

Each "pass" is the outer loop. This is indicated in blue to be clear.
Each line of each pass is the inner loop.

Start with: [1 , 2,  9, 5, 0, 3]

Outer loop 1st pass:  
1 and 2 are fine
2 and 9 are fine
9 and 5 need to be swapped [1 , 2,  5, 9, 0, 3]
now 9 and 0 need to be swapped [1 , 2,  5, 0, 9, 3]
now 9 and 3 need to be swapped [1 , 2,  5, 0, 3, 9]

Now the last element is in the correct place! Don't loop that far anymore
 [1 , 2,  5, 0, 3,        9]

2nd pass
1 and 2 are fine
2 and 5 are fine
5 and 0 need to be swapped  [1 , 2,  0, 5, 3,       9]
5 and 3 need to be swapped  [1 , 2,  0, 3, 5,       9]
Now the last two elements are in the correct place! Don't loop that far anymore
  [1 , 2,  0, 3,     5, 9]

3rd pass  
1 and 2 are fine
2 and 0 swap   [1 , 0,  2, 3,     5, 9]
2 and 3 are fine
Now the last three elements are in the correct place! Don't loop that far anymore
 [1 , 0,  2,    3, 5, 9]


4th pass:
1 and 0 need to swap   [0 , 1,  2,    3, 5, 9]
1 and 2 are fine
Now the last four elements are in the correct place! Don't loop that far anymore
 [0 , 1,      2, 3, 5, 9]


5th pass
0 and 1 are fine
Now the last five elements are in the correct place! Don't loop that far anymore
 [0 ,      1, 2, 3, 5, 9]

We are done!

Comments