Bubble Sort | Bubble Sort #2 | Insertion Sort | Selection Sort |
---|---|---|---|
for (int i = 0; i < list.Length-1; i++) { for (int j= i+1; j< list.Length; j++) {   if (list[i] > list[j])   {     list.Swap(i, j);   } }Basic bubble sort - optimized only in that we know that on the Nth pass the first N-1 values have already been placed correctly and can be skipped. In this variation, a swap free pass means nothing other than the item at position i is in the right place. |
bool swappedThisPass; for (int i = 0; i < list.Length - 1; i++) { swappedThisPass = false; for (int j = list.Length -1; j>i; j--) { if (list[j-1] > list[j]) { swappedThisPass = true; list.Swap(j-1, j); } } if (swappedThisPass == false) break; }Basic bubble sort - by swapping adjacent entries we can optimize further simply by the fact a clean pass indicates the solution has already been reached. |
for (int i = 1; i < list.Length; i++) { int j = i; while (j > 0 && list[j - 1] > list[j]) { list.Swap(j-1, j); j--; } } Basic insertion sort. Given a string like 'FEDCBA' performance is as bad as bubble sort, but real world is just as good. Improvement is we make better use of the face we know that once one comparision returns 'no swap required' nothing to the left of us does either. |
for (int i = 0; i < list.Length; i++) { int minIndex = i; for (int j = i + 1; j < list.Length; j++) { if (list[j] < list[minIndex]) minIndex = j; } list.Swap(i, minIndex); } Basic selection sort. While the number of reads is as bad as bubble sort, the number of writes is far fewer. In the example below, only the final green in a sequenece is an actual swap. |
DEADBEEFCA DEADBEEFCA AEDDBEEFCA AEDDBEEFCA AEDDBEEFCA AEDDBEEFCA AEDDBEEFCA AEDDBEEFCA AEDDBEEFCA AEDDBEEFCA ADEDBEEFCA ADEDBEEFCA ABEDDEEFCA ABEDDEEFCA ABEDDEEFCA ABEDDEEFCA ABEDDEEFCA AAEDDEEFCB AADEDEEFCB AADEDEEFCB AADEDEEFCB AADEDEEFCB AADEDEEFCB AACEDEEFDB AABEDEEFDC AABDEEEFDC AABDEEEFDC AABDEEEFDC AABDEEEFDC AABDEEEFDC AABCEEEFDD AABCEEEFDD AABCEEEFDD AABCEEEFDD AABCDEEFED AABCDEEFED AABCDEEFED AABCDEEFED AABCDEEFED AABCDDEFEE AABCDDEFEE AABCDDEFEE AABCDDEFEE AABCDDEEFE AABCDDEEFE AABCDDEEEF: 45 steps |
DEADBEEFCA DEADBEEFAC DEADBEEAFC DEADBEAEFC DEADBAEEFC DEADABEEFC DEAADBEEFC DEAADBEEFC DAEADBEEFC ADEADBEEFC ADEADBEECF ADEADBECEF ADEADBCEEF ADEADBCEEF ADEABDCEEF ADEABDCEEF ADAEBDCEEF AADEBDCEEF AADEBDCEEF AADEBDCEEF AADEBDCEEF AADEBCDEEF AADEBCDEEF AADBECDEEF AABDECDEEF AABDECDEEF AABDECDEEF AABDECDEEF AABDECDEEF AABDCEDEEF AABCDEDEEF AABCDEDEEF AABCDEDEEF AABCDEDEEF AABCDDEEEF AABCDDEEEF AABCDDEEEF AABCDDEEEF AABCDDEEEF AABCDDEEEF: 39 steps |
DEADBEEFCA DEADBEEFCA DAEDBEEFCA ADEDBEEFCA ADDEBEEFCA ADDEBEEFCA ADDBEEEFCA ADBDEEEFCA ABDDEEEFCA ABDDEEEFCA ABDDEEEFCA ABDDEEEFCA ABDDEEEFCA ABDDEEECFA ABDDEECEFA ABDDECEEFA ABDDCEEEFA ABDCDEEEFA ABCDDEEEFA ABCDDEEEFA ABCDDEEEAF ABCDDEEAEF ABCDDEAEEF ABCDDAEEEF ABCDADEEEF ABCADDEEEF ABACDDEEEF AABCDDEEEF AABCDDEEEF: 28 steps |
DDEADBEEFCA DDEADBEEFCA DEAADBEEFCA DEAADBEEFCA DEAADBEEFCA DEAADBEEFCA DEAADBEEFCA DEAADBEEFCA DEAADBEEFCA AEEDDBEEFCA AEDDBEEFCA AEDDBEEFCA AEDDBBEEFCA AEDDBBEEFCA AEDDBBEEFCA AEDDBBEEFCA AEDDBBEEFCA AADDDBEEFCE AADDDBEEFCE AADDBBEEFCE AADDBBEEFCE AADDBBEEFCE AADDBBEEFCE AADDBBEEFCE AABDDDEEFCE AABDDDEEFCE AABDDDEEFCE AABDDDEEFCE AABDDDEEFCE AABDDEEFCCE AABCDDEEFDE AABCDDEEFDE AABCDDEEFDE AABCDDEEFDE AABCDDEEFDE AABCDEEEFDE AABCDEEEFDE AABCDEEEFDE AABCDEEFDDE AABCDDEEFEE AABCDDEEFEE AABCDDEEFEE AABCDDEFFEE AABCDDEFEE AABCDDEEFFE : 45 steps (but far less writes) |