## 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.