I will give all examples in ascending order, just change the judgement clause when you need descending order.
$O(n^2)$ sorting algorithms
Selection Sort
The idea is, always select the smallest value from the unsorted list and swap it with the first element of the unsorted part. I call it “Head In Order First”.
| Sorted | Unsorted |
|---|---|
| [] | [7 4 8 2 5 3 9] |
| [2] | [7 4 8 5 3 9] |
| [2 3] | [7 4 8 5 9] |
| [2 3 4] | [7 8 5 9] |
| [2 3 4 5] | [7 8 9] |
| [2 3 4 5 7] | [8 9] |
| [2 3 4 5 7 8] | [9] |
| [2 3 4 5 7 8 9] | [] |
Insertion Sort
The idea is, always insert the first value in unsorted list into a proper position of sorted list. I call it “Part In Order First”.
| Sorted | Unsorted |
|---|---|
| [] | [7 4 8 2 5 3 9] |
| [7] | [4 8 2 5 3 9] |
| [4 7] | [8 2 5 3 9] |
| [4 7 8] | [2 5 3 9] |
| [2 4 7 8] | [5 3 9] |
| [2 4 5 7 8] | [3 9] |
| [2 3 4 5 7 8] | [9] |
| [2 3 4 5 7 8 9] | [] |
Bubble Sort
The idea is, always compare nearby two elements, and swap if necessary. For each pass, adjacent elements are compared and swapped if necessary. After each pass, the largest element moves to the end, so the tail part becomes sorted. I call it “Tail In Order First”.
| Unsorted | Sorted |
|---|---|
| [7 4 8 2 5 3 9] | [ ] |
| [4 7 2 5 3 8] | [9 ] |
| [4 2 5 3 7] | [8 9 ] |
| [2 4 3 5] | [7 8 9 ] |
| [2 3 4] | [5 7 8 9 ] |
| [2 3] | [4 5 7 8 9 ] |
| [2] | [3 4 5 7 8 9 ] |
| [] | [2 3 4 5 7 8 9] |
$O(n\log n)$ sorting algorithms
Heap Sort
Heap sort uses heap as data structure, each time put a new value into the heap, the time cost of upheap is always $O(\log n)$. Then always delete min value from the heap, which is also $O(\log n)$ time cost for downheap.
This algorithm needs extra space at $\Theta(n)$.
Merge Sort
This is a recursive solution: The first step is, always divide the array into two parts, and sort each part respectively. Continue until the base case which is only 1 or no element: just return it self. Then return step-by-step, merge each part together inorder.
Easier Approach in C++/Java/Python
You don’t need to implement the sort algorithm for most time, just use C++ STL or any other built-in function of your programming language.
All built-in functions have time complexity $O(n \log n)$.
C++
In C++, use following function in <algorithm>. You can write compare function to compare anything if you want.
1
2
sort(a,a+n);
sort(a,a+n, cmp);
Java
In Java, use the following function, from java.util.Arrays
Arrays.sort(arr1);
and define compare function.
1
2
3
4
Integer[] arr = {2, -1, 3, 4};
Arrays.sort(arr, Collections.reverseOrder());
System.out.println(Arrays.toString(arr));
Python
In Python, there’re also two approaches, Sorted will return a sorted list, and .sort will change the value inpalce return None.
sorted(a)
a.sort()
You can also define compare function, sorting in python
1
2
3
4
5
6
7
8
9
10
sorted("This is a test string from Andrew".split(), key=str.casefold)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
student_tuples = [
('john', 'A', 15),
('jane', 'B', 12),
('dave', 'B', 10),
]
sorted(student_tuples, key=lambda student: student[2]) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]