CODEWITHSUNDEEP
pythonquicksort
JK.song
JK.song

Reputation: 125

Why combining insert sort and quick sort get worse result?

I tried to set a cutoff to combine quick sort and insert sort which using insert sort when n(number of data to sort) is lower than cutoff. However, I found the method didn't work and even worse than before. Why and how to imporve it?

To sort 10e4 random int number, the quick sort with a cutoff(50) takes 0.6s and the method without a cutoff takes only 0.02s.

The quick sort with a cutoff(50):

def quick_sort(line, l, r):
    if r - l > 50:
        pivot = find_median(line, l, r)
        i, j = l+1, r-2
        while True:
            while line[i] < pivot:
                i += 1
            while line[j] > pivot:
                j -= 1
            if i < j:
                line[i], line[j] = line[j], line[i]
                i += 1
                j -= 1
            else:
                break
        line[i], line[r-1] = line[r-1], line[i]
        quick_sort(line, l, i-1)
        quick_sort(line, i+1, r)
    else:
        insert_sort_index(line, l, r)


def find_median(line, l, r):
    center = (l + r) / 2
    if line[l] > line[r]:
        line[l], line[r] = line[r], line[l]
    if line[l] > line[center]:
        line[l], line[center] = line[center], line[l]
    if line[center] > line[r]:
        line[center], line[r] = line[r], line[center]
    line[center], line[r-1] = line[r-1], line[center]
    return line[r-1]


def insert_sort_index(line, l, r):
    if l < r:
        for idi in range(l+1, r+1):
            data = line[idi]
            for idj in range(idi+1)[::-1]:
                if idj >= l+1 and line[idj-1] > data:
                    line[idj] = line[idj-1]
                else:
                    break
            line[idj] = data

The method without a cutoff:

def quick_sort(line, l, r):
    if r - l > 1:
        pivot = find_median(line, l, r)
        i, j = l+1, r-2
        while True:
            while line[i] < pivot:
                i += 1
            while line[j] > pivot:
                j -= 1
            if i < j:
                line[i], line[j] = line[j], line[i]
                i += 1
                j -= 1
            else:
                break
        line[i], line[r-1] = line[r-1], line[i]
        quick_sort(line, l, i-1)
        quick_sort(line, i+1, r)
    else:
        if r == l + 1:
            if line[l] > line[r]:
                line[l], line[r] = line[r], line[l]

Upvotes: 1

Views: 81

Answers (1)

Kenny Ostrom
Kenny Ostrom

Reputation: 5871

python3 implements range and other functions as iterators/generators, so it would probably be much more efficient in this application, but the python2 range function creates a complete list in memory. You use range multiple times insert_sort_index (and create another list with the [::-1] splice. You could have passed step as an argument to range for that one).

My python2 implementation seems to be optimizing for loops with range(0,x) which made it harder to demonstrate the problem, but not when (l, r) is within a larger list, as is the case with this quicksort cutoff.

I measured aprox. double speed of the insert sort, when operating on a range of a larger list, by using a while loop for idi, idj instead of range().

Upvotes: 1

Related Questions