Quick Sort is not returning expected results - Python3

Question

I have been working on a quick sort algorithm which specifically sets a wall to the left, current element just to the right of the wall and the pivot at the end of the data set. The sort will compare the current element with the pivot and increment the current element each time it is greater than the pivot. When it is smaller or equal to the pivot it should swap the current element with the item to the right of the wall and move the wall one place to the right.

Here is my code:

def QuickSort(dataset, low, high):
    if (low >= high):
        return dataset
    else:
        #Set pivot to last element
        pivot = high
        #Set wall at first element
        wall = low
        #Loop through list - if current element is less or equal
        #to the pivot, swap current element with element right of wall
        #and move wall on.
        for i in range(high):
            if (dataset[i] <= pivot):
                temp = dataset[wall]
                dataset[wall] = dataset[i]
                dataset[i] = temp
                wall = wall + 1
                if wall >= high:
                    break

        #recursively call for subsequent part of list
        QuickSort(dataset, low, wall-1)
        QuickSort(dataset, wall, high)

dataset = [1,6,2,3,6,7,4,2,5]
dataset_length = len(dataset)
sorted_data = QuickSort(dataset, 0, dataset_length)
print(sorted_data)

input()

When running the code, the dataset is not returned and I can't quite see where I have gone wrong. Thank you for your help.

If your else block executes, your function will not hit a return statement, so it will return None. Possibly you mean to have return dataset at the end. — khelwood
– khelwood, Commented Apr 28, 2016 at 9:50
swapping variables with a temp is so c way of doing it. In python, you want to do dataset[i], dataset[wall] = dataset[wall], dataset[i] — MohitC
– MohitC, Commented Apr 28, 2016 at 9:58

letmutx · Accepted Answer · 2016-04-28 09:57:43Z

3

pivot = high

This doesn't set the pivot to the last element in the list. Instead, it sets the pivot to the length of the data set which is 9. So changing it to dataset[high - 1] works.

Also, the range in which you need to search for an element which is greater than pivot or less than pivot is not range(high), it is range(low, high) because when you go deeper into recursion, the size of the list changes and also its starting and ending indices.

def QuickSort(dataset, low, high):
    if (low >= high):
        return
    #Set pivot to last element
    pivot = dataset[high - 1]
    #Set wall at first element
    wall = low
    #Loop through list - if current element is less or equal
    #to the pivot, swap current element with element right of wall
    #and move wall on.
    for i in range(low, high):
        if (dataset[i] <= pivot):
            temp = dataset[wall]
            dataset[wall] = dataset[i]
            dataset[i] = temp
            wall = wall + 1
            if wall >= high:
                break
         #recursively call for subsequent part of list
    QuickSort(dataset, low, wall - 1)
    QuickSort(dataset, wall, high)

dataset = [1,6,2,3,6,7,4,2,5]
dataset_length = len(dataset)
QuickSort(dataset, 0, dataset_length)
print(dataset)

edited Apr 28, 2016 at 9:57

answered Apr 28, 2016 at 9:53

letmutx

1,41612 silver badges22 bronze badges

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

3 Comments

dahui Over a year ago

Did you also change the for statement? Might want to point that out in your answer

sw123456 Over a year ago

Fantastic! Thank you. Can I just ask, why will storing the returned dataset in a variable attached to the initial function call (ie result = QuickSort(dataset, 0, dataset_length)) result in a boolean value and not the list itself?

letmutx Over a year ago

@sw123456 Your function doesn't return anything. So None is returned. Also, None is not boolean.

Collectives™ on Stack Overflow

Quick Sort is not returning expected results - Python3

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related