Different Sorting Algorithms comparison

based upon the Time Complexity

Sorting Algorithms: A Comparative Analysis with Demonstrations

Sorting is a fundamental concept in computer science and a crucial area of research. It plays a significant role in improving search efficiency, insertion, and deletion operations in data structures. This blog presents a comparative analysis of five major sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort. We will explore their working principles, analyze their time and space complexity, and observe their performance under different conditions.

---

Introduction

Sorting algorithms arrange elements in ascending or descending order to optimize data processing. Efficient sorting can reduce computational complexity, making problem-solving faster. Sorting methods are broadly categorized into:

• Internal Sorting: Sorting occurs within the main memory.
• External Sorting: Sorting involves external storage due to large data size.

---

Sorting Algorithm Classification Parameters

1. Stability

A sorting algorithm is stable if it maintains the relative order of duplicate elements. Stability is crucial when sorting objects based on multiple attributes.

2. Adaptivity

A sorting algorithm is adaptive if it performs better when the input is already partially sorted. For example, Quick Sort exhibits different performance levels based on pre-sortedness.

3. Time Complexity

Time complexity measures the execution time of an algorithm. It is evaluated under three cases:

• Best Case (Ω): When the input is already optimized.
• Average Case (Θ): The expected performance on random data.
• Worst Case (O): The maximum time required for execution.

4. Space Complexity

Space complexity determines the memory usage of an algorithm, which includes both the input size and additional auxiliary space.

---

Implementations & Simulations

1. Bubble Sort

Concept: Repeatedly compares adjacent elements and swaps them if they are in the wrong order.

Python Implementation:

def bubble_sort(arr):

    n = len(arr)

    for i in range(n):

        swapped = False

        for j in range(0, n-i-1):

            if arr[j] > arr[j+1]:

                arr[j], arr[j+1] = arr[j+1], arr[j]

                swapped = True

        if not swapped:

            break

Output:

Input: [64, 34, 25, 12, 22, 11, 90]

Sorted Output: [11, 12, 22, 25, 34, 64, 90]

Step-by-Step Explanation:

1. Iterate through the list multiple times.​
2. In each iteration, compare adjacent elements.
3. Swap them if they are in the wrong order.​ If no swaps occur in a full pass, the list is sorted, and the algorithm terminates early.

---

2. Selection Sort

Concept: Finds the smallest element and places it at the beginning of the list.

Python Implementation:

def selection_sort(arr):

    n = len(arr)

    for i in range(n):

        min_idx = i

        for j in range(i+1, n):

            if arr[j] < arr[min_idx]:

                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]

Output:

Input: [64, 34, 25, 12, 22, 11, 90]

Sorted Output: [11, 12, 22, 25, 34, 64, 90]

Step-by-Step Explanation:

1. Start with the entire list as the unsorted region.​
2. Find the smallest element in the unsorted region.​
3. Swap it with the first element of the unsorted region.​
4. Expand the sorted region by one element and repeat until the entire list is sorted.

---

3. Insertion Sort

Concept: Picks an element and places it at the correct position relative to the already sorted portion.

Python Implementation:

def insertion_sort(arr):

    for i in range(1, len(arr)):

        key = arr[i]

        j = i-1

        while j >= 0 and key < arr[j]:

            arr[j + 1] = arr[j]

            j -= 1

        arr[j + 1] = key

Output:

Input: [64, 34, 25, 12, 22, 11, 90]

Sorted Output: [11, 12, 22, 25, 34, 64, 90]

Step-by-Step Explanation:

1. Assume the first element is sorted.​
2. Take the next element (key) and compare it with elements in the sorted region.​
3. Shift elements in the sorted region to the right to make space for the key if they are greater than the key.​
4. Insert the key into its correct position.​
5. Repeat until all elements are sorted.

 

---

4. Merge Sort

Concept: Uses divide-and-conquer by breaking the list into smaller parts and merging them in sorted order.

Python Implementation:

def merge_sort(arr):

    if len(arr) > 1:

        mid = len(arr) // 2

        L = arr[:mid]

        R = arr[mid:]

 

        merge_sort(L)

        merge_sort(R)

 

        i = j = k = 0

 

        while i < len(L) and j < len(R):

            if L[i] < R[j]:

                arr[k] = L[i]

                i += 1

            else:

                arr[k] = R[j]

                j += 1

            k += 1

 

        while i < len(L):

            arr[k] = L[i]

            i += 1

            k += 1

 

        while j < len(R):

            arr[k] = R[j]

            j += 1

            k += 1

Output:

Input: [64, 34, 25, 12, 22, 11, 90]

Sorted Output: [11, 12, 22, 25, 34, 64, 90]

Step-by-Step Explanation:

1. Divide the list into two halves recursively until each sublist contains a single element.​
2. Merge the sublists by comparing the elements and arranging them in order.​
3. Continue merging until the entire list is reconstructed in sorted order.

---

5. Quick Sort

Concept: Selects a pivot element and partitions the list into two halves, recursively sorting them.

Python Implementation:

def quick_sort(arr):

    if len(arr) <= 1:

        return arr

    else:

        pivot = arr[len(arr) // 2]

        left = [x for x in arr if x < pivot]

        middle = [x for x in arr if x == pivot]

        right = [x for x in arr if x > pivot]

        return quick_sort(left) + middle + quick_sort(right)

Output:

Input: [64, 34, 25, 12, 22, 11, 90]

Sorted Output: [11, 12, 22, 25, 34, 64, 90]

---

Comparative Analysis

Algorithm	Best Case (Ω)	Average Case (Θ)	Worst Case (O)
Bubble Sort	O(n)	O(n²)	O(n²)
Selection Sort	O(n²)	O(n²)	O(n²)
Insertion Sort	O(n)	O(n²)	O(n²)
Merge Sort	O(n log n)	O(n log n)	O(n log n)
Quick Sort	O(n log n)	O(n log n)	O(n²)

---

Conclusion

Sorting algorithms play a vital role in data organization and efficiency. The choice of algorithm depends on factors like dataset size and initial order of elements. While Merge Sort and Quick Sort perform well for large datasets, Insertion Sort and Bubble Sort are useful for smaller or nearly sorted datasets.

Code Link : https://github.com/mrudula-hingmire/Sorting-Algorithms

---

References

1. Chauhan, Y., & Duggal, A. (2020). "Different Sorting Algorithms Comparison Based Upon the Time Complexity". ResearchGate
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms.
3. Python Documentation: https://docs.python.org/3/

---