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

    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

  
  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;
  }

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&