CODEWITHSUNDEEP
pythonalgorithmquicksort
Connor D
Connor D

Reputation: 105

Python Quicksort algorithm is sorting incorrectly

As the title reads, I'm having encountering an error with my Python Quicksort code. My code is further below and this is the input file that I'm using to test.

5
3
8
6
7
4
9
2
1
10

In the code, the variable i is the border value and the variable j is the current value being compared to the pivot. The issue is that when Partition executes its first iteration, the value 3 in the array doesn't end up on the left side of the pivot value (5 in this case) as it should. I'm always using the leftmost index as the pivot by the way.

def Partition(input_array, left_index, right_index):
    pivot_value = input_array[left_index]

    i = left_index + 1
    for j in range(i+1, right_index):
        if input_array[j] < pivot_value:
            swap(input_array, i, j)
            i = i + 1

    swap(input_array, left_index, i - 1)
    print(input_array)
    return i - 1

def swap(input_array, i, j):
    input_array[i], input_array[j] = input_array[j], input_array[i]
    return input_array

This is the array before the first iteration of Partition:

5, 3, 8, 6, 7, 4, 9, 2, 1, 10

This is the array after the first iteration of Partition:

1, 4, 2, 5, 7, 3, 9, 8 , 6, 10

As you can see, the 3 is in the incorrect spot. Any help with this would be appreciated!

Upvotes: 1

Views: 109

Answers (1)

MBo
MBo

Reputation: 80187

When you start for j loop from i+1 index, algorithm does not discover that 3<5 and does not advance i index. Remove +1

Refer to Lomuto scheme here

Upvotes: 3

Related Questions