Apply Quicksort to the list M,E,R,G,E,S,O,R,T

by

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.

More Related Contents:

  1. Why is quicksort better than mergesort?
  2. Quicksort: Choosing the pivot
  3. Quick sort Worst case
  4. Worst case for QuickSort – when can it occur?
  5. Quicksort: Iterative or Recursive
  6. median of three values strategy
  7. Quicksort vs heapsort
  8. Quicksort superiority over Heap Sort
  9. Why is Insertion sort better than Quick sort for small list of elements?
  10. How can I pair socks from a pile efficiently?
  11. Simple calculations for working with lat/lon and km distance?
  12. Finding a single number in a list [duplicate]
  13. What’s a good algorithm to determine if an input is a perfect square? [duplicate]
  14. Bitwise and in place of modulus operator
  15. Why does Java’s Arrays.sort method use two different sorting algorithms for different types?
  16. nᵗʰ ugly number
  17. Optimal algorithm for returning top k values from an array of length N
  18. Argument for O(1) average-case complexity of heap insertion
  19. insert, delete, max in O(1)
  20. How Can I Best Guess the Encoding when the BOM (Byte Order Mark) is Missing?
  21. Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k
  22. How does Dijkstra’s Algorithm and A-Star compare?
  23. Permute all unique enumerations of a vector in R
  24. Easiest algorithm of Voronoi diagram to implement? [closed]
  25. “Rounding” colour values to the nearest of a small set of colours
  26. Color gradient algorithm
  27. Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location
  28. Compute the area of intersection between a circle and a triangle?
  29. Quadratic algorithm for 4-SUM
  30. CUDA stream compaction algorithm

Leave a Comment