CODEWITHSUNDEEP
pythonquicksort
SmashSquadd
SmashSquadd

Reputation: 11

Why does my Quicksort program not sort items correctly?

My quicksort program is changing the order of the items in the list in the right direction, but it does not fully sort them.

def quick_sort(arr, low, high):
    if (low < high):
        pi = pivot(arr, low, high)
        pivot(arr, low, pi-1)
        pivot(arr, pi+1, high)

def pivot(arr, low, high):
    i = ( low-1 )         
    pivot = arr[high]      

    for j in range(low , high): 

        if   arr[j] <= pivot: 

            i += 1
            arr[i],arr[j] = arr[j],arr[i] 


    arr[i+1], arr[high] = arr[high], arr[i+1] 
    return ( i + 1 ) 
print (numbers)
quick_sort(numbers, 0, len(numbers)-1)
print (numbers)

I expected the results to be correctly sorted instead of partially sorted.

ex. [-9859, -8554, -9846, -9558, -9153, -9483, -7946, -8255, -9743, -8330, -7632, -7513, -7125, 1756, -5176, -441, -3385, 896, -4748, 3811, 4285, -5883, -4342, 6275, 5753, 585, -2491, -243, -3590, -4377, 5986, -3393, -3727, 2976, -1532, -3924, 53, -2461, -5882, -1022, 2881, -3586, -3191, 6153, -4970, -5602, -5944, 5528, -3281, 1515, -680, -1975, -2472, -4371, -2574, -5248, -773, -271, -1967, 5079, 3040, -5871, 4825, 2810, -2301, 1371, 315, 2911, 2669, 2477, -3205, -2350, 2402, 5217, 6205, 2593, 4595, -4340, 6654, 7783, 9653, 8331, 8092, 6869, 7556, 9719, 8555, 9430, 8137, 9057, 8124, 7662, 6991, 6928, 7728, 7849, 7955, 7696, 7775]

Upvotes: 0

Views: 54

Answers (1)

Blckknght
Blckknght

Reputation: 104712

I've not looked in detail into your implementation of pivot (so there may be additional issues), but the top-level function quick_sort has one obvous problem. You're calling pivot three times from it, but you should instead be calling it only once, and recursively calling quick_sort the other two times.

Try:

def quick_sort(arr, low, high):
    if (low < high):
        pi = pivot(arr, low, high)
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)

The recursion is important, because it sorts on successively smaller and smaller intervals. Your current code effectively sorts items into four buckets, but within those buckets, the values will be in a random order.

Upvotes: 1

Related Questions