A simple Quicksort in place


I’ve been “practising” my quicsort skills lately, and tried various ways of implementing it, but I think the Lomuto partition scheme is the best and potentially the easiest to implement.

int Partition(ref int[] intArray, int low, int high) {
    // Pivot is set to the last element   
    var pivot = intArray[high];
    var i = low - 1;
 
    for (var j = low; j <= high; j++) {
        if (intArray[j] <= pivot) {
            i++;
 
            if (i != j) {
		// Swap ints at pos i & j
                var tmp = intArray[i];
                intArray[i] = intArray[j];
                intArray[j] = tmp;
            }
        }
    }

    return i;
}
 
int[] Sort(int[] intArray, int low, int high) {
    if (low < high) {
        var p = Partition(ref intArray, low, high);
        intArray = Sort(intArray, low, p - 1);
        intArray = Sort(intArray, p + 1, high);
    }
 
    return intArray;
}
 
Sort(intArray, 0, arraySize - 1);
Advertisements