Sorting Algorithms

• Sorting

  The process of rearranging (or organising) a sequence of objects in some logical order
• Examples of sorting orders

  • Ascending order (from lowest to highest)
  • Descending order (from highest to lowest)
  • Alphabetical order in ascending order (from 'a' to 'z')
  • Alphabetical order in descending order (from 'z' to 'a')
• Sort key


  The part of a data item that we consider when sorting a data collection
• Bubble sort


  • Simple but inefficient algorithm
  • The largest numbers "bubble" up to the top
• Bubble sort algorithm

  1. Compare list[index] and list[index + 1]

  2. If list[index] is greater than list[index + 1], then swap them

  3. Repeat for n-1 iterations
• Bubble sort executes in O(n^2) time
• Selection sort

  • Find the smallest item in the array
  • Exchange this smallest item with the first entry (itself if the first entry is already the smallest) in the array
  • Find the next smallest item in the array
  • Exchange it with the second entry in the array
  • Repeat these actions (find smallest item and exchange it) until the entire array is sorted
• Selection sort algorithm


  1. Define selectionSort function

  2. Define swap and minLocation functions

  
• Insertion sort

  • Try to improve (that is, reduce) the number of key comparisons
  • Consider the elements one at a time
  • Insert each element in its proper place among those already considered (keeping them sorted)
  • The element being considered is inserted merely by moving larger elements one position to the right, then inserting the element into the vacated position
• Insertion sort algorithm (array-based lists)


  Define insertionSort function
• Insertion sort (linked list-based lists)

  • Traverse list in only one direction
  • Find location of node to be inserted using pointers firstOutOfOrder and lastInOrder
• Finding location of node to be inserted (linked list-based)

  1. Compare firstOutOfOrder info with first node info

  2. If firstOutOfOrder info smaller, move it before first node

  3. Otherwise, search list starting at second node to find location where to move firstOutOfOrder

  4. Use two pointers current and trailCurrent to search list
• Selection sort and insertion sort have average-case behaviour of O(n^2) for a list of length n

  
• Shellsort

  • Reduces number of item movements in insertion sort by modifying it
  • The elements of the list are viewed as sublists at a particular distance
  • Each sublist is sorted, so that elements that are far apart move closer to their final position
• Shellsort algorithm

  Define shellSort function
• Increment sequence

  Determines how far apart elements to be sorted are
• Worse case performance of Shellsort is O(n^2), base case is O(n log n), average case depends on increment sequence
• Quicksort


  • A divide-and-conquer algorithm
  • Partition the array into two (possibly unequal) halves using a pivot element
• Increment sequence


  Also known as interval sequence or gap sequence
• In the example, the sequence 1, 4, 7 is the increment sequence
• How to Choose Increment Sequence?

  1. Typically, increment sequences are chosen to decrease roughly geometrically so that the number of increments is logarithmic in the size of the list

  2. Shell's original sequence: n/2, n/4, …, 1 (repeatedly divide by 2)

  3. Knuth's increments: 1, 4, 13, …, (3k – 1)/2

  4. Certain increment sequences must be avoided, e.g. 1, 2, 4, 8, 16, 32, 64, 128, 256... (bad performance)
• Shellsort

  • Worse case performance: O(n2)
  • Base case performance: O(n log n)
  • Average case performance: depends on the increment sequence
• Quicksort

  Array-based lists
• Quicksort: Array-based Lists

  1. Partition the array into two (possibly unequal) halves using a pivot element

  2. Left half is all less than pivot

  3. Right half is all greater than pivot

  4. Quicksort the left sublist

  5. Quicksort the right sublist

  6. Merge the two sorted sublists
• Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays
• Quick Sort Pivot Algorithm

  1. Choose the highest index value as pivot

  2. Take two variables to point low (lo) and high (hi) of the list excluding pivot

  3. lo points to the low index

  4. hi points to the high index

  5. While value at lo is less than pivot move right

  6. While value at hi is greater than pivot move left

  7. If both step 5 and step 6 does not match, swap lo and hi

  8. If lo ≥ hi, the point where they met is new pivot

  9. Repeat steps 1- 8 for both left sublist and right sublist
• Quick Sort Algorithm Example

  • Pivot = 54
• How to choose a good pivot?

  1. First element

  2. Last element

  3. Median-of-three elements (pick three elements, and find the median x of these elements. Use that median as the pivot)

  4. Random element (randomly pick an element as a pivot)
• Quicksort: Array-based Lists in C++

  Given starting and ending list indices

  Function quickSort calls recQuickSort

  Function recQuickSort implements the recursive version of quicksort

  Function partition passes starting and ending list indices

  Function swap swaps certain elements of the list

  
• Analysis of Quicksort

  • for a list of length n
• Mergesort


  A divide-and-conquer algorithm

  Divide the elements into two groups

  Sort each group recursively

  Merge the two sorted lists
• How to Divide?

  For arrays: Divide the length of the array by two

  For linked lists: Use two pointers - middle and current. Advance middle by one node, advance current by one node. If current is NULL, then middle points to the last node of the first sublist.
• How to Merge Efficiently?

  For linked lists: Compare the elements of the sublists, adjust the references of the nodes with the smaller info.
• Analysis of Mergesort

  • Maximum number of comparisons: O(n log2n)

  Average number of comparisons: O(n log2n) if n is a power of 2
• Selection sort makes (1/2)n(n -1) key comparisons and 3(n-1) item assignments

  
• On average, insertion sort makes (1/4)n2 + O(n) = O(n2) key comparisons and (1/4)n2 + O(n) = O(n2) item assignments

  
• Empirical studies suggest that for large lists of size n, the number of moves in Shellsort is in the range of n1.25 to 1.6n1.25
• Any sorting algorithm that sorts a list of n distinct elements by comparison of the keys only, in its worst case, makes at least O(nlog2n) key comparisons

  
• Both quicksort and mergesort sort a list by partitioning the list
• In quicksort, the sorting work is done in partitioning the list, and the number of key comparisons is O(nlog2n) on average and O(n2) in the worst case