CODEWITHSUNDEEP
algorithmsortingquicksorttheory
Weaver
Weaver

Reputation: 174

I get a different quicksort results from the solution

The problem is to quicksort the word ELECTRONIC. I am working through every line manually, and the solution given is stepped. After the first step I have a different state from the solution and don't understand why.

I choose the pivot from the median of ETC (positions 0,4 and 9) and select E. This pivot is swapped with the last position, 9, and gives: 

0123456789
CLECTRONIE

I increment i from C on the left and decrement j from I on the right and eventually swap positions 1(L) and 4(C) giving

0123456789
CCELTRONIE

Continuing to increment and decrement i and j respectively, the eventually cross with i at position 3, L, and this is swapped with the pivot at position 9 giving:

0123456789
CCEETRONIL

Now with the pivot at position 3 I thought the partition would be

CCE |E| TRONIL

but the solution I have states:

Quicksort ELECTRONIC
choose pivot: median(E,T,C)=E
partition using E: ECC|E|LTRONI
...

I understand the letters in Sl and Sr are the same, but I think the order is important. Can anyone identify where I have gone wrong, or how the solution gets this state please? Anything is appreciated.

Upvotes: 0

Views: 54

Answers (1)

MBo
MBo

Reputation: 80187

Your partition achieves the main goal - left part contains lesser (or equal) elements, right part contains greater elements. Partition is finished. Task (for current stage) is completed successfully.

Order of elements in these parts depends on partition implementation (there are different schemes) and does not influence on sorting correctness and speed.

Upvotes: 2

Related Questions