Bubble Sort
Bubble sort is the simplist sorting algorithm, it repeatly swap the adjacent elements if they are in the wrong order.
The time complexity is $O(N^2)$.
class BubbleSort {
public void bubbleSort(int[] arr) {
for (int i=0; i<arr.length-1; i++) {
for (int j=0; j<arr.length -i-1; j++) {
if (arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
}
Selection Sort
Selection sort divide the input into two parts, sorted and unsorted. It repeatly choose the smallest element from the unsorted part and put it at the beginning of the unsorted part.
The time complexity is $O(N^2)$.
class SelectionSort {
public void selectionSort(int[] arr) {
for (int i=0; i<arr.length; i++) {
int minIdx = i;
for (int j=i+1; j<arr.length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
}
}
Insertion Sort
Insertion sort starts from the beginning of the array and repeatly insert the i^th element to the correct position of the first i elements.
The time complexity is $O(N^2)$.
class InsertionSort {
public void insertionSort(int[] arr) {
for (int i=1; i<arr.length-1; i++) {
int key = arr[i];
for (int j=i-1; j>=0; j--) {
if (arr[j] > key) {
arr[j+1] = arr[j];
arr[j] = key;
}
}
}
}
}
Merge Sort
Merge sort is a Divide and Conquer algorithm, it divde the array into two halves and recursive call itself until there is less or equal than one element in each half, and then merge them together in the correct order.
The time complexity is $O(NlogN)$.
class MergeSort {
public void mergeSort(int[] arr, int left, int right) {
if (left<right) {
int middle = (left+right) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle+1, right);
merge(arr, left, middle, right);
}
}
public void merge(int[] arr, int left, int middle, int right) {
int n1 = middle-left+1;
int n2 = right-middle;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i=0; i<n1; i++) {
L[i] = arr[left+i];
}
for (int i=0; i<n2; i++) {
R[i] = arr[middle+i+1];
}
int i=0;
int j=0;
int k=left;
while (i<n1 && j<n2) {
if (L[i]<R[j]) {
arr[k] = L[i];
k++; i++;
} else {
arr[k] = R[j];
k++; j++;
}
}
while (i<n1) {
arr[k] = L[i];
i++; k++;
}
while (j<n2) {
arr[k] = R[j];
j++; k++;
}
}
}
Quick Sort
Quick sort is also a Divide and Conquer algorithm. It usually choose the last element as pivot and put it in the correct position and keep doing so for the part before the pivot (which are smaller than pivot) and the part after the pivot (which are larger than pivot).
The average time complexity is $O(NlogN)$, but worst case can be $O(N^2)$.
class QuickSort {
public void quickSort(int[] arr, int left, int right) {
if (left<right) {
int pi = partition(arr, left, right);
quickSort(arr, left, pi-1);
quickSort(arr, pi+1, right);
}
}
public int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left;
for (int j=left; j<right; j++) {
if (arr[j] < pivot) {
int tmp = arr[j];
arr[i] = arr[j];
arr[j] = tmp;
i++;
}
}
arr[right] = arr[i];
arr[i] = pivot;
return i;
}
}
Heap Sort
Heap sort is based on Binary Heap, we use a max heap to find the largest element and then place it to the correct position, we use heapify to maintain the quality of the binary heap.
The time complexity is $O(NlogN)$.
class HeapSort {
public void heapSort(int[] arr) {
int n = arr.length;
for (int i=n/2; i>=0; i--) {
heapify(arr, n, i);
}
for (int i=n-1; i>=0; i--) {
int tmp = arr[i];
arr[i] = arr[0];
arr[0] = tmp;
heapify(arr, i, 0);
}
}
// max heap
public void heapify(int[] arr, int n, int root) {
int maxIdx = root;
int left = root*2+1;
int right = root*2+2;
if (left < n && arr[left] > arr[maxIdx]) {
maxIdx = left;
}
if (right < n && arr[right] > arr[maxIdx]) {
maxIdx = right;
}
if (maxIdx != root) {
int tmp = arr[root];
arr[root] = arr[maxIdx];
arr[maxIdx] = tmp;
heapify(arr, n, maxIdx);
}
}
}