Englishlearner101 - 1 year ago 56

Python Question

Recently I was trying to implement the quicksort algorithm in Python, and I couldn't make it work properly. Even though the program sorts the sub-arrays, it's not being reflected on the main list. I'm new to programming, so can anyone help me to understand what part or concept I didn't do right?

`def swap(arr, right, left):`

temp = arr[right]

arr[right] = arr[left]

arr[left] = temp

def split_array(arr, right):

left_half = arr[:right]

right_half = arr[right:]

a = (left_half, right_half)

return a

def quick_sort(arr):

if len(arr) >= 2:

pivot = 0

left_mark = pivot + 1

right_mark = len(arr) - 1

stop = True

while stop:

while arr[pivot] > arr[left_mark] and left_mark < right_mark:

left_mark += 1

while arr[pivot] < arr[right_mark] and left_mark < right_mark:

right_mark -= 1

if left_mark < right_mark:

swap(arr, right_mark, left_mark)

right_mark -= 1

left_mark += 1

else:

if arr[pivot] > arr[right_mark]:

swap(arr, right_mark, pivot)

stop = False

left, right = split_array(arr, right_mark)

quick_sort(left)

quick_sort(right)

return arr

array = [8, 6, 1, 7, 0, 5, 4, 3, 2, 1]

print(quick_sort(array))

Answer Source

Change this:

```
left, right = split_array(arr, right_mark)
quick_sort(left)
quick_sort(right)
```

to this:

```
left, right = split_array(arr, right_mark)
arr = quick_sort(left) + quick_sort(right)
```

Quicksort is typically implemented "in-place" to avoid copying arrays around. Your implementation creates a full copy of the array at each step instead and returns it, so you need to reassemble the pieces yourself.

**UPDATE**

A small change to make your algorithm in-place instead:

```
def quick_sort(arr, start=0, end=None):
if end is None: end = len(arr)-1
if end > start:
pivot = start
left_mark = start + 1
right_mark = end
stop = True
while stop:
while arr[pivot] > arr[left_mark] and left_mark < right_mark:
left_mark += 1
while arr[pivot] < arr[right_mark] and left_mark < right_mark:
right_mark -= 1
if left_mark < right_mark:
swap(arr, right_mark, left_mark)
right_mark -= 1
left_mark += 1
else:
if arr[pivot] > arr[right_mark]:
swap(arr, right_mark, pivot)
stop = False
quick_sort(arr, start, right_mark - 1)
quick_sort(arr, right_mark, end)
array = [8, 6, 1, 7, 0, 5, 4, 3, 2, 1]
quick_sort(array) # in-place
print(array) # now sorted
```

IMO, the following is clearer and more closely matches the typical description of the algorithm:

```
def quick_sort(arr, start=0, end=None):
if end is None:
end = len(arr) - 1
if end <= start:
return
pivot = arr[start]
left_mark = start - 1
right_mark = end + 1
while left_mark < right_mark:
left_mark += 1
while arr[left_mark] < pivot:
left_mark += 1
right_mark -= 1
while arr[right_mark] > pivot:
right_mark -= 1
if left_mark < right_mark:
arr[left_mark], arr[right_mark] = arr[right_mark], arr[left_mark]
quick_sort(arr, start, right_mark)
quick_sort(arr, right_mark + 1, end)
```