0
$\begingroup$

Its well known that Lomuto's partitioning algorithm results in too many unnecessary swaps. Can we modify the algorithm in this way:

  1. Initialize a pointer a that points to the first position in the array, and initialize b to a.
  2. While the element at b is lesser than the pivot, Move B by 1.
  3. Set a = b.
  4. WHILE b doesn't reach the end of the array DO till STEP 7:
  5. IF element at b is greater than pivot, move b one step from left to right
  6. IF an element lesser than the pivot is found, swap the elements at b and a
  7. Increment a by 1 and b by 1.
  8. END.

I think this algorithm swaps only when necessary, unlike Lomuto's algorithm which swaps too many times, often needlessly. The time complexity should also be equivalent to Lomuto's algorithm, in both average as well as the worst-cases.

Does this algorithm correctly partition the array into elements less then the pivot and elements greater than the pivot? Does this algorithm use fewer swaps than Lomuto's algorithm?

$\endgroup$
  • 1
    $\begingroup$ Did you, for example, try to prove that your version of the algorithm works? $\endgroup$ – David Richerby Mar 27 '17 at 9:46
  • $\begingroup$ I've performed some sample executions on paper to convince myself that it does work. $\endgroup$ – Abhishek Mar 27 '17 at 9:48
  • 1
    $\begingroup$ Do you have a specific question about your pseudocode? (Also, it's not clear to me what is meant by an "unnecessary swap".) $\endgroup$ – D.W. Mar 27 '17 at 17:45
  • $\begingroup$ D.W. I basically requested a peer review with regards to the reduction in the number of swaps and time complexity compared to Lomuto's algorithm. I think Lomuto's algorithm does many swaps which may not be needed, and which this algorithm seems to address. $\endgroup$ – Abhishek Mar 28 '17 at 4:30
  • 1
    $\begingroup$ This platform does not work well for peer review. It's designed for questions. Also, since I don't see even an attempt at an analysis, I have no reason take your approach seriously. Sorry, but that's just a heuristic to save me time: Quicksort has been studied for half a century, the chances that you have discovered something new and "better" are very slim (but greater than 0). $\endgroup$ – Raphael Mar 29 '17 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.