Sorting

View Code
Sorting
a means to order an array
Ascending
increasing in value, e.g. 1 2 3
Descending
decreasing in value, e.g. 3 2 1
Merging
the process of creating one sorted array from two sorted arrays

Bubble Sort

The bubble sort is named for the fact that it bubbles up and down values in the array. First the first two elements are compared, if the second is larger than the first they are swapped. Now the second and third elements are compared. If the third exceeds the second they are swapped. Etc. When the whole array is processed we check to see if we made at least one swap. If we did the array is not sorted and we repeat the process until there are no swaps. 

*1 *9 11 13 4 13 10  Swap=no
First we compare the first element with the goal. (I am using a * to be a place holders). Since 1<9 we move on. 
1 *9 *11 13 4 13 10  Swap=no
OK 
1 9 *11 *13 4 13 10  Swap=no
OK 
1 9 11 *13 *4 13 10  Swap=no
13>4 so we swap them and mark that we did. 
1 9 11 4 *13 *13 10  Swap=yes
OK 
1 9 11 4 13 *10 *13  Swap=yes
Swap the 13 and 10. 
1 9 11 4 13 10 13  Swap=yes
Now at the end we check to see if their was a swap. Since there was we start again. 
*1 *9 11 4 13 10 13  Swap=no
OK. Since their are a lot of comparisons, the following comments are after the whole array is compared. 
1 9 4 11 10 13 13  Swap=yes
There was a swap, so we repeat. 
1 4 9 10 11 13 13  Swap=yes
There was a swap, so we repeat. 
1 4 9 10 11 13 13  Swap=no
There were no swaps so are sorting is complete. As you can see the algorithm of the bubble sort is simple but the actual efficiency is not.

Selection Sort

With this sort the appropriate elements of the array are selected and placed in their proper positions. As a result this sort is sometimes quicker than the bubble sort. First mark the first index of the array. From that point to the end find the smallest element and swap it with it. Now advance the mark. Find the smallest element from the mark to the end and swap. Repeat till the end. 

*1 9 11 13 4 13 10
1 is the minimum, so we advance. 
1 *9 11 13 4 13 10
4 is the minimum, so we swap that and advance. 
1 4 *11 13 9 13 10
Etc. 
1 4 9 *13 11 13 10
Etc. 
1 4 9 10 *11 13 13
Etc. 
1 4 9 10 11 *13 13
Etc. 
1 4 9 10 11 13 *13
That is it.

Insertion Sort

This sort is the type people often use to order cards. First the smallest element is found and inserted to the correct place. When it is inserted though, all of the other elements are shifted over by one. It begins by marking the first element. Find the smallest element from that to the end. Check to see if the smallest element is that spot. If so save it, copy all the others up by our marked spot to the smallest spot, and then copy the value. Our spot is moved up by one and we reapeat till the end of the array. 

*1 9 11 13 4 13 10
1 is the minimum, so we advance. 
1 *9 11 13 4 13 10 Min = 4
4 is the minimum and not in the spot, so it is saved. 
1 *9 9 11 13 13 10 Min=4
Copy the rest over 
1 *4 9 11 13 13 10 Min=4
Copy the the minimum to the spot. 
1 4 *9 11 13 13 10
Advance the mark and reapeat. 
1 4 *9 11 13 13 10 Min=9
Etc. 
1 4 9 *10 11 13 13 Min=10
Etc. 
1 4 9 10 *11 13 13 Min=11
Etc. 
1 4 9 10 11 *13 13 Min=13
Etc. 
1 4 9 10 11 13 *13 Min=13
Finished.

Merging

This is not a true sort but a common concept that is used in a sort. If there are two sorted array why not "merge" them together to be one big sorted array. The process goes by keeping two spots on each array. Compare the two elements, append the smaller one to the new array, and advance that spot. Reapeat this util the end of one array is reached and then copy the rest of the other array to the new one. 

*1 9 11
*4 10 13 13
 New =
Mark the first element of each array. 1<4 so copt that to the new array and advance. 
1 *9 11
*4 10 13 13
 New = 1
4<9 copy 4, advance spot. 
1 *9 11
4 *10 13 13
 New = 1 4
Etc. 
1 9 *11
4 *10 13 13
 New = 1 4 9
Etc. 
1 9 *11
4 10 *13 13
 New = 1 4 9 10
Etc. 
1 9 11 *
4 10 *13 13
 New = 1 4 9 10 11
Since we finished the first array, the rest of the second array can be appended since it is already sorted. 
1 9 11
4 10 13 13
 New = 1 4 9 10 13 13
Finished.

Merge Sort

As you may guess the Merge Sort uses merging. It works by spliting the array in half by making two recursive calls, for the front and back end. Then it splits again by the same process, etc. When the initial array is split to individual one element arrays we come back by merging them. Thus every adjacent two "one element arrays" are merged. Then those merged (and sorted) "two element" arrays are merged, etc. It's so fast. 

  /          \
1 9 11   13 4 13 10
First split the array in half. 
    /           \
 /    \      /      \
1 9   11   13 4   13 10
Repeat. 
     /              \
  /     \       /        \
/   \   11    /   \    /   \
1   9        13   4   13   10
Repeat. 
    /           \
 /    \      /      \
1 9   11   4 13   10 13
Now merge the one element array pairs. 
  /          \
1 9 11   4 10 13 13
Now merge the two element array pairs. 
1 4 9 10 11 13 13
Now merge the three (and final) element array pairs.

Try figuring out these sort by yourself before looking at the code. They are listed in degrees of difficulty, bubble being the easiest and merge the most difficult.

Prev -- Back to Portal -- Next