Kalyan Chavali - 8 months ago 75

Python Question

I've been trying to run the quicksort with a switch to insertion sort when the sub array size is less than 10. So it turns out, i'm not getting a sorted list.

Where am i going wrong?

`import random`

import time

m = 0

def quicksort(numList, first, last):

if first<last:

sizeArr = last - first + 1

if(sizeArr < m):

insert_sort(numList, first, last)

else:

mid = partition(numList, first, last)

quicksort(numList, first, mid-1)

quicksort(numList, mid + 1, last)

def partition(numList, first, last):

piv = numList[last]

i = first-1

for j in range(first,last):

if numList[j] < piv:

i += 1

temp = numList[i]

numList[i] = numList[j]

numList[j] = temp

tempo = numList[i+1]

numList[i+1] = numList[last]

numList[last] = tempo

return i+1

def insert_sort(numList, first, last):

for x in range(first, last):

key = numList[x]

y = x-1

while y > -1 and numList[y]> key:

numList[y+1] = numList[y]

y = y-1

numList[y+1] = key

if __name__ == '__main__':

start = time.time()

numList = random.sample(range(5000), 100)

m = 10

quicksort(numList, 0, len(numList) - 1)

print numList

print "Time taken: " + str(time.time() - start)

input is some random array of sizes between 100 - 1000000. I'm using a random generator as you can see.

Please help me.

Answer

You have an off-by-one error in `insert_sort`

function. Iterate over `range(first, last+1)`

and it will sort correctly.

Source (Stackoverflow)