Zhuzhu

Learning Algorithm: Sorting

Introduction

Sorting is algorithms that put elements of an array in a certain order. Efficient sorting is important for what require sorted data.

In this blog, the assumption for these algorithms is that the entire sort can be done in main memory.

Comparison

A basic comparison of some algorithms:

Name Best Average Worst Memory Stable Comment
Insertion sort Ω(N) Θ(N2) O(N2) 1 Yes  
Shell sort Ω(N*log(N)) Depends on gap sequence Depends on gap sequence; best known is O(N4/3) 1 No  
Heapsort Ω(N*log(N)) (N if all keys are not distinct) Θ(N*log(N)) O(N*log(N)) 1 No  
Mergesort Ω(N*log(N)) Θ(N*log(N)) O(N*log(N)) n Yes  
Quicksort Ω(N*log(N)) Θ(N*log(N)) O(N2) log(N) Both  
Bucket Sort Ω(N+M) Θ(N+M) O(N2) N+M Yes Use other sorting algorithms to sort buckets
Bubble Sort Ω(N) Θ(N2) O(N2) 1 Yes  
Selection Sort Ω(N2) Θ(N2) O(N2) 1 No  

Insertion Sort

Insertion sort is one of the simplest sorting algorithm that is quite suitable for small data but is less efficient on large data.

The steps of insertion sort are simple:

  1. Loop the element from the second to the last.
  2. Compare the element to the elements before it, and switch the places until it is larger.

insertion sort (Source: Wikipedia and Wikimedia)

Shell Sort

Shell sort is a generalization of insertion sort that allows the exchange of elements that are far apart.

The steps of shell sort are:

  1. Sort pairs of elements far apart from each other by gap.
  2. Reduce the gap and repeat until gap is 1.

shell sort (Source: Wikipedia and Wikimedia)

The worst case of shell sort is complicated and depends on the gap sequence.

Heapsort

Heap sort is a comparison-based sorting algorithm using binary heap data structure.

The steps of heap sort are:

  1. Build a max heap from the array. Then the largest element is at the root of the heap.
  2. Swap the first element with the last element.
  3. Build a max heap without considering the last element.
  4. Then repeat the step 2 and step 3 until the considered range of elements is only one.

heap sort (Source: Wikipedia and Wikimedia)

Mergesort

Merge sort is an efficient comparison-based sorting algorithm. The fundamental operation of merge sort is merging two sorted separated arrays.

The steps of merge sort are:

  1. Divide the array into two arrays from the middle.
  2. Repeat the division until each array contains only one element.
  3. Repeat merging pairs of arrays by comparison of elements.

merge sort (Source: Wikipedia and Wikimedia)

Quicksort

Quick sort is a divide and conquer algorithm. It is quite efficient.

The steps of quick sort are:

  1. Pick an element called a pivot. Normally, you can pick the first one, the last one, the median one or a random one. But it is a risk to choose the first or the last when the array is pre-ordered.
  2. Partitioning: reorder the array so that all elements that are less than the pivot come before the pivot and all elements that are larger than the pivot come after the pivot.
  3. Recursively apply the above steps to the sub-array.

quick sort (Source: Wikipedia and Wikimedia)

Bucket Sort

Bucket sort is a distribution sort that works by putting elements into some buckets.

The steps of bucket sort are:

  1. Create several empty buckets.
  2. According to the distribution and range of each buckets, put each element into its corresponded bucket.
  3. Sort each non-empty bucket using one of the simple sort algorithms.
  4. Concatenate the buckets in order or put all elements into the original array based on the order of buckets.

bucket sort1 bucket sort2 (Image source: Wikipedia and Wikimedia)

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly compares adjacent pairs and swaps them if they are in wrong order.

bubble sort (Source: Wikipedia and Wikimedia)

Selection Sort

The basic idea of selection sort is finding the minimum element repeatedly.

The steps of selection sort are:

  1. Find the minimum element from the array.
  2. Move it to the front of the array.
  3. Find the minimum element from the rest part of the array.
  4. Move it to the front of the sub-array.
  5. Repeat step 3 and step 4.

selection sort (Source: Wikipedia and Wikimedia)

Source Code

The sources of implementation for these sorting algorithms can be found in my GitHub.

External Sorting

Sorting that cannot be performed in main memory and must be done on disk is also important.

There are some external sorting algorithms such as external merge sort(multiway merge, polyphase merge, replacement selection) and external distribution sort.

References

  1. “Data Structures and Algorithm Analysis in Java” by Mark A. Weiss.
  2. 《数据结构（C语言）》 by 严蔚敏 吴伟民
  3. GitHub - ZhuzhuLearning/Algorithm
blog comments powered by Disqus

Published

05 June 2019

Tags