Back to Welcome Page

Sorting Algorithms I: Fundamentals

Master the basic sorting algorithms, understand their implementation, and learn how to analyze their time and space complexity.

Learning Objectives

Core Concepts

  • Understand common sorting algorithms
  • Compare algorithm efficiency
  • Analyze time and space complexity
  • Identify appropriate use cases

Skills Development

  • Implementing sorting algorithms
  • Debugging sorting-related issues
  • Optimizing algorithm performance
  • Choosing the right algorithm for specific scenarios

Prerequisites

Required Knowledge

  • Basic programming concepts
  • Arrays and loops
  • Function calls and return values
  • Basic understanding of Big O notation

Recommended Preparation

  • Review array operations
  • Practice algorithm analysis
  • Study recursion fundamentals
  • Refresh knowledge of time complexity

Algorithm Comparison

Algorithm Time Complexity (Average) Time Complexity (Worst) Space Complexity Stability
Bubble Sort O(n²) O(n²) O(1) Stable
Selection Sort O(n²) O(n²) O(1) Unstable
Insertion Sort O(n²) O(n²) O(1) Stable

Video Lectures

Bubble Sort Algorithm

Key Concepts Covered:

  • Basic bubble sort implementation
  • Algorithm visualization
  • Time and space complexity analysis
  • Optimization techniques

Selection Sort Algorithm

Key Concepts Covered:

  • Selection sort implementation
  • Finding minimum values in arrays
  • In-place sorting techniques
  • Comparison with other algorithms

Insertion Sort Algorithm

Key Concepts Covered:

  • Insertion sort implementation
  • Partial sorting of arrays
  • Real-world applications
  • Performance characteristics

Bubble Sort Implementation

Java Implementation

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            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;
                    swapped = true;
                }
            }
            
            // If no swapping occurred in this pass, array is sorted
            if (!swapped) {
                break;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        
        System.out.println("Original array:");
        printArray(arr);
        
        bubbleSort(arr);
        
        System.out.println("Sorted array:");
        printArray(arr);
    }
    
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Selection Sort Implementation

Java Implementation

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in unsorted array
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // Swap the found minimum element with the first element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        
        System.out.println("Original array:");
        printArray(arr);
        
        selectionSort(arr);
        
        System.out.println("Sorted array:");
        printArray(arr);
    }
    
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Insertion Sort Implementation

Java Implementation

public class InsertionSort {
    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;
            
            /* Move elements of arr[0..i-1] that are greater than key
               to one position ahead of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        
        System.out.println("Original array:");
        printArray(arr);
        
        insertionSort(arr);
        
        System.out.println("Sorted array:");
        printArray(arr);
    }
    
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Practice Exercises

Implementation Exercises

Practice implementing these basic sorting algorithms:

  1. Implement Bubble Sort with a counter to track the number of swaps performed
  2. Modify Selection Sort to sort in descending order instead of ascending
  3. Implement Insertion Sort for sorting strings alphabetically
  4. Create a function that identifies if an array is already sorted in O(n) time

Algorithm Analysis Exercises

Analyze the performance of sorting algorithms:

  1. Compare the performance of the three algorithms on arrays of different sizes
  2. Measure the impact of initial array order (sorted, reverse sorted, random) on performance
  3. Analyze the best and worst-case scenarios for each algorithm
  4. Calculate the exact number of comparisons and swaps for a given input

Coding Challenges

Solve these sorting-related problems:

Advanced Problems

Challenge yourself with these advanced sorting problems:

  • Implement a hybrid sorting algorithm that uses Insertion Sort for small subarrays and another algorithm for larger arrays
  • Create a visualization tool that shows the sorting process step by step
  • Implement a custom comparator to sort objects based on multiple properties
  • Develop an algorithm to identify the k smallest/largest elements in an array without fully sorting it

Guided Practice

For additional hands-on practice and detailed exercises on sorting algorithms, check out our comprehensive guided project: