Quick-Sort Algorithm: How to Sort an Array

Introduction

Consider a set of integers without a particular order. We want to sort this set. This article will explain how to perform this operation using the quick-sort algorithm.

Problem Example Quick-Sort Algorithm

Consider an array of integers:

int[] toSortArray = { 5, 1, 2, 4, 3 };

We want to sort the array to get the numbers in their natural ascending order:

{ 1, 2, 3, 4, 5 }

Sort the Array by the Quick-Sort Algorithm

The quick-sort algorithm works recursively by picking a value from the set and re-positioning it with the lower values on its left and the greater ones on its right. We call this a pivot value. In each recurring step, we repeat the above for the left and right sets. We can choose the pivot with various strategies, for example:

• Randomly
• Choosing the first element
• Choosing the last element

In our example, we will choose the last element.

We can describe the recursive algorithm by the following steps:

• If the first element is lower than the last element
• We pick the last element of the set as the pivot
• We set the current lower position for the pivot in the set, initializing it with the position of the left element minus one
• We loop over the remaining elements from left to right
• If the current element is lower than the pivot:
  • We increment the current lower position of the pivot by one
  • We swap the current element with the element in the current lower position
• We increment the current lower position by one and swap its element with the pivot
• We have now a temporary position for the pivot
• We repeat recursively the above steps:
  • For the elements from the start position to the current pivot position
  • For the elements from the current pivot position plus one to the last position

The steps described above are shown in the following code snippet:

private void quickSort(int[] toSortArray, int left, int right) throws Exception {

    if (left < right) {
        int pivotPosition = step(toSortArray, left, right);

        quickSort(toSortArray, left, pivotPosition);
        quickSort(toSortArray, pivotPosition + 1, right);
    }

}

@Test
public void quickSortTest() throws Exception {
    int[] toSortArray = { 5, 1, 2, 4, 3 };
    quickSort(toSortArray, 0, toSortArray.length - 1);
    System.out.println(toSortArray);
}

private int step(int[] toSortArray, int left, int right) throws Exception {
    int currentLow = left - 1;
    int pivotFinalPosition = right;
    //we choose the last element as pivot
    int pivot = toSortArray[right];
    for (int i = left; i <= right - 1; i++) {
        if (toSortArray[i] < pivot) {
            ++currentLow;
            pivotFinalPosition = currentLow;
            swap(toSortArray, i, currentLow);
        }
    }
    swap(toSortArray, ++currentLow, right);
    return pivotFinalPosition;
}

private void swap(int[] sortedSet, int i, int j) throws Exception {
    int temp = sortedSet[i];
    sortedSet[i] = sortedSet[j];
    sortedSet[j] = temp;
}

Performance Considerations for the Quick-Sort Algorithm

The time complexity of the above algorithm is O(n*log (n)) for the best and average cases. It is O(n2) for the worst case: for instance, if the original set is already ordered and we choose the pivot as the last element.

Conclusion

In this article, we have seen how to sort an array of integers with the Quick-Sort algorithm. The example code is available on GitHub.