I have been using table.sort in many of my projects and I must say it’s quite good however for the people who would like to micro-optimise this module is perfect for you as it seperates different sorting algorithms. This goes in depth of each sorting algorithm.
Bubble sort and Insertion Sort
Bubble sort…
- looks at the first two items in the list.
- If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them.
- Move on to the next pair of items (the 2nd and 3rd entries) and repeat step 2
- Repeat steps 1-4 until there are no swaps in a pass.
Example:
66, 21, 38, 15, 89, 49 Compare 66 and 21 - swap them
21, 66, 38, 15, 89, 49 Compare 66 and 38 - swap them
21, 38, 66, 15, 89, 49 Compare 66 and 15 - swap them
21, 38, 15, 66, 89, 49 Compare 66 and 89 - no swap
21, 38, 15, 66, 49, 89 End of first pass
After the 2nd pass the order of the numbers will be 21,15, 38, 49, 66, 89
After the 3rd pass the order of the numbers will be 15, 21, 38, 49, 66, 89
There are no swaps in the 4th pass so the list has been sorted 15, 21, 38, 49, 66, 89
The bubble sort is considered to be one of the simplest sorting algorithms as it only ever focuses on two items rather than the whole list of items. In this algorithm I have combined the Insertion Sort into the Bubble Sort as they both compare two values.
Pros
- It’s an efficient way to check if a list is already in order. For a list of n items you only have to do one pass of n - 1 comparisons to check if the list is ordered or not.
- Doesn’t use very much memory as all the sorting is done using the original list.
Cons
- It’s an inefficient way to sort a list - for a list of n items, the worst case scenario would involve you doing n(n - 1) / 2 comparisons.
- Due to being inefficient, the bubble sort algorithm does not cope well with a very large list of items.
Merge sort
A merge sort…
- Splits the list in half
- keep repeating step 1 on each sub-list until all the lists only contain one item.
- Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the right order
Example:
- Split the original list of 8 items into two lists, the second list should start at the (8 + 1) / 2 = 4.5 = 5th term.
- Carry on splitting the sub-lists until each list only has one item in it.
- Merge and order the sub-lists back together.
- Keep merging until you only have one list
This merge writes these letters in alphabetical order in our case the algorithm will organise strings in alphabetical order based on the first letter of the string and organise them in an array.
You’ll often be unable to split or merge lists evenly. For exampe, sometimes you’ll have to merge a list containing two items with a list containing one item to make a list of three items.
Pros
- It has a very consistent running time regardless of how ordered the items in the original array are.
Cons
- It’s slower than other algorithms for small lists.
- Even if the list is already sorted it still goes through the whole splitting and merging process if you call it by accident
- It uses more memory than the other sorting algorithms in order to create the seperating lists.
Thanks for reading if you have any feedback or suggestions don’t hesitate to reply! 