Introsort in Python, can anybody point out my mistake?

Question

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!

`a = a1 + [a[p]] + a2` isn't going to do anything to the input list. That's just rebinding a local variable. — user2357112, Feb 04 '18 at 23:51
How to fix this? I tried to use introSort(a[0:p],d-1) and so on, it didn't work — Z. Yan, Feb 04 '18 at 23:59
Your partition function is definitely wrong. Try putting a print statement in the inner loop and running just the partition function to look closely at what it's doing. — Turksarama, Feb 05 '18 at 00:13
put `print "before end a=",a` after `a = a1 + [a[p]] + a2` and set `1` in `introSort(b,2)` . You'll get `before end a= [1, 3, 5, 6, 7, 15, 21, 23, 53, 62, 123, 421, 435, 521, 632, 672, 6243] [3, 5, 6, 1, 15, 7, 21, 632, 123, 53, 62, 421, 23, 672, 521, 435, 6243] `. It doesn't change final array — TigerTV.ru, Feb 05 '18 at 05:29
@Z.Yan: you can fix it by `a.insert(index, value)` and `a.pop(index+1)` — TigerTV.ru, Feb 05 '18 at 06:48
Thank you very much but it failed when using the list given above, it changed 435 to 6243. I actually got idea to fix this and solved the problem. Thank you so much!!! — Z. Yan, Feb 05 '18 at 20:37
@Z.Yan: Oh, yes. It fails now, I see. In addition, the code you give fails too with error on "math.floor(END/2)" — TigerTV.ru, Feb 05 '18 at 22:23

Z. Yan · Accepted Answer · 2018-02-05T22:05:22.263

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:

import math

def introSort(a, d, start, end):
    n = end - start
    if n <= 1:
        return
    elif d == 0:
        introHS(a, start, end)
    else:
        p = partition(a, start, end)
        introSort(a, d-1, start, p)
        introSort(a, d-1, p+1, end)

def introHS (a, start, end):
    b = a[start:end]
    heapSort(b)
    for i in range(0,len(b)):
        a[start+i] = b[i]

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, start, end):
    x = a[end-1]
    i = start-1
    for j in range(start, end-1):
        if a[j] <= x:
            i=i+1
            swap(a, i, j)
    swap(a, i+1, end-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

It worked fine by testing with:

a = [3,5,6,1,23,521,6243,632,123,53,62,421,15,672,7,435,21,123,41,52,6234,11,55,6345,324,58,46,2,123,152,6156,46,34,3426,5341,16,3314,34,73416,345]
print("Original:")
print(a)
for i in range(0,15):
    introSort(a,i,0,len(a))
    print("d=" + str(i))
    print(a)

Giving:

>Original:
>[3, 5, 6, 1, 23, 521, 6243, 632, 123, 53, 62, 421, 15, 672, 7, 435, 21, 123, 41, 52, 6234, 11, 55, 6345, 324, 58, 46, 2, 123, 152, 6156, 46, 34, 3426, 5341, 16, 3314, 34, 73416, 345]
>d=0
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=1
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=2
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=3
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=4
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=5
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=6
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=7
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=8
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=9
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=10
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=11
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=12
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=13
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=14
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]

Darn - maybe not because of the recursion. Gives me "compiler re-entrant to the same function signature" error — Sterling, Aug 18 '21 at 08:59

TigerTV.ru · Answer 2 · 2018-02-05T17:20:40.647

Remove

a = a1 + [a[p]] + a2

And insert

for i in range(0, len(a1)):
    a.insert(i, a1[i])
    a.pop(i+1)
for i in range(0, len(a2)-1):
    a.insert(i+p+1, a2[i])
    a.pop(i+p+2)

Full code:

#!/usr/bin/python
import math


def introSort(a,d):
    n = len(a)
    if n <= 1:
        return
    elif d == 0:
        heapSort(a)
    else:
        p = partition(a)
        a1 = a[:p]
        a2 = a[p+1:n]
        introSort(a1, d-1)
        introSort(a2, d-1)
        for i in range(0, len(a1)):
            a.insert(i, a1[i])
            a.pop(i+1)
        for i in range(0, len(a2)-1):
            a.insert(i+p+1, a2[i])
            a.pop(i+p+2)

def heapSort (a):
    END = len(a)
    for k in range ( int(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):
    hi = len(a)-1
    x = a[hi]
    i = 0
    for j in range(0, hi-1):
        if a[j] <= x:
            swap(a, i, j)
            i = i + 1
    swap(a, i, hi)
    return i

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]
print(a)

introSort(a,2)

print(a)

Also, see an answer about references in Python https://stackoverflow.com/a/986145/9210255

Introsort in Python, can anybody point out my mistake?

2 Answers2