How to arrange a sub-array for Quick sorting algorithm?

Question

Alghorithm : Quick sort .

idea : devide and conqure .

steps : 1- find the pivot point from array like first element . 2- partiotioning the array so that elements are smaller than pivot point are in the left side and ones are bigger in the right side . 3- sorting both sub arrays (recursion)

Question : i know all of the steps but i don't know how to sorting sub arrays in step 3 . i can't find any example that explains this ending part .

Example :

if you look at this you see that both sub arrays are unsorted and we should complete steps with recursion method to solve this and this is my question .

but can you explian this for me ?

Answer 1

The conceptually simplest way is to simply use the same algorithm recursively to sort the sub arrays; hence why it's labeled as recursion. As long as the base cases for very small arrays are correctly defined, this will yield a correct result.

As an example, let's Quicksort some alphabet, using first symbol as pivot:

sort(FHDEBACG) -> sort(DEBAC) F sort(HG)

Then, we recursively sort DEBAC and HG. I'll demonstrate with the former:

sort(DEBAC) -> sort(BAC) D sort(E) -> sort(BAC) D E
sort(BAC)   -> sort(A) B sort (C) -> A B C

thereby getting the desired result:

sort(DEBAC) -> A B C D E

In practice, Quicksort implementations are often modified to sort small enough (sub-)arrays with Insertion Sort, which usually exhibits superior performance for sufficiently small input arrays. Arrays and sub-arrays larger than this are sorted, as above, usually by recursively applying the same algorithm.