After reading about the quick sort algorithm, I decided to write my own implementation before looking at any code. The code below is what I came up with. Upon comparing my code with other implementations I have observed that rather than returning the sorted array from the quick sort function, other implementations tend to take advantage of a list's mutability and simply run the function on the unsorted array, which in turn will sort the array without having to reference the function call. I am curious about the space time comparison with my code and the code from the book I am using, which I have provided below. I am assuming that in terms of time the algorithims perform rather similarly, maybe the concatenation operation I am performing has a negative impact? In terms of space, since I am not modifying the input array directly, I am assuming that I am creating/ returning a new array which is obviously inefficient, and important because the main advantage of quick sort over merge sort is the saved space. Overall I am just looking for some additional insight and any way to improve my algorithm's efficiency.
My code:
from random import randint
def quick(arr):
if len(arr) == 1:
return arr
else:
pivot = arr[0]
R = len(arr)-1
L = 1
while L <= len(arr)-1 and R >= 1:
if R == L:
if arr[0] > arr[R]:
arr[0], arr[R] = arr[R], arr[0]
break
if arr[R] >= pivot:
R = R - 1
continue
if arr[L] <= pivot:
L = L + 1
continue
arr[L], arr[R] = arr[R], arr[L]
return quick(arr[:R]) + quick(arr[R:])
print quick([randint(0,1000) for i in range(1000)])
The book I am using, Problem Solving With Algorithms and Data Structures Using Python By Brad Miller and David Ranum, provides this quick sort code:
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
# alist = [54,26,93,17,77,31,44,55,20]
# quickSort(alist)
# print(alist)
