quickSort algorithm on GeeksForGeeks question

Question

I have a question about the quickSort algorithm on the GeeksForGeeks website here: https://www.geeksforgeeks.org/python-program-for-quicksort/

The quickSort consists of the partition function shown on GeeksForGeeks as follows:

def partition(arr, low, high):
    i = (low-1)         # index of smaller element
    pivot = arr[high]     # pivot
  
    for j in range(low, high):
  
        # If current element is smaller than or
        # equal to pivot
        if arr[j] <= pivot:
  
            # increment index of smaller element
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]
  
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return (i+1)

I am wondering why i is set to i = low - 1.

Why can't the function be rewritten like this (Notice all the i's):

def partition(arr, low, high):
        i = low
        pivot = arr[high]
      
        for j in range(low, high):
      
            if arr[j] <= pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1

        arr[i], arr[high] = arr[high], arr[i]
        return i

Answer 1

Your implementation of quicksort works. There are multiple correct implementations of quicksort out there. My guess is that GeeksForGeeks chose this implementation, but as to why they chose it?

You'd have to ask the writer of the article.

I think your question brings up a good point, that is, algorithms can be implemented in different, but similar ways.

I quickly wrote a script to test your version of the quicksort implementation. See it below.

def partition(arr, low, high):
    i = low        # index of smaller element
    pivot = arr[high]     # pivot
  
    for j in range(low, high):
  
        # If current element is smaller than or
        # equal to pivot
        if arr[j] <= pivot:
  
            # increment index of smaller element
            arr[i], arr[j] = arr[j], arr[i]
            i = i+1
  
    arr[i], arr[high] = arr[high], arr[i]
    return i
  
  
def quickSort(arr, low, high):
    if len(arr) == 1:
        return arr
    if low < high:
  
        # pi is partitioning index, arr[p] is now
        # at right place
        pi = partition(arr, low, high)
  
        # Separately sort elements before
        # partition and after partition
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
  
  
# Driver code to test above
arr = []
for i in range(0, 10000):
    import random
    r = random.randint(-100000,100000)
    arr.append(r)
n = len(arr)
quickSort(arr, 0, n-1)
# using naive method to 
# check sorted list 
flag = 0
i = 1
while i < len(arr):
    if(arr[i] < arr[i - 1]):
        flag = 1
    i += 1
      
# printing result
if (not flag) :
    print ("Sorted")
else :
    print ("Not sorted")
    print(arr)