CODEWITHSUNDEEP
pythonalgorithmsortingquicksort
aba bab
aba bab

Reputation: 1

quick sorting using 'for' vs 'while'

'''

def swap_elements(my_list, index1, index2):
    my_list[index1], my_list[index2] = my_list[index2], my_list[index1]

def partition(my_list, start, end):

    p = end
    b= start
    for i in range(len(my_list)):
        if my_list[i] < my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
    swap_elements(my_list, b, p)
    p = b
    return p
            
def quicksort(my_list, start, end):
    if end - start < 1:
        return my_list
    else: 
        p = partition(my_list, start, end)
        partition(my_list, start, p-1)
        partition(my_list, p+1, end)
'''

When I use this code because of second function 'partition' there is a IndexError: list index out of range. However When I change the 'partition' code like this '''

def partition(my_list, start, end):
    i = start
    b = start
    p = end

    while i < p:
        if my_list[i] <= my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
        i += 1

    swap_elements(my_list, b, p)
    p = b

    return p

''' It works. I don't know the differences between for and while. Does anyone knows the answer?

Upvotes: 0

Views: 159

Answers (1)

Hossmeister
Hossmeister

Reputation: 166

It has nothing to do with the choice of the for vs. while loop, since they are functionally the same. It has everything to do with the bounds. You have written the following line for the for loop:

for i in range(len(my_list)):

whereas you have written the following lines for the while loop:

i = start
b = start
p = end

while i < p:

You can see that these lines are not the same. In the for loop, you are iterating over the length of the entire array, whereas in the while loop, you are iterating from the bounds you are given. Therefore, you should modify the range of the for loop like so:

p = end
b= start
for i in range(start, p):

Also, you should modify the quicksort method like so to ensure that it runs:

    p = partition(my_list, start, end)
    quicksort(my_list, start, p-1)
    quicksort(my_list, p+1, end)
    return my_list

Upvotes: 1

Related Questions