25 June 2013

sorting

by mo

sorting

A sorting algorithm is an algorithm that puts elements of a list in a certain order. - Wikipedia

bubble sort

  • pass through the data from one end to the other, swap adjacent elements whenever the first is greater than the last.
  • O(n^2) - very slow for large data sets
  for (int i = 0; i < data.Length; i++)
    for (int j = 0; j < data.Length - 1; j++)
      if (data[j] > data[j+1])
      {
        tmp = data[j]
        data[j] = data[j+1]
        data[j + 1] = tmp
      }

insertion sort

for (int i = 0; i < data.Length; i++) {
  int j = i;
  while (j  > 0 && data[i] < data[j-1])
    j--;
  int tmp = data[i];
  for (int k = i; k > j; k--)
  {
    data[k] = data[k -1];
  }
  data[j] = tmp;
}
  • seeks to sort a list one element at a time.
  • one of the principal advantages of the insertion sort is that it works very efficiently for lists that are nearly sorted initially.
  • It can also work on data sets that are constantly being added to.
  • e.g. if one wanted to maintain a sorted list of the highest scores achieved in a game, an insertion sort would work well, since new elements would be added to the data as the game was played.

library sort

merge sort

  • works recursively. First it divides a data set in half, and sorts each half separately.
  • next the first elements from each of the two lists are compared.
  • the lesser element is then removed from its list and added to the final result list.
  • optimization for nearly sorted lists.
    • if the highest element in one list is less than the lowest element in the other half, the the merge steps is unnecessary.

heap sort

  Heap h = new Heap();
  for (int i = 0; i < data.Length; i++)
    h.Add(data[i]);
  int[] result = new int[data.length];
  for (int i = 0; i < data.Length; i++)
    data[i] = h.RemoveLowest();
  • we create a heap data structure.
  • head datastructure: stored in a tree such that all the smallest (or largest) elements is always the root node.
  • all data is inserted into a heap, then the root element is removed and stored back into the list.

quick sort

  • efficient sorting algorithm.
  • divide the data into two groups of “high” values and “low” values.
  • then recursively process the two halves. then reassemble the now sorted list.
  Array quickSort(Array data)
  {
    if (data.Length <= 1)
      return;
    middle = Array[data.Length / 2];
    Array left = new Array();
    Array right = new Array();
    for (int i=0; i < data.Length; i++)
    {
      if(i != data.Length / 2)
      {
        if (data[i] <= middle)
          left.Add(data[i]);
        else
          right.Add(data[i]);
      }
    }
    return combine(quickSort(left), middle, quickSort(right));
  }
algorithms 💎