What is quick sort technique? Using quick sort arrange the following elements in ascending order: 26, 5, 37, 3, 61, 11, 59, 15, 48, 19

Quick Sort Technique

Quick sort is a highly efficient sorting algorithm and is based on the divide and conquer approach. It divides the original array into smaller ones (but doesn't create new arrays as in merge sort), and then sorts the smaller arrays. The steps are:

1. Choose a Pivot: Select an element from the array as the pivot. The choice of pivot can be the first element, the last element, the median, or a random element.
2. Partitioning: Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it. After this partitioning, the pivot is in its final position.
3. Recursively Apply: Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

The base case of the recursion is arrays of size zero or one, which are always sorted.

The efficiency of the algorithm depends on the pivot selection. The worst-case time complexity is O(n^2), but with good pivot selection, the average-case complexity is O(n log n).

Quick Sort Example

Let's sort the given array using the quick sort algorithm:

26, 5, 37, 3, 61, 11, 59, 15, 48, 19

We will use the last element as the pivot for simplicity.

Step 1: Choose a Pivot

We choose 19 as the pivot.

Step 2: Partitioning

We will reorder the array so that all elements less than 19 are placed before it, and all elements greater than 19 are placed after it.

We start with two pointers: one at the start (left) and one before the pivot (right).

26, 5, 37, 3, 61, 11, 59, 15, 48, [19]

We move left to the right until we find an element greater than or equal to the pivot and move right to the left until we find an element less than the pivot, and then we swap these elements. We repeat this process until left and right pointers meet.

After partitioning, the array looks like this:

15, 5, 3, 11, 19, 26, 59, 37, 48, 61

Now, 19 is in its correct position.

Step 3: Recursively Apply

We now apply quick sort to the sub-arrays on either side of 19.

Left sub-array: 15, 5, 3, 11 Right sub-array: 26, 59, 37, 48, 61

We repeat the process for both sub-arrays.

Left Sub-array:

Choose pivot: 11 Partitioning: 5, 3, 11, 15 Recursively apply to 5, 3 and 15

Right Sub-array:

Choose pivot: 61 Partitioning: 26, 59, 37, 48, 61 Recursively apply to 26, 59, 37, 48 and no elements after 61

This process continues until all sub-arrays are sorted. The final sorted array will be:

3, 5, 11, 15, 19, 26, 37, 48, 59, 61

Detailed Steps

Here's a step-by-step breakdown of the entire process:

Step	Pivot	Array State	Sub-arrays to Sort Next
1	19	15, 5, 3, 11, 19, 26, 59, 37, 48, 61	15, 5, 3, 11 and 26, 59, 37, 48, 61
2	11	5, 3, 11, 15	5, 3 and 15 (Left sub-array)
3	61	26, 59, 37, 48, 61	26, 59, 37, 48 (Right sub-array)
4	3	3, 5	3 (Left sub-array)
5	48	26, 37, 48, 59	26, 37 and 59 (Right sub-array)
6	37	26, 37	26 (Right sub-array)

After completing these steps, the array is fully sorted.

Conclusion

Quick sort is a powerful sorting algorithm that, on average, performs better than other O(n^2) algorithms like bubble sort or insertion sort. However, its performance heavily depends on the choice of the pivot. In practice, variations of quick sort that choose the pivot in a more sophisticated way (such as the median of three) are used to avoid the worst-case O(n^2) performance on already sorted or nearly sorted arrays.