Python: setting recursion limit slows sorting program

Question

I'm doing a program, that compares different sorting algorithms: insertion sort, bubble sort and quick sort. When the input is a list of at least 1000 elements, the program throws an error.

  File "/Users/karol/PycharmProjects/Algorytmy6/main.py", line 52, in quickSort
return quickSort(less) + equal + quickSort(greater)
  [Previous line repeated 995 more times]
  File "/Users/karol/PycharmProjects/Algorytmy6/main.py", line 43, in quickSort
    if len(list) > 1:
RecursionError: maximum recursion depth exceeded while calling a Python object

I tried to set recursion limit by sys.setrecursionlimit(sizeOfList+1), but it dramatically slows the quick sort algorithm. For example for 10 000 elements in list, quick sort is slower than insertion sort:

Insertion sorting a list of 10000 elements took: 3.238

Bubble sorting a list of 10000 elements took: 5.618 s

Quick sorting a list of 10000 elements took: 4.239 s

Moreover, if I run only quickSort algorithm without insertionSort and bubbleSort, then it works fine. And it is as fast as it should be:

Quick sorting a list of 10000 elements took: 0.077 s

I need the real quickSort time, because the program was made to compare it with other sorting algorithms.

Here is my code:

import random, time

def insertionSort(list):
    startTime = time.time()
    for i in range(len(list)):
        min = list[i]
        for j in range(i, len(list)):
            if list[j] <= min:
                min = list[j]
                index = j
        list[index] = list[i]
        list[i] = min

    elapsedTime = round(time.time() - startTime, 3)
    print("Insertion sorting a list of {} elements took: {} s".format(len(list), elapsedTime))

    return list

def bubbleSort(list):
    startTime = time.time()
    n = len(list) - 1
    for j in range(len(list)):
        for i in range(n-j):
            if list[i] > list[i+1]:
                temp = list[i]
                list[i] = list[i+1]
                list[i+1] = temp


    elapsedTime = round(time.time() - startTime, 3)
    print("Bubble sorting a list of {} elements took: {} s".format(len(list), elapsedTime))

    return list

def quickSort(list):

    less = []
    equal = []
    greater = []

    if len(list) > 1:
        pivot = list[0]
        for x in list:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)
        return quickSort(less) + equal + quickSort(greater)
    else:
        return list


size = 10000
list = [0]*size

for i in range(size):
    list[i] = random.randint(1, size)

insertionSort(list)
bubbleSort(list)
startTime = time.time()
quickSort(list)
elapsedTime = round(time.time() - startTime, 3)
print("Quick sorting a list of {} elements took: {} s".format(len(list), elapsedTime))

Your pivot selection is terrible. This is what happens when your pivot selection is terrible. — user2357112 supports Monica
Quicksort is notoriously much slower on a sorted list than on a randomly shuffled list. Try to call insertionSort and bubbleSort on copies of your list instead of on the original list, so that the original list remains unsorted. Note that you should never call a list list in python, because list is the name of the whole class list; shadowing that name will cause trouble. Instead call your list myList. You can make a copy using myList[:] or list(myList); replace insertionSort(myList) with insertionSort(list(myList)) to run insertion sort on copy instead of the original. — Stef
"Moreover, if I comment insertionSort and bubbleSort, quickSort doesn't need recursion limit anymore." um, what? — juanpa.arrivillaga
@user2357112supportsMonica I changed the pivot selection for random, I didn't know that it is so important. Now the program works correctly, thanks. How do I mutate input? — kstajer

Surt Surt · Accepted Answer · 2020-12-05T21:37:14

The problem is that you sort the list in the first two sorts so its sorted already when it reaches quicksort

insertionSort(lst)
bubbleSort(lst)
quickSort(lst)

sorts the same list 3 times but it is already sorted after the first insertionSort.

You will need to copy the list sort from the original order.

import copy

lst_b = copy.deepcopy(lst)
lst_q = copy.deepcopy(lst)

insertionSort(lst)
bubbleSort(lst_b)
quickSort(lst_q)

The reason you see the problem with quickSort in your original code is that a sorted list leads to quadratic time when the list is already sorted.

Python: setting recursion limit slows sorting program

1 Answers