## The Brevity of Functional Languages

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.

*01 Oct 2010*
*Damien Wintour*
0 comments