Given a sequence of elements, sorting them means that ordering them in a particular fashion. In general, when we talk about sorting, we are talking about ordering them in ascending order.
Example
Initial Sequence: 3, 4, 1, 6, 2, 5
After Sorting: 1, 2, 3, 4, 5, 6
The values might be integers, or strings, or even other kinds of objects.
The most popular sorting algorithms are:
We will be learning about all these algorithms.
Reference table for time complexities of popular sorting algorithms:
|
Algorithm |
Best Case |
Average Case |
Worst Case |
|
Bubble Sort |
O(n) |
O(n2) |
O(n2) |
|
Selection Sort |
O(n2) |
O(n2) |
O(n2) |
|
Insertion Sort |
O(n) |
O(n2) |
O(n2) |
|
Merge Sort |
O(n log(n)) |
O(n log(n)) |
O(n log(n)) |
|
Quick Sort |
O(n log(n)) |
O(n log(n)) |
O(n2) |
Bubble Sort
Introduction
Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly iterating through the list, comparing adjacent elements, and swapping if they are in the wrong order.
Because of its poor performance, it is not practically used and is just used for educational purposes.
Example
Initial Array: 6 5 3 1 8 7 2 4
First Iteration:
- 5 6 3 1 8 7 2 4
- 5 3 6 1 8 7 2 4
- 5 3 1 6 8 7 2 4
- 5 3 1 6 8 7 2 4
- 5 3 1 6 7 8 2 4
- 5 3 1 6 7 2 8 4
- 5 3 1 6 7 2 4 8
Second Iteration:
- 3 5 1 6 7 2 4 8
- 3 1 5 6 7 2 4 8
- 3 1 5 6 7 2 4 8
- 3 1 5 6 7 2 4 8
- 3 1 5 6 2 7 4 8
- 3 1 5 6 2 4 7 8
- 3 1 5 6 2 4 7 8
Third Iteration:
- 1 3 5 6 2 4 7 8
- 1 3 5 6 2 4 7 8
- 1 3 5 6 2 4 7 8
- 1 3 5 2 6 4 7 8
- 1 3 5 2 4 6 7 8
- 1 3 5 2 4 6 7 8
- 1 3 5 2 4 6 7 8
Fourth Iteration:
- 1 3 5 2 4 6 7 8
- 1 3 5 2 4 6 7 8
- 1 3 2 5 4 6 7 8
- 1 3 2 4 5 6 7 8
- 1 3 2 4 5 6 7 8
- 1 3 2 4 5 6 7 8
- 1 3 2 4 5 6 7 8
Fifth Iteration:
- 1 3 2 4 5 6 7 8
- 1 2 3 4 5 6 7 8
- 1 2 3 4 5 6 7 8
- 1 2 3 4 5 6 7 8
- 1 2 3 4 5 6 7 8
- 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
Visualization
Code
C++
void bubbleSort(int arr[], int n) {
bool swapped;
while (true) {
swapped = false;
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
int temp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = temp;
swapped = true;
}
}
if (swapped == false) {
break;
}
}
}Java
static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
while (true) {
swapped = false;
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
int temp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = temp;
swapped = true;
}
}
if (swapped == false) {
break;
}
}
}Complexity Analysis
Time Complexity
- Best Case: O(n)
- Average Case: O(n2)
- Worst Case: O(n2)
Space Complexity: O(1)
Selection Sort
Introduction
Selection Sort is one of the simplest sorting algorithms. It works by creating a sorted array by finding and adding the correct element in each iteration.
The sequence (array) is divided into two parts: sorted part and unsorted part. In each iteration, pick the smallest element from the unsorted part, exchange it with the leftmost unsorted element and move the boundary by one place to include another element in the sorted part. After all the iterations, the entire array gets sorted.
Example
Initial Array: 3, 4, 1, 6, 2, 5
In each iteration, we will move the smallest element from the unsorted part to the sorted part. The sorted part is marked bold.
Before the first iteration:
3, 4, 1, 6, 2, 5
After iteration 1:
1, 4, 3, 6, 2, 5
After iteration 2:
1, 2, 3, 6, 4, 5
After iteration 3:
1, 2, 3, 6, 4, 5
After iteration 4:
1, 2, 3, 4, 6, 5
After iteration 5:
1, 2, 3, 4, 5, 6
After iteration 6:
1, 2, 3, 4, 5, 6
Visualization
Code
C++
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}Java
static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}Complexity Analysis
Time Complexity
- Best Case: O(n2)
- Average Case: O(n2)
- Worst Case: O(n2)
Space Complexity: O(1)
Insertion Sort
Introduction
Insertion Sort is one of the simplest sorting algorithms. Most people use this algorithm subconsciously while arranging playing cards in their hands.
The sequence (array) is divided into two parts: sorted part and unsorted part. In each iteration, one element from the unsorted part is moved to the correct position in the sorted part. After all the iterations, the entire array gets sorted.
Insertion Sort is one of the fastest sorting algorithms for sorting very small input.
Example
Initial Array: 3, 4, 1, 6, 2, 5
In each iteration, we will move one element from the unsorted part to its correct position in the sorted part. The sorted part is marked bold.
Before first iteration:
3, 4, 1, 6, 2, 5
After iteration 1:
3, 4, 1, 6, 2, 5
After iteration 2:
1, 3, 4, 6, 2, 5
After iteration 3:
1, 3, 4, 6, 2, 5
After iteration 4:
1, 2, 3, 4, 6, 5
After iteration 5:
1, 2, 3, 4, 5, 6
Visualization
Code
C++
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}Java
static void insertionSort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}Complexity Analysis
Time Complexity
- Best Case: O(n)
- Average Case: O(n2)
- Worst Case: O(n2)
Space Complexity: O(1)
Part II: Sorting Algorithms (Quick Sort, Merge Sort) | DSA Tutorials
