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
