QuickSort is a well-known, efficient, sort algorithm. In previous posts I've discussed the runtime and space complexity of this algorithm, but there are some other factors that are rather important: brevity and clarity of code. Let's examine this by looking at the implementation of quicksort in C#, Java, C++ and F#.
Here is my version of quick sort in non-generic Java:
1: public static void quickSort(int[] input, int start, int finish)
2: {
3: if (finish-start < 2)
4: return;
5:
6: //pick a pivot
7: int pivotIndex = (finish+start)/2;
8:
9: //partition about the pivot
10: int i=start, j=finish;
11: while(i<=j)
12: {
13: while(input[i] < input[pivotIndex])
14: i++;
15:
16: while(input[j] > input[pivotIndex])
17: j--;
18:
19: if(i<=j)
20: {
21: int temp = input[i];
22: input[i]=input[j];
23: input[j]=temp;
24: i++;
25: j--;
26: }
27: }
28:
29: if (start < i-1)
30: quickSort(input, start, i-1);
31:
32: if (i < finish)
33: quickSort(input, i, finish);
34: }
And here it is in a generic C# flavour:
1: public static void QuickSort<T>(T[] input)
2: where T : IComparable<T>
3: {
4: QuickSort(input, 0, input.Length - 1);
5: }
6:
7: public static void QuickSort<T>(T[] input, int start, int finish)
8: where T:IComparable<T>
9: {
10: if (finish - start < 2)
11: return;
12:
13: //pick a pivot
14: int pivotIndex = (finish + start) / 2;
15:
16: //partition about the pivot
17: int i = start, j = finish;
18: while (i <= j)
19: {
20: while (input[i].CompareTo(input[pivotIndex]) < 0)
21: i++;
22:
23: while (input[j].CompareTo(input[pivotIndex]) > 0)
24: j--;
25:
26: if (i <= j)
27: {
28: T temp = input[i];
29: input[i] = input[j];
30: input[j] = temp;
31: i++;
32: j--;
33: }
34: }
35:
36: if (start < i - 1)
37: QuickSort(input, start, i - 1);
38:
39: if (i < finish)
40: QuickSort(input, i, finish);
41: }
Here's my C++ code :
1: void quickSort(int arr[], int left, int right) {
2: int i = left, j = right;
3: int tmp;
4: int pivot = arr[(left + right) / 2];
5:
6: /* partition */
7: while (i <= j) {
8: while (arr[i] < pivot)
9: i++;
10: while (arr[j] > pivot)
11: j--;
12: if (i <= j) {
13: tmp = arr[i];
14: arr[i] = arr[j];
15: arr[j] = tmp;
16: i++;
17: j--;
18: }
19: };
20:
21: /* recursion */
22: if (left < j)
23: quickSort(arr, left, j);
24: if (i < right)
25: quickSort(arr, i, right);
26: }
Here's some Erlang code to do the same:
qsort([]) -> [];
qsort([Pivot|T]) ->
qsort([X || X <- T, X =< Pivot])
++ [Pivot] ++
qsort([X || X <- T, X > Pivot]).
And finally, here's my F# code, that admittedly does it slightly differently in that it selects the first items as the pivot:
#light
open System
let rec quickSort ls =
match ls with
| [] -> []
| p::r ->
quickSort [for i in r do if (compare i p) <= 0 then yield i]
@ [p]
@ quickSort [for i in r do if (compare i p) > 0 then yield i]
I know I've mentioned it before on this site, but despite my deep admiration for C++ , Java and C# - they are all great languages - it's painfully clear that, with their advanced list comprehension syntax, functional languages are great at producing succinct code that is very easy to turn into highly parallelized code! With multi-core servers the norm these days these features of functional languages are extremely attractive.
