Sorting Algorithms

Selection Sort

  1. Repeat steps 2 and 3 as index k goes from 0 to SIZE-2.
  2. Find the smallest array value in the index range k to SIZE – 1.  Call the index where the smallest value is found smallest.
  3. Swap the old value at position k with the value at smallest.

 

Big O (n2)

Selection Sort (opposite direction)

  1. Repeat steps 2 and 3 as index k goes from SIZE-1 to 1.
  2. Find the largest array value in the index range 0 to k.  Call the index where the largest value is found largest.
  3. Swap the old value at position k with the value at largest.

 

Big O (n2)

Bubble Sort or Sinking Sort

  1. Repeat steps 2-5 as index i goes from 0 to SIZE – 1 or until you find that the array is sorted.
  2. Assume the array is sorted. 
  3. Repeat steps 4-5 as index k goes from 0 to SIZE – 1 –  i.
  4. On each pass compare element at index k and element k + 1.
  5. If the pair is in increasing order (or the values are identical) leave the values as they are. 

Otherwise the pair is in decreasing order,  so swap them.  Now you know that the array was not sorted.

 

Best Case = Big O (n)

Worst Case = Big O (n2)

Average Case = Big O (n2)

 

Insertion Sort

Partition the array in two parts sorted and unsorted. 

 

  1. Start with the element at index 0 in the sorted portion and the rest of the array in the unsorted portion. Set DividerIndex to 1.
  2. Repeat steps 3-7 as DividerIndex goes from 1 to SIZE-1.
  3. Copy the value at the divider index in to another variable (DividerValue).
  4. Search through the sorted portion until the DividerValue is greater than a given element.
  5. Move the rest of the element in the sorted region to the right one position to make room for the DividerValue. (There may not be any to move.)
  6. Place DividerValue in the position left open.
  7. Increment the DividerIndex.

 

Worst Case = Big O (n2)

Average Case = Big O (n2)

 

Quick Sort

1.      Pick an item from the list and call it the pivot.

2.      Move all of the elements that are smaller than the pivot into a left-list and all of the items that are greater than the pivot into right-list.

3.      Recursively perform steps 1 & 2 on the left-list and right-list.

a.       When the  list contains only one item it is sorted and no further calls should be made to QuickSort.

4.      The sorted list including the left-list,  pivot item & the right-list should be copied back into the list. (This is the answer…aka. sorted list.)