-6

enter image description hereI have been trying to analyse the operation of Quicksort for the above input. But i dont know what to do when i encounter 2 equal elements while traversing the list. Could somebody help me with trace as how quick sort works for above input? FIRST ELEMENT SHOULD BE PIVOT

Pradeep Kumar
  • 471
  • 2
  • 6
  • 14
  • do the same thing with them? i.e. move them to the same partition – meowgoesthedog Jul 19 '17 at 11:57
  • I could not trace the quicksort operation for this. Every time try , i get it wrong.Kindly help. – Pradeep Kumar Jul 19 '17 at 11:59
  • Do you already have some code we can take a look at? If yes, please post it. Where exactly is the problem? Can you be a bit more precise please? For example show us the process until the point where you stuck. – Zabuzard Jul 19 '17 at 12:00
  • there are 2 R's in this list. when variable i points to R and so does j , i dont know whether to exchange or not . By tracing i mean the way it is shown in anany levitin textbook. when i try to trace the algorithm for given input im not able to get it right. – Pradeep Kumar Jul 19 '17 at 12:44
  • @PradeepKumar If you're pivoting around `R`, and there is another `R` in the partitions on either side, then you can put the non-pivot `R` in either partition. – hnefatl Jul 19 '17 at 12:52
  • Possible duplicate of [Understanding quicksort](https://stackoverflow.com/questions/39665299/understanding-quicksort) – hnefatl Jul 19 '17 at 13:56

1 Answers1

1

Using ^ below a letter to indicate it's a pivot, and * to indicate it's already been pivoted. If a partition has odd length, I pick the "rounded down middle" (partition length 4 would have the 2nd item as pivot).

Note how in the 4th line, there are two R's, with one of them being the pivot. In cases like this, the duplicate (the other R) can go on either side.

Edit: when comparing two letters, you need to sort them based on their position in the alphabet. If you "sort" based on their relative positions, you're never going to move any elements so naturally you'll never sort the list.

Edit #2: The algorithm I'm using is, unsurprisingly, quicksort.

MERGESORT -> EEMRGSORT
    ^         ^

EEMRGSORT -> EEMRGORST
^*   ^       ^*     ^

EEMRGORST -> EEGMRORST
**  ^  *^    **^    **

EEGMRORST -> EEGMORRST
*** ^  **    ***  ^ **

EEGMORRST -> EEGMORRST
***^ *^**    ***^ *^**

EEGMORRST -> EEGMORRST
****^****    ****^****

EEGMORRST -> Complete
*********

If I've made a mistake, please correct me.

hnefatl
  • 5,860
  • 2
  • 27
  • 49
  • could you please show me the trace for FIRST ELEMENT AS PIVOT. i had mentioned it earlier but my question was edited out – Pradeep Kumar Jul 19 '17 at 13:08
  • @PradeepKumar No. It took me long enough to do this example, which highlights all the edge cases I can think of. If you can't extrapolate out from this trace where you're going wrong, then I can't help you. – hnefatl Jul 19 '17 at 13:13
  • Im sorry. i dint understand the first line itself as to how got EEMRGSORT. – Pradeep Kumar Jul 19 '17 at 13:26
  • @PradeepKumar Having selected `E` as the pivot (as it's in the middle, so for you you'd pick `M`), iterate over every other character in the partition that you picked the pivot from (here the entire string), and if an item is less than the pivot place it on the left, otherwise place it on the right. So `M`>`E`, so we move `M` to the right of `E`. Then `E` = `E`, so we leave it. `R`>`E`, so we move `R` to the right of `E`. – hnefatl Jul 19 '17 at 13:33
  • Plz forgive me , im unable to follow u.I tried like u. taking middle E as pivot. M E R G are all less than E, so they will remain on left. S O R T are all greater than E. so they will remain right. No exchanges takes place. Howd u get EEMRGSORT? – Pradeep Kumar Jul 19 '17 at 13:37
  • @PradeepKumar No, all of MRGSORT come **later in the alphabet** than E. They're greater in that sense. – hnefatl Jul 19 '17 at 13:39
  • Could u plz tell which algorithm you are using.could u give me the algorithm snippet. – Pradeep Kumar Jul 19 '17 at 13:45
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/149613/discussion-between-pradeep-kumar-and-hnefatl). – Pradeep Kumar Jul 19 '17 at 13:46
  • Thanks a lot. U made me understand it easily.+1. Thank u – Pradeep Kumar Jul 20 '17 at 04:39