Types Of Sorting Algorithm

Bilal Muhammad

3 years ago

There are several types of Sorting as Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort, Radix Sort. Lets get informed what are these? How these work? What are the features of different types of sorting?

What is Bubble Sort?

Bubble sort is a sorting algorithm that repeatedly steps through the list to be sorted, comparing adjacent items and swapping them if they are in the wrong order.

How Bubble Sort works?

The bubble sort algorithm works by repeatedly passing through the list to be sorted, comparing adjacent elements and swapping them if they are in the wrong order. At the end of each pass, the largest element will be in its final position, and all of the other elements will have been moved closer to their correct positions.

Features of bubble sort

simple and easy to understand
requires only a small number of comparisons to sort a set of items
iterative, meaning it can be inefficient on large data sets
sorts in ascending order, by default

Bubble sort code examples

def bubble_sort(alist):
      for passnum in range(len(alist)-1,0,-1):
	for i in range(passnum):
	      if alist[i]>alist[i+1]:
	         temp = alist[i]
	         alist[i] = alist[i+1]
	         alist[i+1] = temp
     return alist

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

class bubbleSort:
    def __init__(self, list):
        self.list = list
        self.size = len(list)
        self.swap = 0
        self.comparison = 0
    def sort(self):
        for i in range(self.size):
            for j in range(self.size - i - 1):
                self.comparison += 1
                if self.list[j] > self.list[j + 1]:
                    self.swap += 1
                    self.list[j], self.list[j + 1] = self.list[j + 1], self.list[j]
        return self.list
    def getSwap(self):
        return self.swap
    def getComparison(self):
        return self.comparison

class bubbleSort:
    def __init__(self, list):
        self.list = list
    def sort(self):
        for i in range(len(self.list)):
            for j in range(len(self.list)-1):
                if self.list[j] > self.list[j+1]:
                    self.list[j], self.list[j+1] = self.list[j+1], self.list[j]
        return self.list

class bubbleSort:
    def __init__(self, list):
        self.list = list
    def bubbleSort(self):
        for i in range(len(self.list)-1, 0, -1):
            for j in range(i):
                if self.list[j] > self.list[j+1]:
                    temp = self.list[j]
                    self.list[j] = self.list[j+1]
                    self.list[j+1] = temp
        return self.list

What is Insertion Sort?

Insertion sort is a sorting algorithm that builds a sorted list from an unordered list by inserting elements one at a time.

How Insertion Sort works?

The insertion sort algorithm works by taking a list of items and inserting them one at a time into a sorted list. It does this by finding the position of the item to be inserted and then inserting it into the list at that position.

Features of Insertion Sort

It is a simple algorithm.
It is a stable sorting algorithm.
It is a comparison-based sorting algorithm.
It is a in-place sorting algorithm.
It is a tail-recursive algorithm.
It is a linear-time algorithm.

Insertion sort code examples

def insertion_sort(lst):
    for i in range(1, len(lst)):
        j = i
        while j > 0 and lst[j] < lst[j - 1]:
            lst[j], lst[j - 1] = lst[j - 1], lst[j]
            j -= 1
    return lst

def insertion_sort(lst):
    for i in range(1, len(lst)):
        j = i
        while j > 0 and lst[j-1] > lst[j]:
            lst[j-1], lst[j] = lst[j], lst[j-1]
            j -= 1
    return lst

class insertionSort:
    def __init__(self, list):
        self.list = list
        self.length = len(list)

    def sort(self):
        for i in range(1, self.length):
            j = i
            while j > 0 and self.list[j] < self.list[j-1]:
                self.list[j], self.list[j-1] = self.list[j-1], self.list[j]
                j -= 1
        return self.list

class insertionSort:
    def __init__(self, list):
        self.list = list
        self.length = len(list)
        self.swap_count = 0
        self.comparison_count = 0
    def sort(self):
        for i in range(1, self.length):
            j = i
            while j > 0 and self.list[j] < self.list[j-1]:
                self.swap(j, j-1)
                j -= 1
                self.swap_count += 1
                self.comparison_count += 1
    def swap(self, i, j):
        temp = self.list[i]
        self.list[i] = self.list[j]
        self.list[j] = temp
    def get_swap_count(self):
        return self.swap_count
    def get_comparison_count(self):
        return self.comparison_count

What is Selection Sort?

Selection Sort is a sorting algorithm that takes an unsorted list of items and organizes them in ascending order. It does this by selecting the smallest item from the list and placing it at the beginning of the list. It then repeats this process for the remaining items in the list.

How Selection Sort works?

In selection sort, the algorithm starts by comparing the first two elements in the list and selects the smaller one to be placed in the first position. It then compares the next two elements and selects the smaller one to be placed in second position and so on.

Features of Selection Sort

Easy to understand
O(n2) time complexity
Can be used for any data type
Requires a loop
Sorting is stable

Selection sort code examples

def selection_sort(lst):
    for i in range(len(lst)):
        min_index = i
        for j in range(i+1, len(lst)):
            if lst[j] < lst[min_index]:
                min_index = j
        lst[i], lst[min_index] = lst[min_index], lst[i]
    return lst

class selectionsort:
    def __init__(self, list):
        self.list = list

    def sort(self):
        for i in range(len(self.list)):
            min = i
            for j in range(i+1, len(self.list)):
                if self.list[j] < self.list[min]:
                    min = j
            self.list[i], self.list[min] = self.list[min], self.list[i]
        return self.list

What is Merge Sort?

Merge sort is a comparison-based sorting algorithm that sorts data using the divide and conquer technique. The algorithm splits the data set into halves, sorts each half, and then merges the two sorted halves.

How Merge Sort works?

The merge sort algorithm starts by dividing the input data set into two equal parts. It then proceeds to sort each part separately. After that, the two sorted parts are merged together to form the sorted data set.

Features of Merge Sort

Merge Sort is a comparison-based sorting algorithm.
Merge Sort is a divide and conquer algorithm.
Merge Sort is a stable sorting algorithm.
Merge Sort is an in-place sorting algorithm.
Merge Sort is a serial algorithm.

Merge sort code examples

def merge_sort(a):
    if len(a) > 1:
        mid = len(a) // 2
        left = a[:mid]
        right = a[mid:]

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                a[k] = left[i]
                i += 1
            else:
                a[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            a[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            a[k] = right[j]
            j += 1
            k += 1

def merge_sort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        merge_sort(lefthalf)
        merge_sort(righthalf)

        i = 0
        j = 0
        k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i = i + 1
            else:
                alist[k] = righthalf[j]
                j = j + 1
            k = k + 1

        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i = i + 1
            k = k + 1

        while j < len(righthalf):
            alist[k] = righthalf[j]
            j = j + 1
            k = k + 1
    return alist

class mergesort:
    def __init__(self, array):
        self.array = array
        self.length = len(array)
        self.mergesort()

    def mergesort(self):
        if self.length > 1:
            mid = self.length // 2
            left = self.array[:mid]
            right = self.array[mid:]
            left = mergesort(left)
            right = mergesort(right)
            self.array = self.merge(left.array, right.array)

    def merge(self, left, right):
        result = []
        while len(left) > 0 and len(right) > 0:
            if left[0] < right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        if len(left) > 0:
            result += left
        if len(right) > 0:
            result += right
        return result

class mergesort:
    def __init__(self, array):
        self.array = array
        self.length = len(array)
        self.merge_sort(self.array, 0, self.length - 1)

    def merge_sort(self, array, start, end):
        if start < end:
            mid = (start + end) // 2
            self.merge_sort(array, start, mid)
            self.merge_sort(array, mid + 1, end)
            self.merge(array, start, mid, end)

    def merge(self, array, start, mid, end):
        left = array[start:mid + 1]
        right = array[mid + 1:end + 1]
        i = 0
        j = 0
        k = start
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                array[k] = left[i]
                i += 1
            else:
                array[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1

class mergesort:
    def __init__(self, data):
        self.data = data
        self.length = len(data)
        self.merge_sort(self.data, 0, self.length - 1)
    def merge_sort(self, data, left, right):
        if left < right:
            mid = (left + right) // 2
            self.merge_sort(data, left, mid)
            self.merge_sort(data, mid + 1, right)
            self.merge(data, left, mid, right)
    def merge(self, data, left, mid, right):
        left_data = data[left:mid + 1]
        right_data = data[mid + 1:right + 1]
        left_data.append(999999999) # sentinel value
        right_data.append(999999999) # sentinel value
        i = j = 0
        for k in range(left, right + 1):
            if left_data[i] <= right_data[j]:
                data[k] = left_data[i]
                i += 1
            else:
                data[k] = right_data[j]
                j += 1

What is Quick Sort?

Quick sort is a sorting algorithm which partitions the input array into two arrays: one larger than the Kth element, and one smaller. It then recursively sorts the two arrays.

How Quick Sort works?

In the quick sort algorithm, the partitioning is done recursively. The leftmost element in the sublist is compared with the rightmost element. If they are equal, the sublist is sorted. If the leftmost element is less than the rightmost element, the leftmost element is placed in the new sublist and the rightmost element is placed in the old sublist. If the leftmost element is greater than the rightmost element, the rightmost element is placed in the new sublist and the leftmost element is placed in the old sublist.

Features of Quick Sort

Quick sort is a divide and conquer algorithm
The algorithm partitions the input array into two parts: the leftmost subarray and the rightmost subarray
The leftmost subarray is then sorted using a recursive call to quick sort
The rightmost subarray is not sorted and is returned to the caller
The partitioning step is repeated until the entire array is sorted

Quick sort code examples

def quick_sort(alist):
    quick_sort_helper(alist, 0, len(alist) - 1)

def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

class quicksort:
    def __init__(self, array):
        self.array = array
        self.length = len(array)

    def partition(self, low, high):
        pivot = self.array[high]
        i = low - 1
        for j in range(low, high):
            if self.array[j] <= pivot:
                i += 1
                self.array[i], self.array[j] = self.array[j], self.array[i]
        self.array[i + 1], self.array[high] = self.array[high], self.array[i + 1]
        return i + 1

    def quick_sort(self, low, high):
        if low < high:
            pi = self.partition(low, high)
            self.quick_sort(low, pi - 1)
            self.quick_sort(pi + 1, high)

    def print_array(self):
        print(self.array)

class quicksort:
    def __init__(self, array):
        self.array = array
        self.length = len(array)
        self.quicksort(0, self.length - 1)

    def quicksort(self, start, end):
        if start < end:
            pivot = self.partition(start, end)
            self.quicksort(start, pivot - 1)
            self.quicksort(pivot + 1, end)

    def partition(self, start, end):
        pivot = self.array[end]
        i = start - 1
        for j in range(start, end):
            if self.array[j] <= pivot:
                i += 1
                self.swap(i, j)
        self.swap(i + 1, end)
        return i + 1

    def swap(self, i, j):
        self.array[i], self.array[j] = self.array[j], self.array[i]

What is Heap Sort?

Heap sort is a sorting algorithm that works by first creating a heap out of the unsorted list, and then iteratively removing the largest element from the heap and inserting it into the correct position in the sorted list.

How Heap Sort works?

Heap sorting is a comparison-based sorting algorithm. It works by first constructing a heap out of the input elements. The root node of the heap is then compared with the last node of the heap. If the root node is greater than the last node, the last node is replaced with the root node. If the root node is less than the last node, the last node is left unchanged. This process is then repeated for the children of the last node, and so on, until the entire heap is sorted.

Simply, the algorithm starts by sorting the first element in the array. It then compares the first two elements and inserts the larger element into the array at the appropriate position. The algorithm then compares the last two elements and inserts the larger element into the array at the appropriate position. The process then repeats until the entire array is sorted.

Features of Heap Sort

Heap Sort is a stable sorting algorithm.
Heap Sort is an in-place sorting algorithm.
Heap Sort takes linear time to sort an array of n elements.

Heap sort code examples

def heap_sort(a):
    n = len(a)
    for i in range(n, -1, -1):
        heap_adjust(a, i, n)
    for i in range(n - 1, 0, -1):
        a[i], a[0] = a[0], a[i]
        heap_adjust(a, 0, I)

def heap_sort(arr):
    for i in range(len(arr)):
        heapify(arr, i)
    for i in range(len(arr) - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i - 1)
    return arr

class heapsort:
    def __init__(self, array):
        self.array = array
        self.heapSize = len(array)
        self.buildHeap()
        self.sort()

    def buildHeap(self):
        for i in range(self.heapSize//2, -1, -1):
            self.heapify(i)

    def heapify(self, i):
        left = 2*i + 1
        right = 2*i + 2
        largest = i
        if left < self.heapSize and self.array[left] > self.array[largest]:
            largest = left
        if right < self.heapSize and self.array[right] > self.array[largest]:
            largest = right
        if largest != i:
            self.array[i], self.array[largest] = self.array[largest], self.array[i]
            self.heapify(largest)

    def sort(self):
        for i in range(self.heapSize-1, 0, -1):
            self.array[0], self.array[i] = self.array[i], self.array[0]
            self.heapSize -= 1
            self.heapify(0)

What is Radix Sort?

Radix Sort is a sorting algorithm that sorts elements in a list according to the numerical value of each element’s digit.

How Radix Sort works?

Radix Sort is a sorting algorithm that works by dividing an input into a series of buckets and sorting each bucket independently.

Features of Radix Sort

It is a comparison-based sorting algorithm.
It is a stable sorting algorithm.
It is a Divide-and-Conquer algorithm.
It is an in-place sorting algorithm.
It is a deterministic sorting algorithm.
It is a priority queue-based sorting algorithm.

Radix sort code examples

def Radix_Sort(A, d):
    # A is the list to be sorted
    # d is the number of digits
    # initialize the buckets
    buckets = [[] for _ in range(10)]
    # initialize the index
    index = 1
    # loop until the index is greater than the number of digits
    while index <= d:
        # loop through the list
        for i in range(len(A)):
            # get the digit at the index
            digit = (A[i] // (10 ** (index - 1))) % 10
            # append the number to the bucket
            buckets[digit].append(A[i])
        # empty the list
        A = []
        # loop through the buckets
        for i in range(10):
            # loop through the bucket
            for j in range(len(buckets[i])):
                # append the number to the list
                A.append(buckets[i][j])
            # empty the bucket
            buckets[i] = []
        # increase the index
        index += 1
    return A

class RadixSort:
    def __init__(self, arr):
        self.arr = arr
        self.max = max(arr)
        self.digit = 1
        self.bucket = [[] for i in range(10)]

    def sort(self):
        while self.max // self.digit > 0:
            for i in self.arr:
                self.bucket[i // (self.digit * 10) % 10].append(i)
            self.arr.clear()
            for i in self.bucket:
                self.arr.extend(i)
            self.digit *= 10
            self.bucket = [[] for i in range(10)]
        return self.arr

class RadixSort:
    def __init__(self):
        self.radix = 10
        self.n = 0
        self.digit = 1
        self.bucket = [0] * self.radix
        self.output = [0] * self.n
        self.count = [0] * self.radix
        self.temp = [0] * self.n

    def getDigit(self, num, digit):
        return (num // self.radix ** digit) % self.radix

    def sort(self, A):
        for i in range(self.n):
            self.temp[i] = A[i]
        for i in range(self.n):
            self.output[i] = self.temp[i]
        for i in range(self.n):
            self.count[self.getDigit(self.output[i], self.digit)] += 1
        for i in range(1, self.radix):
            self.count[i] += self.count[i - 1]
        for i in range(self.n - 1, -1, -1):
            self.bucket[self.count[self.getDigit(self.output[i], self.digit)] - 1] = self.output[i]
            self.count[self.getDigit(self.output[i], self.digit)] -= 1
        for i in range(self.n):
            self.output[i] = self.bucket[i]
        self.digit += 1
        if self.digit < self.radix:
            self.sort(self.output)

Conclusion

Sorting algorithms, each has its own strengths and weaknesses. I did my best to share useful stuff with you to make the best understanding regarding complexity of code in sorting algorithms.

Find more here about Algorithms…