Sorting Algorithms

Sorting Algorithms (Brief intro)

In this article, I will describe the most popular sorting algorithms and implement them from their definitions. The little background story of my burgeoning interest in data structures and algorithms generally lies in the fact that I like hacking. However my decision to formally acquaint myself with the subject was precipitated by a potential job interview and I have not looked back since. Now lets get to it.

Types of sort algorithms

• In place algorithms: these algorithms don't need additional memory.
• Stable algorithms: these algorithms don't change the original order of things after sorting.

Bogo sort

This algorithm is basically not your go to algorithm except you have a super computer. It basically gets all the possible permutations of the list to be sorted and then checks if they are sorted. The implementation can be seen below.

xxxxxxxxxx
# Here you need to sort with the permutation of all possibilities
# Basically has variety of possible implementations.
class BogoSort(Sort):
    def sort(self):
        p = self.arr
        found = False
        count = 0
        while found is not True:
            # Implement permutation n!
            # Fisher Yates approach
            for i in range(len(p)):
                r = random.randint(i, len(p) -1)
                p[i], p[r] = p[r], p[i]
            found = self.check(p)
        return p
    
​
    def check(self, p):
        for i in range(len(p)-1):
            if p[i] > p[i + 1]:
                return False
        return True

Time complexity of this algorithm is basically:

$$(n-1)n! \\ \ with \ and \ average \ performance \ of \ O((n+1)!)$$

This algorithm is not a stable algorithm but it is an inplace algorithm.

Bubble sort

For some weird reason I like this algorithm. It basically bubbles the largest value to the end of the list. It does this by binary comparison starting with the first and second element. If the first is greater than the second you move the first to the second position and then proceed to compare the second and the third till you get to the end of the list and start all over. This is a stable and an inplace algorithm which means that if there is sorted subsection, the algorithm will leave them that way. The implementation can be seen below.

xxxxxxxxxx
# this can be done with recursion and loop. I have implemented the recursion before will do the loop here
class BubbleSort(Sort):
    
​
    def sort(self):
​
        for i in range(len(self.arr)-1):
            for j in range(len(self.arr)-1-i):
                if self.arr[j] > self.arr[j+1]:
                    self.arr[j], self.arr[j+1] = self.arr[j+1], self.arr[j]
​
        return self.arr

From the implementation, this algorithm has an $O(n^2)$ complexity because you have to iterate twice over a list of size n.

Selection sort

This algorithm finds the largest(smallest) item and moves it over to the first index(last unsorted index) till the whole list is sorted. It is a stable and an inplace algorithm. The implementation can be seen below.

xxxxxxxxxx
class SelectionSort(Sort):
    
    def sort(self):
        for i in range(len(self.arr)):
            min = i
            for j in range(i, len(self.arr)-1):
                if self.arr[min] > self.arr[j+1]:
                    min = j+1
            self.arr[i], self.arr[min] = self.arr[min], self.arr[i]
        return self.arr

The time complexity is $O(n^2)$.

Insertion sort

This is very similar to selection sort with the exception that it makes many insertions and inserts can be costly depending on the type of memory we are looking at. It is an inplace and stable algorithm. Basically you compare an element in the list with the preceding ones and move it as required. In selection sort you had to check the elements in front for the smallest one but here you look at the preceding ones. The implementation can be seen below.

xxxxxxxxxx
class InsertionSort(Sort):
    
    def sort(self):
​
        for i in range(len(self.arr)):
            for j in range(i, 0, -1):
                if self.arr[j] < self.arr[j-1]:
                    self.arr[j], self.arr[j-1] = self.arr[j-1], self.arr[j] 
        return self.arr

The time complexity is $O(n^2)$.

Quick sort

This is one of the most popular sort algorithms. And arguably one of the fastest. It is a divide and conquer algorithm. In the first iteration you divide the list into two and move elements bigger than the middle element to right and does smaller to the left. You repeat the process recursively till the list is sorted. This algorithm is an in place algorithm but not stable.

xxxxxxxxxx
class QuickSort(Sort):
    
    def sort(self):
        self.pivot_and_check(0, len(self.arr) - 1)
​
        return self.arr
​
​
    def pivot_and_check(self, l_lim, r_lim):
        if l_lim >= r_lim:
            return
​
        pivot = (l_lim + r_lim) // 2
​
        # swap the pivot with the last item
        self.arr[pivot], self.arr[r_lim] = self.arr[r_lim], self.arr[pivot]
        mid = l_lim
​
        for i in range(l_lim, r_lim):
            if self.arr[i] < self.arr[r_lim]:
                self.arr[mid], self.arr[i] = self.arr[i], self.arr[mid]
                mid += 1
​
        self.arr[mid], self.arr[r_lim] = self.arr[r_lim], self.arr[mid]
​
        self.pivot_and_check(l_lim, mid-1)
        self.pivot_and_check(mid + 1, r_lim)

This algorithm has an $O(NlogN)$ time complexity.

Merge sort

This algorithm is another divide and conquer algorithm. It breaks the list down to a single unit and begins joining them in sorted order by making comparisms till the whole list is sorted. It is a stable algorithm but not in place. The implementation can be seen below.

xxxxxxxxxx
class MergeSort(Sort):
    
    
    def sort(self):
        return self.recursion(self.arr)
​
​
    def recursion(self, arr):
​
        # base case
        if len(arr) == 1:
            return arr
​
        midpoint = len(arr) // 2
​
        left = arr[:midpoint]
        right = arr[midpoint:]
        left_arr = self.recursion(left)
        right_arr = self.recursion(right)
​
        r_index = 0
        l_index = 0
        new_arr = []
​
        while l_index < len(left_arr) and r_index < len(right_arr):
            
            if left_arr[l_index] < right_arr[r_index]:
                new_arr.append(left_arr[l_index])
                l_index += 1
            else:
                new_arr.append(right_arr[r_index])
                r_index += 1
​
        if r_index < len(right_arr):
            for i in range(r_index, len(right_arr)):
                new_arr.append(right_arr[i])
​
        if l_index < len(left_arr):
            for i in range(l_index, len(left_arr)):
                new_arr.append(left_arr[i])
        return new_arr

This algorithm has an $O(NlogN)$ time complexity.

Competition time

I executed the code below

xxxxxxxxxx
p = [1, 8, -50, 100, 5, 7, -1, 49]
    # bogo
    print("bogo sort")
    bogo = BogoSort(p)
    tic = timer()
    result = bogo.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)
    print("-----------------------")
​
    # bubble sort
    print("bubble sort")
    bubble = BubbleSort(p)
    tic = timer()
    result = bubble.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)
    print("-----------------------")
​
​
    # selection sort
    print("selection sort")
    selection = SelectionSort(p)
    tic = timer()
    result = selection.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)
    print("-----------------------")
​
    # insertion sort
    print("insertion sort")
    insertion = InsertionSort(p)
    tic = timer()
    result = insertion.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)
    print("-----------------------")
​
    # quick sort
    print("quick sort")
    quick = QuickSort(p)
    tic = timer()
    result = quick.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)
    print("-----------------------")
​
​
    # merge sort
    print("merge sort")
    merge = MergeSort(p)
    tic = timer()
    result = merge.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)

Result:

Bogo sort - 1.2 secs. Don't use this for a large list. I tried it and it took forever.

Bubble sort - 2.0 secs.

Selection sort - 1.8 secs. Has a reputation of being efficient for small lists like the one used above.

Insertion sort - 1.9 secs. Not far away from selection sort.

Quick sort - 3.5 secs.

Merge sort - 3.19 secs.

Bonus

Sorting an object. I implemented an obect to test the sorting algorithms.

xxxxxxxxxx
class Object():
​
    def __init__(self, name, age):
        self.name = name
        self.age = age
​
​
    def __lt__(self, other):
        return self.age < other.age
    
    def __repr__(self):
        return str(self.name)
        
        
  p = [Object('Object1', 31), Object('Object2', 29), Object('Object3', 24), Object('Object4', 33)]
    # bogo
    print("bogo sort")
    bogo = BogoSort(p)
    tic = timer()
    result = bogo.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)
    print("-----------------------")
​
    # bubble sort
    print("bubble sort")
    bubble = BubbleSort(p)
    tic = timer()
    result = bubble.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)
    print("-----------------------")
​
​
    # selection sort
    print("selection sort")
    selection = SelectionSort(p)
    tic = timer()
    result = selection.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)
    print("-----------------------")
​
    # insertion sort
    print("insertion sort")
    insertion = InsertionSort(p)
    tic = timer()
    result = insertion.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)
    print("-----------------------")
​
    # quick sort
    print("quick sort")
    quick = QuickSort(p)
    tic = timer()
    result = quick.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)
    print("-----------------------")
​
​
    # merge sort
    print("merge sort")
    merge = MergeSort(p)
    tic = timer()
    result = merge.sort()
    print(result)
    toc = timer()
    total_time = toc - tic
    print(total_time)

Viola!!! Your object is sorted.

Thanks for reading.