unable to sort array using quick sort in python-CodePudding

Currently i am writing a sorting code for array.....but due to some bugs i am unable to sort my array, could you please help to fix that bugs.

CODE

# QUICK SORT 
import math

a = [34, 1, 3, 90, 34, -1, -4,78, 6, 55, 20, -65]
a.append(math.inf)

def partition(l,h,a):
    p = l
    i = l 1
    j = h
    while i<j:
        while a[i] < a[p]:
            i  = 1
        while a[j] > a[p]:
            j -= 1
        if i<j:
            a[i],a[j] = a[j],a[i]
    a[p],a[j] = a[j],a[p]
    return j

def quick(l,h,a):
    if l<h:
        j = partition(l,h,a)
        quick(l,j,a)
        quick(j 1,h,a)

quick(0,len(a)-1,a)
print(a)

CodePudding user response：

There are a couple of things off with your code. If you want an indeepth guide for it I highly recommend the following link: https://www.geeksforgeeks.org/python-program-for-quicksort/ . the code below if an functioning version of your code.

import math

a = [34, 1, 3, 90, 34, -1, -4,78, 6, 55, 20, -65]
a.append(math.inf)

def partition(l,h,a):
    p = a[h]
    i = l - 1

    for j in range(l,h):
        if a[j] < p:
            i = i   1
            a[i],a[j] = a[j],a[i]

    a[i 1],a[h] = a[h],a[i 1]
    return i 1

def quick(l,h,a):
    if l < h:
        j = partition(l,h,a)
        quick(l,j-1,a)
        quick(j 1,h,a)

quick(0,len(a)-1,a)
print(a)

CodePudding user response：

I'm not sure where you got that algorithm, but here's one based on your code that actually works. This is the Hoare partitioning:

# QUICK SORT 
import math

a = [34, 1, 3, 90, 34, -1, -4,78, 6, 55, 20, -65]
a.append(math.inf)

def partition(l,h,a):
    p = a[(h l)//2]
    i = l-1
    j = h 1
    while True:
        i  = 1
        while a[i] < p:
            i  = 1
        j -= 1
        while a[j] > p:
            j -= 1
        if i >= j:
            return j
        a[i],a[j] = a[j],a[i]

def quick(l,h,a):
    if l<h:
        j = partition(l,h,a)
        quick(l,j,a)
        quick(j 1,h,a)

quick(0,len(a)-1,a)
print(a)

FOLLOWUP

The problem with your code is that the while loop you have to use in Python is NOT the same as the do/while loop he used in his video. You need to do the operation once BEFORE entering the while loop. This works:

# QUICK SORT 
import math

a = [34, 1, 3, 90, 34, -1, -4, 78, 6, 55, 20, -65]
a.append(math.inf)

def partition(l,h,a):
    p = a[l]
    i = l
    j = h
    while i < j:
        i  = 1
        while a[i] <= p:
            i  = 1
        j -= 1
        while a[j] > p:
            j -= 1
        if i < j:
            a[i],a[j] = a[j],a[i]
    a[l],a[j] = a[j],p
    return j

def quick(l,h,a):
    if l<h:
        j = partition(l,h,a)
        quick(l,j-1,a)
        quick(j 1,h,a)

quick(0,len(a)-1,a)
print(a)