Sorting Methods in Algorithm

Methods in Action

Bubble Sort

Worst complexity: n2
Average complexity: n2
Best complexity: n
Space complexity: 1
Stable: Yes

Selection Sort

Worst complexity: n2
Average complexity: n2
Best complexity: n2
Space complexity: 1
Stable: No

Insertion Sort

Worst complexity: n2
Average complexity: n2
Best complexity: n
Space complexity: 1

Quicksort


(Picture from Techie Delight)

Worst complexity: n2
Average complexity: nlog(n)
Best complexity: n
log(n)
Space complexity: log(n)

Comparisions

Bubble vs Selection

Their direction is different.
A bubble sort compares the members one by one and swaps when the former is larger than the latter in the current pair.
A selection sort determine the smallest one in an iteration and make it swap with the first number in the array of the current iteration before the iteration ends.
Selection Sort is twice as fast as Bubble Sort. (Complexity still the same as that of Bubble Sort, because in the world of Big O, constants r ignored.)1

Selection vs Insertion

In an average case, where an array is randomly sorted, they perform similarly.1
If an array is mostly sorted, selection is a better choice.1

Insertion vs Quicksort

Insertion Sort is actually faster than Quicksort for a best-case scenario. However, Quicksort is much more superior than Insertion Sort in the average scenaro, thus more popular. 1

Overview

Hmm, I've only seen 4 methods in the referenced guide1. So maybe I'll check others out later.......

Now I'll head out to Leetcode for some practice.


  1. Wengrow, Jay. A Common-Sense Guide to Data Structures and Algorithms. Pragmatic Bookshelf, 2020.