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 3Done.Insertion sort: Each pass places the next element in the correct spotEach 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 sortedDone.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 fine2 and 9 are fine9 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 pass1 and 2 are fine2 and 5 are fine5 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 fine2 and 0 swap   [1 , 0,  2, 3,     5, 9]2 and 3 are fineNow 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 fineNow the last four elements are in the correct place! Don't loop that far anymore [0 , 1,      2, 3, 5, 9]5th pass0 and 1 are fineNow the last five elements are in the correct place! Don't loop that far anymore [0 ,      1, 2, 3, 5, 9]We are done!