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.