Elementary Sorts
Selection Sort
O(1/2(n^2)) -> O(n^2). It is in-place sort. We find smallest value and move it to the front. It is not stable algorithm.
class SortArray {
static void main(String[] args) {
int[] array = [1, 5, 7, 3, 9, 1, -2]
println array
sort(array)
println array
}
static void sort(int[] array) {
int min
int temp
for (int i = 0; i < array.length; i++) {
min = i
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[min]) {
min = j
}
}
temp = array[i]
array[i] = array[min];
array[min] = temp;
}
}
}
Insertion Sort
Complexity is about O(1/4(n^2)) in optimistic case - when the array is partially sorted, this algorithm works perfectly In worst case, it is O(1/2(n^2)) - when the values in reversed order. In general, O(n^2). It is in-place and stable. For sorted list, the complexity is O(n).
class InsertionSortArray {
static void main(String[] args) {
int[] array = [1, 5, 7, 3, 9, 1, -2]
println array
sort(array)
println array
}
static void sort(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = i; j > 0; j--) {
if (array[j] < array[j -1]) {
int temp = array[j]
array[j] = array[j - 1]
array[j - 1] = temp;
} else {
break
}
}
}
}
}
Shell Sort
O(n^(3/2). Not stable, can be done in-place.
class ShellSortArray {
static void main(String[] args) {
int[] array = [1, 5, 7, 3, 9, 1, -2]
println array
sort(array)
println array
}
static void sort(int[] a) {
int N = a.length;
int h = 1;
while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, ...
while (h >= 1) { // h-sort the array.
for (int i = h; i < N; i++) {
for (int j = i; j >= h && a[j] < a[j - h]; j -= h) {
int temp = a[j]
a[j] = a[j - h];
a[j - h] = temp;
}
}
h = h / 3;
}
}
}
Example: shuffle cards randomly
First idea: Generate random numbers and assign them to cards. Then sort the array.
Knuth shuffle: iterate through the cards and generate random number that is between 0 and i (i is current index).
Convex Hull
The first approach to calculate a convex hull could be:
Find most left point
Then find most right point to that point and repeat this until we get to the most left point

Last updated
Was this helpful?