Sorting Algorithms in a few Words

This note contains the basic ideas of different sorting algorithms in brief and plain words. It is for my own revision purpose and does not guarantee to be fully accurate.

Selection Sort

  • Start from A[0] (subject), find the smallest number among all elements
  • Swap the subject element with the smallest number that was found
  • Repeat the above steps start from the next position (A[1])
  • Keep on repeating until the last cycle
  • It is basically the worst sorting algorithm as you must check until the last cycle and can’t skip checking any element
  • Runtime: O(n^2)

Bubble Sort

  • Start from A[0], compare A[0] with A[1]. Swap them if A[0] is larger
  • Shift the comparison window by 1. That’s mean A[1] and A[2] are to be compared in the next step
  • Repeat until the last 2 elements are checked. By then the largest element will be at the last position and fixed
  • Restart the checking from A[0]. Do the comparison and swap from A[0] until the last unfixed element
  • Keep on repeating until no element is swapped in a cycle or reach the last cycle
  • Runtime: O(n^2)

Insertion Sort

  • Start from A[1], compare A[1] with A[0]. Swap them if A[1] is smaller
  • Move on to A[2]. Compare A[2] with A[1]. Swap them if A[2] is smaller
  • If a swap is performed, continue to compare A[1] with A[0] and swap them if A[1] is smaller
  • Repeat the above steps with the next elements. We keep comparing the subject element with the previous elements and swap them until the subject is no longer smaller than the previous elements
  • In each cycle, the subject element would be inserted into the correct sorted position
  • Runtime: O(n^2)

Quick Sort

  • Select a pivot value
  • Go through the array. Put elements smaller than the pivot to a new array on the left, elements larger than or equal to the pivot are put into a new array on the right
  • Do the same thing above to the new arrays to split them into smaller arrays
  • Repeat until there are n arrays
  • Merge the arrays from left to right. Then the combined array is sorted
  • It is important to choose a suitable pivot to make the sub-arrays balanced. One common method is to choose the median of the first, last and the middle elements
  • Runtime: O(n log n)

Merge Sort

  • Keep splitting the array into half until all sub-arrays contain only 1 element
  • Merge the arrays 2 by 2. Sort the elements during merging
  • To sort while merging, compare one element from an array to another and then put the smaller one to the new array
  • Runtime: O(n log(n))

Counting Sort

  • Make an array with size equal to the largest value among the numbers to be sorted. The index of the array represent the values
  • Go through all the numbers to be sorted. Increase the counter at the corresponding index. (e.g. If the number is 5, add A[5] by 1)
  • Go through the array from A[0]. Reproduce the number with regard to the value in each index to the new sorted array (i.e. If A[0] = 5, insert 0 into the sorted array 5 times)
  • Runtime: O(n+k)

Binary Sort

  • Put all elements into a binary search tree
  • Use in-order traversal to visit the elements from the smallest to the largest

Heap Sort

  • Put all the elements into a heap
  • Keep perform delete min operation to pop out the smallest number one by one
  • Runtime: O(n log n)


在下方填入你的資料或按右方圖示以社群網站登入: 標誌

您的留言將使用 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )


您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s