Hoare partition scheme in Python

Question

I translated the Hoare partition scheme from a Wikipedia article to Python:

Here's my code:

def partition(nums, low, high):
  pivot = nums[(high + low) // 2]
  i = low - 1
  j = high + 1

  while True:
    i += 1
    j -= 1

    while nums[i] < pivot:
      i += 1
    while nums[j] > pivot:
      j -= 1

    if i >= j:
      return j

    nums[i], nums[j] = nums[j], nums[i]    


nums = [14801, 338, 6389, 3209, 4825, 10818, 1768, 7669, 4545, 10930, 11810]
pivot_1 = partition(nums, 0, len(nums) - 1)
print(pivot_1)  # 6 ---> this should be 7, no?
print(nums)  # [4545, 338, 6389, 3209, 4825, 7669, 1768, 10818, 14801, 10930, 11810]

pivot_2 = partition(nums, 0, 6)
print(pivot_2)  # 2 ---> this looks ok
print(nums)  # [1768, 338, 3209, 6389, 4825, 7669, 4545, 10818, 14801, 10930, 11810]

What am I doing wrong? Why is my code not returning the correct pivot location?

Your Python while loops test and if false don’t execute the increment/decrement, where the wikipedian equivalent seem to always increment/decrement before doing the test? — DisappointedByUnaccountableMod
– DisappointedByUnaccountableMod, Commented Sep 20, 2020 at 18:45
@barny The OP also always increments/decrements before the test. — Kelly Bundy
– Kelly Bundy, Commented Sep 20, 2020 at 19:07
Well yes but that’s a) the same as the wikipedian and b) before either while loop, E.g. while nums[i]<pivot: will not execute the contained increment if the test is false, whereas the wikipedian will increment i before testing — DisappointedByUnaccountableMod
– DisappointedByUnaccountableMod, Commented Sep 20, 2020 at 19:31

Kelly Bundy · Accepted Answer · 2020-09-20 19:25:55Z

1

this should be 7, no?

No.

As the paragraph above the code at Wikipedia says:

the pivot's final location is not necessarily at the index that is returned

You misunderstood the meaning of the returned index. It's just the partition border which you can then use for the recursive quicksorts.

edited Sep 20, 2020 at 19:25

answered Sep 20, 2020 at 19:20

Kelly Bundy

28k7 gold badges34 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

csirmazbendeguz Over a year ago

Oh man... I've spent hours debugging my code and thinking about why it's not working. I thought this partitioning algorithm was interchangeable with the other one

Kousik Mandal · Accepted Answer · 2020-09-20 18:39:45Z

0

I am not familiar with python syntax, but in java I implement this as follows

private static int partition(int[] arr, int low, int high) {
        int pivot = arr[(low+high)/2];
        int i = low-1, j = high+1;
        while(true) {
          do { i++; } while(arr[i] < pivot);
          do { j--; } while(arr[j] > pivot);
          if (i < j) swap(arr, i, j);
          else return j;
        }

It may help you to implement same logic in python.

answered Sep 20, 2020 at 18:39

Kousik Mandal

7301 gold badge6 silver badges17 bronze badges

1 Comment

csirmazbendeguz Over a year ago

Your implementation returns an incorrect result for the input mentioned in the original question as well.

Collectives™ on Stack Overflow

Hoare partition scheme in Python

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related