Tag: sorting

ShellSort is not a comparison-based sorting algorithm like those previously shown on this blog, it uses the property of InsertionSort that nearly sorted arrays of values are sorted very quickly. It has a performance of O(n log² n) which makes it a lot faster than a lot of other algorithms, certainly the O(n²) ones, but not entirely the fastest.

public static void shellSort(int[] ia) {
	int l = ia.length;
	if (l == 1)
		return;
	int inc = l / 2;
	while (inc != 0) {
		for (int i = inc; i != l; i++) {
			int t = ia[i];
			int j = i;
			while (j >= inc && ia[j - inc] > t) {
				ia[j] = ia[j - inc];
				j = j - inc;
			}
			ia[j] = t;
		}
		inc = (int) (inc / 2.2);
	}
}

Read More

Another O(n²) sorting algorithm, however it’s more efficient than most O(n²) algorithms like BubbleSort and SelectionSort.

public static void insertionSort(int[] ia) {
	int l = ia.length;
	if (l == 1)
		return;
	for (int i = 0; i != l; i++)
		for (int j = i; j != 0; j--)
			if (ia[j] < ia[j - 1]) {
				int t = ia[j];
				ia[j] = ia[j - 1];
				ia[j - 1] = t;
			}
}

Read More

SelectionSort is another sorting algorithm that has a performance of O(n²) like BubbleSort. It sorts an array of numbers by finding the smallest element in the unsorted part of the array and switching it with the current item. This is repeated until the entire array is sorted.

public static void selectionSort(int[] ia) {
	int l = ia.length;
	if (l == 1)
		return;
	for (int i = 0; i != l; i++) {
		int s = i;
		for (int j = i; j != l; j++)
			if (ia[j] < ia[s])
				s = j;
		int t = ia[i];
		ia[i] = ia[s];
		ia[s] = t;
	}
}

Read More

The bubblesort algorithm is one of the slowest sorting algorithms around as it’s performance is O(n²). As a result of this the algorithm is barely ever used in any real life applications, however, even though the algorithm will always stay rather slow, it can be tweaked to improve the code’s performance.

The implementation of the algorithm you see below has been optimized in various ways and it also makes use of the property that all items in an array of numbers that come after the last index that was sorted in a run through the array by the algorithm are already sorted.

public static void bubbleSort(int[] ia) {
	int l = ia.length, i = l;
	if (l == 1)
		return;
	while (i != 0) {
		int last = 0;
		for (int j = 1; j != i; j++)
			if (ia[j - 1] > ia[j]) {
				int t = ia[j];
				ia[j] = ia[j - 1];
				ia[j - 1] = t;
				last = j;
			}
		i = last;
	}
}

Read More