PYTHON

quicksort algorithm in python

#Code With Redoy: https://www.facebook.com/codewithredoy/
#My python lectures: https://cutt.ly/python-full-playlist

def quick_sort(array):
    if len(array) < 2:
        return array
    else:
        #select pivot element
        pivot = array[0]
        #partitioning the main array into less and greater
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        
        #calling recursively 
        return quick_sort(less) + [pivot] + quick_sort(greater)

array = [9,8,7,6,5,4,3,2,1]
res = quick_sort(array)
print(res)

quicksort python3

 
def partition(l, r, nums):
    # Last element will be the pivot and the first element the pointer
    pivot, ptr = nums[r], l
    for i in range(l, r):
        if nums[i] <= pivot:
            # Swapping values smaller than the pivot to the front
            nums[i], nums[ptr] = nums[ptr], nums[i]
            ptr += 1
    # Finally swapping the last element with the pointer indexed number
    nums[ptr], nums[r] = nums[r], nums[ptr]
    return ptr
 
# With quicksort() function, we will be utilizing the above code to obtain the pointer
# at which the left values are all smaller than the number at pointer index and vice versa
# for the right values.
 
 
def quicksort(l, r, nums):
    if len(nums) == 1:  # Terminating Condition for recursion. VERY IMPORTANT!
        return nums
    if l < r:
        pi = partition(l, r, nums)
        quicksort(l, pi-1, nums)  # Recursively sorting the left values
        quicksort(pi+1, r, nums)  # Recursively sorting the right values
    return nums

quicksort python

"""Basic Quicksort
"""
from random import randint
def qs_basic(nums, low=0, high=None):
    if high is None:
        high = len(nums) - 1
    # Sorting
    if low < high:
        pivot = nums[randint(low, high)]
        # i finds greater than pivot, j finds smaller than pivot
        i, j = low, high
        
        # Sort the pivot
        while i <= j:
            while nums[i] < pivot:
                i += 1
            while nums[j] > pivot:
                j -= 1
                
            # Pivot still not sorted
            if i <= j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
                
        # Recursive Partition
        qs_basic(nums, low, j)
        qs_basic(nums, i, high)
    return nums # for easy testing