Trying to implement Introsort using Python.
The pseudo-code given is:
1 n ←|A|
2 if n ≤ 1
3 return
4 elseif d = 0
5 Heap-Sort(A)
6 else
7 p ← Partition(A) // Partitions A and returns pivot position
8 Intro-Sort(A[0:p],d−1)
9 Intro-Sort(A[p+1:n],d−1)
My source code is:
import math
def introSort(a,d):
n = len(a)
if n <= 1:
return
elif d == 0:
heapSort(a)
else:
p = partition(a)
a1 = a[0:p]
a2 = a[p+1:n]
introSort(a1, d-1)
introSort(a2, d-1)
a = a1 + [a[p]] + a2
def heapSort (a):
END = len(a)
for k in range (math.floor(END/2) - 1, -1, -1):
heapify(a, END, k)
for k in range(END, 1, -1):
swap(a, 0, k-1)
heapify(a, k-1, 0)
def partition(a):
x = a[len(a) - 1]
i = -1
for j in range(0, len(a) - 2):
if a[j] <= x:
i = i + 1
swap(a, i, j)
swap(a, i + 1, len(a) - 1)
return i + 1
def swap(a, i, j):
tmp = a[i]
a[i] = a[j]
a[j] = tmp
def heapify(a,iEnd,iRoot):
iL = 2*iRoot + 1
iR = 2*iRoot + 2
if iR < iEnd:
if (a[iRoot] >= a[iL] and a[iRoot] >= a[iR]):
return
else:
if(a[iL] > a[iR]):
j = iL
else:
j = iR
swap(a, iRoot, j)
heapify(a, iEnd, j)
elif iL < iEnd:
if (a[iRoot] >= a[iL]):
return
else:
swap(a, iRoot, iL)
heapify(a,iEnd,iL)
else:
return
a = [3,5,6,1,23,521,6243,632,123,53,62,421,15,672,7,435,21]
introSort(a,2)
print(a)
The result given was wrong:
>python introsort.py
[3, 5, 6, 1, 15, 7, 21, 632, 123, 53, 62, 421, 23, 672, 521, 435, 6243]
It seems that it stopped straight after partition and the sorting on sublists was not working. It was clear that 21 was the pivot and the partition worked perfectly.
Can anybody point out my mistake? Thank you very much!
I actually fixed this by using a helper function that calls heapsort on a piece of the list. Instead of doing it by modify the heapsort function, I did this in a separate copy and update the sorted elements back in the original list. The code shown as:
It worked fine by testing with:
Giving: