Python while loop getting stuck during quicksort

Question

I am trying to write a quicksort function in Python using a while loop and for some reason, my loop will cause sublime to shut down if I don't increase i during EACH iteration (which is not something I want to do as index 0 of the array may change during the loop). Any ideas about why this may be happening or what is wrong with my while loop? Thanks for the help! I bet I am just being dumb somewhere.

from random import randint

def quicksort(arr):
    print(arr)
    pivot = arr[randint(0, len(arr)-1)]
    i = 0
    while i < len(arr):
        print('value', arr[i])
        print('pivot', pivot)
        if arr[i] < pivot:
            arr.append(arr[i])
            del arr[i]
        else:
            i += 1
        print(arr)
    print(arr)

arr1 = [3,86,5,75,2,58,6,4,9,7,87,2,1,6,9,90,65,5,1,890]
quicksort(arr1)

Why don't you use a for-loop. Like this: for i in range(len(arr)) — Agile_Eagle
– Agile_Eagle, Commented Aug 12, 2018 at 8:34
@Agile_Eagle Because there's a branch where the list is mutated and the index is not incremented. — Aran-Fey
– Aran-Fey, Commented Aug 12, 2018 at 8:35
A suggestion: You can replace pivot = arr[randint(0, len(arr)-1)] with random.choice(arr). — DYZ
– DYZ, Commented Aug 12, 2018 at 8:37
What happens if you pivot is 1 ? The conditions will never be True and not sorting will take place. In other scenarios you get a never ending loop and that's why probably your code stalls. . — joaquin
– joaquin, Commented Aug 12, 2018 at 8:50

DYZ · Accepted Answer · 2018-08-12 08:39:18Z

2

If the last element of the list is smaller than the pivot, your function will append it to the end and delete again forever. In fact, this is true even when all the remaining elements are smaller than the pivot.

answered Aug 12, 2018 at 8:39

DYZ

57.3k10 gold badges73 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python while loop getting stuck during quicksort

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related