CODEWITHSUNDEEP
pythonquicksortinsertion-sort
Bob Tan
Bob Tan

Reputation: 103

Error implementing insertion sort into quicksort

I am currently facing an issue implementing insertion sort into quicksort. I am making it such that when the sublist is smaller than a certain value, insertion sort is called on the sublist instead of quicksort. I have managed to make it work by passing in the full list along with the indexes of the sublists, but when I try it by passing the sublist as a slice of the main list, it does not work.

Code that works (passing in the indexes of the sublist)

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if (last - first +1) < 5:
       insertionSort(alist, first, last)
   else:
       splitpoint = partition(alist,first,last)
       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
   pivotvalue = alist[first]
   leftmark = first+1
   rightmark = last
   done = False
   while not done:
       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1
       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1
       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp
   return rightmark

def insertionSort(alist, first, last):
   for index in range(1,last +1):
     currentvalue = alist[index]
     position = index
     while position>0 and alist[position-1]>currentvalue:
         alist[position]=alist[position-1]
         position = position-1
     alist[position]=currentvalue


alist = [54,26,93,17,77,31,44,55,20,1,3,5]
quickSort(alist)

print(alist)

Code that doesnt work (passing the sublist in as a slice of the main list)

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if (last - first +1) < 5:
       insertionSort(alist[first:last +1])
   else:
       splitpoint = partition(alist,first,last)
       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
   pivotvalue = alist[first]
   leftmark = first+1
   rightmark = last
   done = False
   while not done:
       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1
       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1
       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp
   return rightmark

def insertionSort(alist):
   for index in range(1, len(alist)):
     currentvalue = alist[index]
     position = index
     while position>0 and alist[position-1]>currentvalue:
         alist[position]=alist[position-1]
         position = position-1
     alist[position]=currentvalue


alist = [54,26,93,17,77,31,44,55,20,1,3,5]
quickSort(alist)

print(alist)

I have tried debugging it, basically what happens is once insertion sort is done with sorting the subarray and it returns to the previous recursive function, the array goes back to its previous 'unsorted' self. Would greatly appreciate any advice, thank you everyone.

Upvotes: 0

Views: 231

Answers (2)

Tzane
Tzane

Reputation: 3462

Building on what was said in https://stackoverflow.com/a/68662714/14536215 you need return the sorted list from insertionSort and assign the the sorted values in your original list. You can use the same slicing for assigning you used in the function call:

alist[first:last +1] = insertionSort(alist[first:last +1])

Upvotes: 1

enzo
enzo

Reputation: 11496

In your first snippet, when you call

insertionSort(alist, first, last)

and then use

for index in range(1, last+1):

  1. you're iterating last times.

  2. you're operating on the original alist (any changes will reflect on alist).

In your second snippet, when you call

insertionSort(alist[first:last +1])

and then use

for index in range(1, len(alist)):
  1. you're iterating last - first + 1 times.
  2. you're operating on the (sliced) copy of the original alist (any changes will not reflect on alist).

Upvotes: 2

Related Questions