Data Structure and Algorithm - Sort

0. Introduction

• Bubble sort
• Insertion sort
• Selection sort
• Merge sort
• Quick sort
• Heap sort

1. Bubble sort

A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. It has a worst-case and average-case time complexity of O(n^2).

#include <iostream>
#include <vector>

using namespace std;

void bubble_sort(vector<int>& arr) {
	for (int i = 0; i < arr.size() - 1; i++) {
		// EACH ROUND WILL MOVE THE LARGEST ELEMENT TO THE LAST
		for (int j = 0; j < arr.size() - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				// SWAP arr[j] and arr[j + 1]
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int main() {
	vector<int> arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
	bubble_sort(arr);
	for (int x : arr) {
		cout << x << " ";
	}
	cout << endl;
	return 0;
}

2. Insertion sort

A simple sorting algorithm that builds the final sorted array one item at a time. It has a worst-case and average-case time complexity of O(n^2).

#include <iostream>
#include <vector>

using namespace std;

void insertion_sort(vector<int>& arr) {
	int n = arr.size();
	for (int i = 1; i < n; i++) {
		int key = arr[i];
		int j = i - 1;
		// MOVE BACK
		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = key;
	}
}

int main() {
	vector<int> arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
	insertion_sort(arr);
	for (int x : arr) {
		cout << x << " ";
	}
	cout << endl;
	return 0;
}

3. Selection sort

A simple sorting algorithm that repeatedly selects the minimum element from the unsorted portion of the list and swaps it with the leftmost unsorted element. It has a worst-case and average-case time complexity of O(n^2).

#include <iostream>
#include <vector>

using namespace std;

void selection_sort(vector<int>& arr) {
	for (int i = 0; i < arr.size() - 1; i++) {
		// FIND MIN ELEMENT INDEX
		int min_index = i;
		for (int j = i + 1; j < arr.size(); j++) {
			if (arr[j] < arr[min_index]) {
				min_index = j;
			}
		}
		// SWAP arr[i] and arr[min_index]
		int tmp = arr[i];
		arr[i] = arr[min_index];
		arr[min_index] = tmp;
	}
}

int main() {
	vector<int> arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
	selection_sort(arr);
	for (int x : arr) {
		cout << x << " ";
	}
	cout << endl;
	return 0;
}

4. Merge sort

A divide-and-conquer algorithm that recursively divides the input list into two halves, sorts each half, and then merges the sorted halves back together. It has a worst-case and average-case time complexity of O(n log n).

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
	int arr1_size = mid - left + 1;
	int arr2_size = right - mid;
	vector<int> L(arr1_size), R(arr2_size);
	// Copy ARR -> L, R
	for (int i = 0; i < arr1_size; i++) {
		L[i] = arr[left + i];
	}
	for (int j = 0; j < arr2_size; j++) {
		R[j] = arr[mid + 1 + j];
	}
	// MERGE L, R TO ONE ARR
	int i = 0, j = 0, k = left;
	while (i < arr1_size && j < arr2_size) {
		if (L[i] <= R[j]) {
			arr[k++] = L[i++];
		}
		else {
			arr[k++] = R[j++];
		}
	}
	// COPY REST ELEMENT
	while (i < arr1_size) {
		arr[k++] = L[i++];
	}
	while (j < arr2_size) {
		arr[k++] = R[j++];
	}
}

void merge_sort(vector<int>& arr, int left, int right) {
	if (left >= right) {
		return;
	}
	int mid = left + (right - left) / 2;
	merge_sort(arr, left, mid);
	merge_sort(arr, mid + 1, right);
	merge(arr, left, mid, right);
}

int main() {
	vector<int> arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
	merge_sort(arr, 0, arr.size() - 1);
	for (int x : arr) {
		cout << x << " ";
	}
	cout << endl;
	return 0;
}

5. Quick sort

A divide-and-conquer algorithm that recursively partitions the input list into two sub-lists based on a pivot element, and then sorts each sub-list. It has a worst-case time complexity of O(n^2), but an average-case time complexity of O(n log n).

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& arr, int left, int right) {
	int pivot = arr[left];
	while (left < right) {
		while (left < right && arr[right] >= pivot) --right;
		arr[left] = arr[right];
		while (left < right && arr[left] <= pivot) ++left;
		arr[right] = arr[left];
	}
	arr[left] = pivot;
	return left;
}

void quick_sort(vector<int>& arr, int left, int right) {
	if (left < right) {
		int pivot_pos = partition(arr, left, right);
		quick_sort(arr, left, pivot_pos - 1);
		quick_sort(arr, pivot_pos + 1, right);
	}
}

int main() {
	vector<int> arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
	quick_sort(arr, 0, arr.size() - 1);
	for (int x : arr) {
		cout << x << " ";
	}
	cout << endl;
	return 0;
}

6. Heap sort

A sorting algorithm that uses a binary heap data structure to repeatedly extract the maximum element from the heap and place it at the end of the sorted array. It has a worst-case and average-case time complexity of O(n log n).

#include <iostream>
#include <vector>

using namespace std;

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heap_sort(vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    vector<int> arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
    heap_sort(arr);
    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}