How can I improve my quick sort algorithim (Python)
Question: After reading about the quick sort algorithim, 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)
    


Answer: This is nice code.

Compared to a quicksort version that is done in place (using only one array),
yours may be a bit slower because of the copy/concatenation.

Quicksort performances rely a lot on the choice of the pivot. By choosing the
first element, there are some cases where your code runs in quadratic time,
for example while sorting an already sorted array. The most known
optimizations are:

  * Choosing a better pivot, for example by applying Tukey's ninther (you avoid those worst cases almost certainly).
  * Performing an Insertion sort when the subarray is small enough (< 10 for example).

Else, there are a few variants of quicksort which run faster, like 3-way
quicksort using Bentley-McIlroy's sheme or dual-pivot quicksort (used to sort
arrays of primitive in java). The Insertion speedup is still applicable for
those.

