Sorting Algorithms - potatoscript/dsa GitHub Wiki

šŸ”„ Sorting Algorithms ā€“ Putting Things in Order šŸ”„

Sorting algorithms are a set of techniques used to arrange elements in a specific order, such as ascending or descending order. Sorting is fundamental in programming, and many problems can be solved more efficiently once the data is sorted. There are various sorting algorithms, each with its strengths and weaknesses. In this tutorial, we'll go through some of the most common sorting algorithms, explaining them with simple examples and professional-level explanations.

šŸ§© Why Sorting?

Sorting is crucial in computer science and programming for many reasons:

  • Efficient Searching: A sorted list allows faster searching algorithms, like binary search.
  • Data Presentation: It helps present data in a readable and organized manner (e.g., arranging names alphabetically or numbers in ascending order).
  • Optimized Performance: Many problems can be solved more efficiently if the data is sorted first (e.g., finding duplicates, merging lists).

šŸ§© Bubble Sort ā€“ The Slow Learner

Bubble Sort is the simplest sorting algorithm but not very efficient for large datasets. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.

Steps of Bubble Sort:

  1. Compare each pair of adjacent elements.
  2. If the elements are in the wrong order (i.e., the first is larger than the second), swap them.
  3. Repeat the process for all elements in the list.
  4. After each pass through the list, the largest unsorted element is "bubbled" to its correct position.

Bubble Sort Example

Consider the following unsorted list:

[5, 2, 9, 1, 5, 6]

Pass 1:

  • Compare 5 and 2 ā†’ Swap ā†’ [2, 5, 9, 1, 5, 6]
  • Compare 5 and 9 ā†’ No swap.
  • Compare 9 and 1 ā†’ Swap ā†’ [2, 5, 1, 9, 5, 6]
  • Compare 9 and 5 ā†’ Swap ā†’ [2, 5, 1, 5, 9, 6]
  • Compare 9 and 6 ā†’ Swap ā†’ [2, 5, 1, 5, 6, 9]
  • After Pass 1: [2, 5, 1, 5, 6, 9] (9 is in its correct position)

Repeat the process until the list is sorted.

C# Code for Bubble Sort

using System;

public class BubbleSortExample
{
    public static void BubbleSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    // Swap arr[j] and arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void Main()
    {
        int[] arr = { 5, 2, 9, 1, 5, 6 };
        Console.WriteLine("Unsorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
        
        BubbleSort(arr);

        Console.WriteLine("\nSorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
    }
}

Time Complexity of Bubble Sort

  • Best Case: O(n) when the array is already sorted.
  • Worst Case: O(nĀ²) when the array is reversed.
  • Average Case: O(nĀ²)

šŸ§© Selection Sort ā€“ The Smarter Picker

Selection Sort improves upon Bubble Sort by selecting the minimum element from the unsorted portion of the array and swapping it with the first unsorted element.

Steps of Selection Sort:

  1. Start from the first element.
  2. Find the minimum element in the unsorted portion of the list.
  3. Swap the minimum element with the first unsorted element.
  4. Move the boundary between sorted and unsorted portions and repeat the process.

Selection Sort Example

Given the unsorted list:

[5, 2, 9, 1, 5, 6]

Step 1: Find the smallest element (1), and swap it with 5 ā†’ [1, 2, 9, 5, 5, 6]

Step 2: Find the next smallest element (2), no swap needed ā†’ [1, 2, 9, 5, 5, 6]

Step 3: Find the next smallest element (5), no swap needed ā†’ [1, 2, 5, 9, 5, 6]

Step 4: Find the next smallest element (5), no swap needed ā†’ [1, 2, 5, 5, 9, 6]

Step 5: Find the next smallest element (6), swap it with 9 ā†’ [1, 2, 5, 5, 6, 9]

C# Code for Selection Sort

using System;

public class SelectionSortExample
{
    public static void SelectionSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }
            // Swap arr[i] and arr[minIndex]
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void Main()
    {
        int[] arr = { 5, 2, 9, 1, 5, 6 };
        Console.WriteLine("Unsorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
        
        SelectionSort(arr);

        Console.WriteLine("\nSorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
    }
}

Time Complexity of Selection Sort

  • Best Case: O(nĀ²)
  • Worst Case: O(nĀ²)
  • Average Case: O(nĀ²)

šŸ§© Insertion Sort ā€“ The Building Blocks

Insertion Sort works similarly to how you might sort playing cards in your hand. It builds the sorted portion of the list one element at a time by inserting each new element into its correct position.

Steps of Insertion Sort:

  1. Start with the second element (since a single element is already sorted).
  2. Compare it with the element before it.
  3. If it's smaller, shift the previous elements to the right to make room and insert the new element in the correct position.
  4. Repeat the process until the entire list is sorted.

Insertion Sort Example

Given the unsorted list:

[5, 2, 9, 1, 5, 6]

Step 1: Compare 2 with 5, insert 2 ā†’ [2, 5, 9, 1, 5, 6]

Step 2: Compare 9 with 5, no change ā†’ [2, 5, 9, 1, 5, 6]

Step 3: Compare 1 with 9, 5, and 2, insert 1 ā†’ [1, 2, 5, 9, 5, 6]

Step 4: Compare 5 with 9, insert 5 ā†’ [1, 2, 5, 5, 9, 6]

Step 5: Compare 6 with 9, insert 6 ā†’ [1, 2, 5, 5, 6, 9]

C# Code for Insertion Sort

using System;

public class InsertionSortExample
{
    public static void InsertionSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 1; i < n; i++)
        {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void Main()
    {
        int[] arr = { 5, 2, 9, 1, 5, 6 };
        Console.WriteLine("Unsorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
        
        InsertionSort(arr);

        Console.WriteLine("\nSorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
    }
}

Time Complexity of Insertion Sort

  • Best Case: O(n) when the list is already sorted.
  • Worst Case: O(nĀ²) when the list is sorted in reverse order.
  • Average Case: O(nĀ²)