0
$\begingroup$

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 array are unsorted and we should complete step3 with recursion method to solve this and this is my question .

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 .

enter image description here

but can you explian this for me ?

$\endgroup$
1
  • $\begingroup$ Its just a simple recursion. Call quicksort on both sub arrays $\endgroup$
    – nir shahar
    Jun 15, 2021 at 12:25

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you so much . can you take a look at this top picture ? i can't undrestand it . in your example we just normally divide the elements between p.p yes ? $\endgroup$
    – jasmine
    Jun 15, 2021 at 14:02
  • $\begingroup$ @jasmine The top picture seems utterly irrelevant to Quicksort; it appears to portray the Bubble Sort algorithm. $\endgroup$
    – kviiri
    Jun 15, 2021 at 20:21
  • $\begingroup$ Yes i think so . Thank you , i really learned it because of your help . $\endgroup$
    – jasmine
    Jun 16, 2021 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.