DSA 30: Quicksort [Part 1]

1. partition Function

def partition(arr, l, r):
    p=r
    pivot=arr[p]
    r-=1

    print(arr, l,r,pivot)
    
    while True:
        while arr[l]<pivot:
            l+=1
        while arr[r]>pivot:
            r-=1
        if l>=r:
            break
        else:
            arr[l],arr[r]=arr[r],arr[l]    
            l+=1
    arr[l],arr[p]=arr[p],arr[l]    
    print(arr)
    return l

arr = [int(char) for char in "052163"]

partition(arr,0,len(arr)-1)

[0, 5, 2, 1, 6, 3] 0 4 3
[0, 1, 2, 3, 6, 5]

3

2. quick_sort Function

• Recursive function
• Includes partition function

def quick_sort(arr, l, r):
    if r-l<=0:
        return 
    p = partition(arr, l,r)
    quick_sort(arr, l, p-1)
    quick_sort(arr, p+1, r)

arr = [int(char) for char in "052163"]
quick_sort(arr,0,len(arr)-1)

[0, 5, 2, 1, 6, 3] 0 4 3
[0, 1, 2, 3, 6, 5]
[0, 1, 2, 3, 6, 5] 0 1 2
[0, 1, 2, 3, 6, 5]
[0, 1, 2, 3, 6, 5] 0 0 1
[0, 1, 2, 3, 6, 5]
[0, 1, 2, 3, 6, 5] 4 4 5
[0, 1, 2, 3, 5, 6]

3. SortableArray Class with partition Instance Method

• Instance attribute: array

class SortableArray():
    def __init__(self,array):
        self.array=array
        
    def partition(self, l, r):
        p=r
        pivot=self.array[p]
        r-=1

        print(self.array, l,r,pivot)
        
        while True:
            while self.array[l]<pivot:
                l+=1
            while self.array[r]>pivot:
                r-=1
            if l>=r:
                break
            else:
                self.array[l],self.array[r]=self.array[r],self.array[l]    
                l+=1
        self.array[l],self.array[p]=self.array[p],self.array[l]    
        print(self.array)
        return l

3.1 Test: partition Instance Method

arr = [int(char) for char in "052163"]
my_array = SortableArray(arr)
my_array.array
my_array.partition(l=0,r=len(my_array.array)-1)
my_array.array

[0, 5, 2, 1, 6, 3] 0 4 3
[0, 1, 2, 3, 6, 5]

[0, 1, 2, 3, 6, 5]

4. SortableArray Class with quick_sort Instance Method

class SortableArray():
    def __init__(self,array):
        self.array=array
        
    def partition(self, l, r):
        p=r
        pivot=self.array[p]
        r-=1

        print(self.array, l,r,pivot)
        
        while True:
            while self.array[l]<pivot:
                l+=1
            while self.array[r]>pivot:
                r-=1
            if l>=r:
                break
            else:
                self.array[l],self.array[r]=self.array[r],self.array[l]    
                l+=1
        self.array[l],self.array[p]=self.array[p],self.array[l]    
        print(self.array)
        return l

    def quick_sort(self, l, r):
        if r-l<=0:
            return 
        p = partition(self.array, l,r)
        quick_sort(self.array, l, p-1)
        quick_sort(self.array, p+1, r)

4.1 Test: quick_sort Instance Method

arr = [int(char) for char in "052163"]
my_array = SortableArray(arr)
my_array.array
# my_array.partition(l=0,r=len(my_array.array)-1)
my_array.quick_sort(l=0,r=len(my_array.array)-1)
my_array.array

[0, 5, 2, 1, 6, 3] 0 4 3
[0, 1, 2, 3, 6, 5]
[0, 1, 2, 3, 6, 5] 0 1 2
[0, 1, 2, 3, 6, 5]
[0, 1, 2, 3, 6, 5] 0 0 1
[0, 1, 2, 3, 6, 5]
[0, 1, 2, 3, 6, 5] 4 4 5
[0, 1, 2, 3, 5, 6]

[0, 1, 2, 3, 5, 6]