Topic 7 – Sorting Techniques
Introduction
Once you have mastered searching sorted data for values – you are surely asking yourself, how do we sort the data? There are many techniques for sorting and the choice of technique is surprisingly important. Also the structure used to represent the data is also quite important. The reason is performance is dependent upon how we use the data is pretty basic. If we have a list that we are only going to add items at the beginning or end (already sorted) then sort efficiency is not terribly important after the first sort. If we need to add items all the time and always have the list in sorted order – the choices become important.
Video – Introduction to Sorting
Link – https://www.youtube.com/watch?v=Bt0NPCPNAEo
Abstraction
If our data structure used to represent our list follows the List interface, implementing Insert and Delete – which always insert correctly, we are assured that growing or shrinking our list will always work. In this respect we don’t care how the list is implemented. However, if we care about performance, then we do care about the implementation of the list. This was just a good chance to review the concept of abstraction – http://en.wikipedia.org/wiki/Abstraction_%28computer_science%29
Stability of Sorting Algorithms
When sorting a list there is always the possibility of items that are equal (or at least equal on the value being used to sort the list). Some sorting algorithms are Stable in that if two items compare as equal then their relative order will be preserved. An Unstable algorithm does not preserve this original order. So – if the order of possible equal values is important be sure to select a stable algorithm. An example of where you might need this is sorting a deck of cards by value, while retaining the order of the suits.
Useful Sorting Algorithms
Complete details of every sorting algorithm (that I know at least) is available at http://en.wikipedia.org/wiki/Sorting_algorithm . You need to be familiar with and capable of implementing the following sorts; Quicksort (my favorite), MergeSort, and BubbleSort (easiest). These have excellent documentation and representation from the wikipedia article. Please be prepared to implement any of these, recognize them, and also know advantages (computational complexity, stability) and disadvantages.
Visualization of Sorting Algorithms
This little video will take you through 15 different sorting algorithms and show the visualization of the actual sorting;
Sort Algorithms and Psuedo Code
One of the greatest challenges of implementing sort algorithms in JavaScript is the translation of the pseudo-code. Here is some help using the conventions that we use in this class for the standard functions in lists.
node – represents a single node in a linked list
content – represents the content of the linked list, typically a string
Psuedo-Code | JavaScript |
from https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists
for each x with index i in m do if i < (length of m)/2 then add x to left else add x to right |
_list – is passed linked list
left is a linked list right is a linked list
var length = _list.length var i = 0; var node = _list.head; while (node != null) { if (i < length / 2) { left.add(node.content); } else { right.add(node.content); } i++; node = node.next; } |
from https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists
function merge(left, right) var result := empty list while left is not empty and right is not empty do if first(left) ≤ first(right) then append first(left) to result left := rest(left) else append first(right) to result right := rest(right) // Either left or right may have elements left; consume them. // (Only one of the following loops will actually be entered.) while left is not empty do append first(left) to result left := rest(left) while right is not empty do append first(right) to result right := rest(right) return result |
function merge(left, right) { var result = new DoublyLinkedList(); while ((left.head != null) && (right.head != null)) { if (left.head.content <= right.head.content) { result.add(left.pop().content); } else { result.add(right.pop().content); } } while (left.head != null) { result.add(left.pop().content); } while (right.head != null) { result.add(right.pop().content); } return result; } |
Video – Insertion Sort
Link – https://www.youtube.com/watch?v=1DYIH9SQdGM&