Sorting Algorithms You Probably Want to Know

Bubble Sort


The basic idea behind a bubble sort is to step through the array comparing every two elements and swapping them if they are in the wrong order. For example if the array is [2][1][3] the first step would compare ([2][1])[3] and notice on the first comparison that 2 and 1 should be swapped so now you have [1][2][3] but it will still check 2 and 3 to make sure they are correct. Bubble sort has an average of O(n^2) complexity. Given it tries all cases no matter what the worst case sceneiro is also the same, making it a poor choice for larger "n" number of elements.

As Shown Here:


Psudo Code:

FOR i in LENGTH - 1

FOR j in LENGTH - i - 1

IF arrayElement[j] > arrayElement[j + 1]

SWAP arrayElement[j] and arrayElement[j + 1]

ENDIF

ENDFOR

ENDFOR

Selection Sort


Selection sort is one of the best sorts to do in a list that is of reasonable size. While potentially not as efficient as the simmular insertion sort and larger sorting algroithems. Selection benifits from its simplicity and speed in small to medium size lists. By medium size I mean things around the thousands. As compared to Merge or Quick sorts which requires allocating space to store all the temporary lists, most smaller lists can be sorted in the ammount of time a more complex sorting takes to just initialize (this is fractions of seconds).
Basicly selection sort finds the smallest value (or largest) on the first pass and places it at the begining, then finds the second smallest storing it at place two... ect this grows until there is no unsorted vlues left. Very simple and natural when you think about it.

Psudo Code:

FOR i = 1 in LENGTH

SET temp TO arrayElement[i]

FOR j = i - 1 in LENGTH > 0 AND arrayElement[j] > temp COUNTS BACKWARDS

SET arrayElement[j + 1] TO arrayElement[j]

ENDFOR

SET arrayElement[j + 1] TO temp

ENDFOR

Insertion Sort


Insertion is a slightly smarter version of Selection sort. Instead of finding the smallest value in the list and placing it at the start, insertion takes what ever value it has and places it in the "sorted" side of the list. This means it does not have to check each one for the minimum it just checks aginst whats already sorted. Like a selection sort, insertion is best for smaller lists, but still likely faster and computationally less expensive to preform on smaller lists than quick, merge or heap sort. In its worst case scenerio like if the elements where in the oppsite order desired it has the same complexity as selection (n(n-1)/2) but in most cases it will not need to search the whole list so its almost always better.

As Shown Here:


Psudo Code:

FOR i = 1 LESS THAN OR EQUAL TO LENGTH - 1

SET j TO i

WHILE j > 0 AND arrayElement[j] < arrayElement[j - 1]

SWAP arrayElement[j] and arrayElement[j - 1]

SET j TO j - 1

ENDWHILE

ENDFOR

Merge Sort


Ahh good ol' merge sort! The basic idea here is to recursively call the function each time breaking it up in half. Finally when you are left with only one element then as the returns actually start coming back the list is put back in order. Merge sort is great for its average complexity of O(n * log(n)) and being the same for its worst case. But merge comes at a cost because it needs to make an entire copy of the original list to work meaning there is a memory concern for larger arrays and a bit of overhead to setting it up, which is why most merge sort implementations have something like insertion sort built in for smaller arrays.

I recommend watching this if you want to see merge sort in action, or just something weird.

(Honestly I didn't even watch it all, but I was onboard within the first 5 seconds.)



Psudo Code:


So there are two basic parts of our mergesort, the recursive splitting function and the merge function.


void
MERGESORT
PARAMS array, low, high

//Base case for the recursive call

//Recursively calls itself passing in the first half of the split

//Recursively calls itself passing in the second half of the split

//Merge using the given params

ENDMERGESORT


Next the actual merge

void
MERGE
PARAMS array, low, mid, high

//Create a tempoary array to be built

//We will need 2 variables to store the lowest index for the first half and the lowest for the second half

//We will also need a blank counter variable (let's call it k)

//Loop while the first half and second half is less than their prespective highs

//In the loop check if the Nth element of the first half

//is less than or equal to the Nth element of the second half

//If so set the temp array at it's index to the the first half at it's index

//and iterate both the first halves index and the temp arrays index ('k')

//If not set the temp array at it's index to the second half at it's index

//and iterate both the second halves index and the temp arrays index ('k')

//End Loop

//Loop over the first half assigning the rest of the values to the temp array

//Loop over the second half assiging the rest of it's values to the temp array

//Subtract 1 from k as it's final iteration will cause it to bump up one too many

//Loop backwards over k until 0

//assigning our real array at the index of the 'low' plus our current 'k'

ENDMERGE


This will be the actual function called from other functions, lets call it 'MERGESORT'

void
MERGESORT
PARAMS array, low, high

IF
low IS LESS THAN high

SET mid TO low + high / 2

mergeSort(array, low, mid)

mergeSort(array, mid + 1, high)

merge(array, low, mid, high)

ENDIF

ENDMERGESORT


Here we have the comparison and building function called from MERGESORT, lets call it MERGE

void
MERGE
PARAMS array, low, mid, high

INITIALIZE tempArray

INITIALIZE i SET TO low

INITIALIZE j SET TO mid + 1

INITIALIZE k SET TO 0


WHILE
i <= mid AND j <= high

IF
array[i] <= array[j]

SET tempArray[k++] TO array[i++]

ENDIF

ELSE

SET tempArray[k++] TO array[j++]

ENDELSE

ENDWHILE

WHILE
i <= mid

SET tempArray[k++] TO array[i++]

ENDWHILE

WHILE
j <= mid

SET tempArray[k++] TO array[j++]

ENDWHILE

SET k TO k -1

WHILE
k > 0

SET array[low + k] TO tempArray[k]

SET k TO k - 1

ENDWHILE

ENDMERGE


Boom there we have it, to call it just do somthing simmular to a binary search

mergeSort(array, 0, length);

Heap Sort


Comming Soon...

Quick Sort


Comming Soon...