My DSA Notes 5: Sorting Algorithms in Python

Published in

Level Up Coding

6 min readJul 4, 2023

Introduction:

Sorting is a fundamental operation in computer science, and understanding different sorting algorithms is essential for any aspiring programmer or computer scientist. In this comprehensive guide, we will explore various sorting algorithms and provide a detailed explanation of each algorithm along with code examples.

Common Sorting Algorithms

Bubble Sort:

Bubble sort is a simple and intuitive sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order. The process continues until the entire list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list.

Code Example:

class Unsorted_Data:
    def bubble_sort(self):
        for i in range(len(self.list)-1):
            for j in range(len(self.list)-1-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

Selection Sort:

Selection sort is an in-place comparison sorting algorithm. It divides the input list into two parts: the sorted and the unsorted part. The algorithm repeatedly finds the minimum (or maximum) element from the unsorted part and swaps it with the leftmost unsorted element, expanding the sorted part.

Code Example:

class Unsorted_Data:
    def selection_sort(self):
        for i in range(len(self.list)):
            index_of_min = i
            for j in range(i+1, len(self.list)):
                if self.list[j] < self.list[index_of_min]:
                    index_of_min = j
            self.list[i], self.list[index_of_min] = self.list[index_of_min], self.list[i]

Insertion Sort:

Insertion sort is a simple and efficient sorting algorithm that builds the final sorted array one item at a time. It gradually inserts each element into its proper position within the sorted portion of the array.

Code Example:

class Unsorted_Data:
    def insertion_sort(self):
        for i in range(1, len(self.list)):
            temp_value = self.list[i]
            for j in range(i-1, -1, -1):
                if temp_value < self.list[j]:
                    self.list[j+1] = self.list[j]
                    self.list[j] = temp_value
                else:
                    break

Bucket Sort:

Bucket sort is a distribution sorting algorithm that works by distributing elements into a set of buckets and then sorting the elements within each bucket individually. It is particularly useful when the input is uniformly distributed over a range.

Code Example:

class Unsorted_Data:
    def bucket_sort(self):
        number_of_buckets = round(math.sqrt(len(self.list)))
        buckets = [[] for i in range(number_of_buckets)]
        max_item = max(self.list)

        for item in self.list:
            destination_bucket = math.ceil(item*number_of_buckets/max_item)
            buckets[destination_bucket-1].append(item)

        self.list = []
        for bucket in buckets:
            bucket.sort()
            self.list.extend(bucket)

Merge Sort:

Merge sort is a divide-and-conquer sorting algorithm that divides the unsorted list into smaller sublists, recursively sorts them, and then merges them to produce a sorted list. It is known for its stable and efficient sorting performance.

Code Example:

class Unsorted_Data:
    def merge_sort(self):
        def merge_helper(array):
            if len(array) > 1:
                middle = len(array)//2
                left_side = array[:middle]
                right_side = array[middle:]

                merge_helper(left_side)
                merge_helper(right_side)

                i = j = index = 0

                while i < len(left_side) and j < len(right_side):
                    if left_side[i] < right_side[j]:
                        array[index] = left_side[i]
                        i += 1
                    else:
                        array[index] = right_side[j]
                        j += 1
                    index += 1

                while i < len(left_side):
                    array[index] = left_side[i]
                    i += 1
                    index += 1

                while j < len(right_side):
                    array[index] = right_side[j]
                    j += 1
                    index += 1


        merge_helper(self.list)

Quick Sort:

Quick sort is a highly efficient sorting algorithm based on the divide-and-conquer principle. It works by selecting a pivot element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The process is then applied recursively on the sub-arrays.

Code Example:

class Unsorted_Data:
    def quick_sort(self):
        def quick_sort_helper(array):
            if len(array) <= 1:
                return array
            else:
                pivot = array[0]
                less_than = [item for item in array[1:] if item < pivot]
                more_than = [item for item in array[1:] if item > pivot]
                return quick_sort_helper(less_than) + [pivot] + quick_sort_helper(more_than)

        self.list = quick_sort_helper(self.list)

Heap Sort:

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It first builds a max-heap from the unsorted array and then repeatedly extracts the maximum element from the heap and places it at the end of the sorted array.

Code Example:

class Unsorted_Data:
    def heap_sort(self):
        def heapify(arr, n, i):
            largest = i
            l = 2 * i + 1
            r = 2 * i + 2

            if l < n and arr[i] < arr[l]:
                largest = l

            if r < n and arr[largest] < arr[r]:
                largest = r

            if largest != i:
                arr[i], arr[largest] = arr[largest], arr[i]
                heapify(arr, n, largest)

        arr = self.list
        n = len(arr)

        for i in range(n // 2, -1, -1):
            heapify(arr, n, i)

        for i in range(n - 1, 0, -1):
            arr[i], arr[0] = arr[0], arr[i]
            heapify(arr, i, 0)

Testing and Output

# Create an instance of Unsorted_Data with sample data
data = [9, 7, 8, 6, 4, 5, 1, 2, 3, 0]
unsorted_data = Unsorted_Data(data)

# Perform bubble sort
unsorted_data.bubble_sort()
print("Bubble Sort: " + str(unsorted_data.list))

# Output: Bubble Sort: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Create another instance of Unsorted_Data with the same data
data = [9, 7, 8, 6, 4, 5, 1, 2, 3, 0]
unsorted_data = Unsorted_Data(data)

# Perform selection sort
unsorted_data.selection_sort()
print("Selection Sort: " + str(unsorted_data.list))

# Output: Selection Sort: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Create another instance of Unsorted_Data with the same data
data = [9, 7, 8, 6, 4, 5, 1, 2, 3, 0]
unsorted_data = Unsorted_Data(data)

# Perform insertion sort
unsorted_data.insertion_sort()
print("Insertion Sort: " + str(unsorted_data.list))

# Output: Insertion Sort: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Create another instance of Unsorted_Data with the same data
data = [9, 7, 8, 6, 4, 5, 1, 2, 3, 0]
unsorted_data = Unsorted_Data(data)

# Perform bucket sort
unsorted_data.bucket_sort()
print("Bucket Sort: " + str(unsorted_data.list))

# Output: Bucket Sort: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Create another instance of Unsorted_Data with different data
data = [0, 0.9, 0.7, 0.8, 0.6, 0.4, 0.5, 0.1, 0.2, 0.3]
unsorted_data = Unsorted_Data(data)

# Perform bucket sort on float data
unsorted_data.bucket_sort()
print("Bucket Sort (Float Data): " + str(unsorted_data.list))

# Output: Bucket Sort (Float Data): [0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]

# Create another instance of Unsorted_Data with the same data
data = [0, 0.9, 0.7, 0.8, 0.6, 0.4, 0.5, 0.1, 0.2, 0.3]
unsorted_data = Unsorted_Data(data)

# Perform merge sort
unsorted_data.merge_sort()
print("Merge Sort: " + str(unsorted_data.list))

# Output: Merge Sort: [0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]

# Create another instance of Unsorted_Data with the same data
data = [0, 0.9, 0.7, 0.8, 0.6, 0.4, 0.5, 0.1, 0.2, 0.3]
unsorted_data = Unsorted_Data(data)

# Perform quick sort
unsorted_data.quick_sort()
print("Quick Sort: " + str(unsorted_data.list))

# Output: Quick Sort: [0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]

# Create another instance of Unsorted_Data with the same data
data = [0, 0.9, 0.7, 0.8, 0.6, 0.4, 0.5, 0.1, 0.2, 0.3]
unsorted_data = Unsorted_Data(data)

# Perform heap sort
unsorted_data.heap_sort()
print("Heap Sort: " + str(unsorted_data.list))

# Output: Heap Sort: [0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]

Conclusion:

Sorting algorithms play a crucial role in computer science and are widely used in various applications. In this comprehensive guide, we have explored several important sorting algorithms, including Bubble Sort, Selection Sort, Insertion Sort, Bucket Sort, Merge Sort, Quick Sort, and Heap Sort. Understanding these algorithms, their principles, and their implementation is essential for any programmer or computer scientist looking to optimize their code and solve real-world problems efficiently.

My DSA Notes 5: Sorting Algorithms in Python

Introduction:

Common Sorting Algorithms

Testing and Output

Conclusion:

Level Up Coding

Written by Ebo Jackson