Sorting Algorithms Comparison and Quicksort example

Today I’ve remembered those days back in University, when we learned Algorithms and Data Structures. Among the big amount of algorithms we studied, there were the sorting algorithms. The first algorithm introduced was the Bubble Sort, the worst efficient one. Afterwards, the most efficient algorithms were introduced: Merge Sort and Quicksort. Let’s remember the basics of these algorithms.

Bubble Sort

This is the simplest algorithm, however it’s the worst one in performance speaking. The average and worst case complexity are both O(n²). But there is good news, its complexity, for the best case, is only O(n). Here there is an animation that explains how it works: Bubble Sort Animation.

Merge Sort

The Merge Sort algorithm is better than Bubble Sort. The average and worst case complexity is O(nlogn). The best case (when the array is sorted) is also O(nlogn), but with some optimizations can be reduced to O(n). Here you can find another animation Merge Sort.

Quicksort

The Quicksort algorithm is usually faster than Merge Sort, despite they have the same average case complexity O(nlogn). However, the complexity for the worst case is O(n²), with some improvements it can be reduced. Here there is an animation: Quicksort.

Implementation Quicksort

After this brief comparison between sorting algorithms, let’s see the implementation of Quicksort algorithm in Java and Scala.

Java

This is the implementation in Java of the Quicksort algorithm:

public static void sort(int[] xs){
	sort(xs,0,xs.length-1);
}
public static void sort(int[] xs, int left, int right){
	int pivot = xs[(left+right)/2];
	int i = left;
	int j = right;
	while(i <= j){
		while(xs[i] < pivot){
			i++;
		}
		while(xs[j] > pivot){
			j++;
		}
		if(i<=j){
			int sw = xs[i];
			xs[i] = xs[j];
			xs[j] = sw;
			i++;
			j--;
		}
	}
	if(left < j){
		sort(xs,left,j);
	}
	if(j < right){
		sort(xs,i,right);
	}
}

Scala

First the algorithm in a no functional way, as you could see, this implementation is equivalent to Java’s:

def sort(xs: Array[Int]) {
	def swap(i: Int, j: Int) {
		val t = xs(i); xs(i) = xs(j); xs(j) = t
	}
	def sort1(l: Int, r: Int) {
		val pivot = xs((l + r) / 2)
		var i = l; var j = r
		while (i <= j) {
			while (xs(i) < pivot) i += 1
			while (xs(j) > pivot) j -= 1
			if (i <= j) {
				swap(i, j)
				i += 1
				j -= 1
			}
		}
		if (l < j) sort1(l, j)
		if (j < r) sort1(i, r)
	}
	sort1(0, xs.length - 1)
}

And now, let’s rewrite it in a functional way:

def sort(xs: Array[Int]): Array[Int] = {
	if (xs.length <= 1) xs
	else {
		val pivot = xs(xs.length / 2)
		Array.concat(
			sort(xs filter (pivot >)),
			xs filter (pivot ==),
			sort(xs filter (pivot <)))
	}
}