Seven Sorting Algorithms in a Few Lines
I found these codes when I always looking through my early projects and I decided to share. Let’s start it from the simplest ones to the hardest ones.
private static void bubbleSort(int[] v) {
int i, j, n = v.length;
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
if (v[i] > v[j]) {
swap(v, i, j);
}
}
}
}
private static void selectionSort(int[] v) {
int i, j, min, n = v.length;
for (i = 0; i < n; i++) {
min = i;
for (j = i + 1; j < n; j++) {
if (v[min] > v[j])
min = j;
}
swap(v, min, i);
}
}
private static void insertionSort(int[] v) {
int i, j, temp, n = v.length;
for (i = 1; i < n; i++) {
temp = v[i];
j = i - 1;
while (j >= 0 && v[j] > temp) {
v[j + 1] = v[j];
j--;
}
v[j + 1] = temp;
}
}
private static void shellSort(int[] v) {
int n = v.length;
int range = n / 2;
int i, j, temp;
int gap;
while (range > 0) {
for (i = range; i < n; i++) {
temp = v[i];
j = i;
gap = j - range;
while (j >= range && v[gap] > temp) {
v[j] = v[gap];
j -= range;
gap = j - range;
}
v[j] = temp;
}
range /= 2;
}
}
private static void heapify(int[] v, int pos, int n) {
int low = 2 * pos + 1;
int high = 2 * pos + 2;
int largest, temp;
if (low < n && v[low] > v[pos])
largest = low;
else
largest = pos;
if (high < n && v[high] > v[largest])
largest = high;
if (largest != pos) {
temp = v[largest];
v[largest] = v[pos];
v[pos] = temp;
heapify(v, largest, n);
}
}
private static void heapSort(int[] v) {
int n = v.length, i;
int low = n / 2 - 1, high = n - 1;
// Build initial heap
for (i = low; i >= 0; i--) {
heapify(v, i, n);
}
for (i = high; i > 0; i--) {
swap(v, 0, i);
heapify(v, 0, i);
}
}
// Start with quickSort(v, 0, v.length - 1);
private static int i;
private static int j;
private static void partition(int[] v, int low, int high) {
i = low;
j = high;
int x = v[(i + j) / 2];
while (i <= j) {
while (v[i] < x)
i++;
while (v[j] > x)
j--;
if (i <= j) {
swap(v, j, i);
i++;
j--;
}
}
}
private static void quickSort(int[] v, int low, int high) {
partition(v, low, high);
if (low < j)
quickSort(v, low, j);
if (high > i)
quickSort(v, i, high);
}
// Start with mergeSort(v, 0, v.length - 1);
private static void merge(int[] v, int low, int middle, int high) {
int[] vAux = new int[v.length];
for (int i = low; i <= high; i++) {
vAux[i] = v[i];
}
int i = low;
int j = middle + 1;
int k = low;
while (i <= middle && j <= high) {
if (vAux[i] <= vAux[j]) {
v[k] = vAux[i];
i++;
} else {
v[k] = vAux[j];
j++;
}
k++;
}
while (i <= middle) {
v[k] = vAux[i];
k++;
i++;
}
}
private static void mergeSort(int[] v, int low, int high) {
if (low < high) {
int middle = (low + high) / 2;
mergeSort(v, low, middle);
mergeSort(v, middle + 1, high);
merge(v, low, middle, high);
}
}
private static void swap(int[] v, int i, int j) {
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
This code is also available on my GitHub profile.