Introduction to Sorting Algorithms

Sorting algorithms are fundamental tools in computer science and programming. They allow us to arrange elements in a specific order, making it easier to search, analyze, and manipulate data. In simple terms, a sorting algorithm is like a recipe for organizing a collection of elements such as numbers or strings.

There are various sorting algorithms, each with its own approach and characteristics. Some algorithms rely on comparing elements with each other, while others use different techniques to achieve sorting. The choice of algorithm depends on the specific requirements of the problem at hand.

In this lesson, we will explore different sorting algorithms, analyze their time and space complexity, and discuss their best use cases. We will cover popular algorithms such as bubble sort, selection sort, insertion sort, merge sort, quick sort, heap sort, and radix sort.

To get started, let's take a look at a high-level overview of these sorting algorithms in Java:

1// Sorting Algorithms
2
3// Bubble Sort
4
5// Selection Sort
6
7// Insertion Sort
8
9// Merge Sort
10
11// Quick Sort
12
13// Heap Sort
14
15// Radix Sort

xxxxxxxxxx

// Sorting Algorithms

​

// Bubble Sort

​

// Selection Sort

​

// Insertion Sort

​

// Merge Sort

​

// Quick Sort

​

// Heap Sort

​

// Radix Sort

Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order. Each pass of the algorithm iterates through the array and pushes the largest element to the end. This process is repeated until the array is fully sorted.

Algorithm Steps:

1. Start with the first element and compare it with the next element.
2. If the next element is smaller, swap the two elements.
3. Move to the next pair of elements and repeat step 2.
4. Repeat steps 1-3 for the remaining elements.
5. The largest element will move to the end in each pass, so the number of iterations is equal to the number of elements minus one.

Time Complexity

The time complexity of Bubble Sort is O(n^2) in the worst and average cases, where n is the number of elements in the array. This is because in each pass, we have to compare all adjacent pairs of elements. However, in the best case where the array is already sorted, the time complexity is O(n).

Example

Let's see an implementation of Bubble Sort in Java:

1${code}

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // Bubble Sort Algorithm

    int[] arr = {5, 2, 8, 12, 7};

    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 elements

          int temp = arr[j];

          arr[j] = arr[j + 1];

          arr[j + 1] = temp;

        }

      }

    }

​

    // Print sorted array

    for (int i = 0; i < n; i++) {

      System.out.print(arr[i] + " ");

    }

  }

}

Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It works by dividing the input list into two parts: the sorted part and the unsorted part. Initially, the sorted part is empty, and the unsorted part contains all the elements. The algorithm repeatedly selects the smallest element from the unsorted part and moves it to the sorted part.

Steps of Selection Sort

1. Find the minimum element in the unsorted part.
2. Swap the minimum element with the first element of the unsorted part.
3. Increment the boundary of the sorted part.
4. Repeat steps 1-3 until the entire array is sorted.

Time Complexity

The time complexity of Selection Sort is O(n^2) in all cases, where n is the number of elements in the array. This is because the algorithm involves two nested loops, resulting in quadratic time complexity. Selection Sort is not efficient for large data sets.

Example

Let's see an implementation of Selection Sort in Java:

1${code}

xxxxxxxxxx

}

public class SelectionSort {

​

    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;

                }

            }

            int temp = arr[minIndex];

            arr[minIndex] = arr[i];

            arr[i] = temp;

        }

    }

​

    public static void printArray(int[] arr) {

        for (int i = 0; i < arr.length; i++) {

            System.out.print(arr[i] + " ");

        }

        System.out.println();

    }

​

    public static void main(String[] args) {

        int[] arr = {64, 25, 12, 22, 11};

        System.out.println("Array before sorting:");

        printArray(arr);

        selectionSort(arr);

Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages in certain scenarios. It has an average and worst-case time complexity of O(n^2).

Algorithm

The algorithm works by dividing the input array into a sorted subarray and an unsorted subarray. At each iteration, the next element in the unsorted subarray is picked and inserted into its correct position in the sorted subarray. This process continues until the entire array is sorted.

Steps of Insertion Sort

1. Iterate from arr[1] to arr[n], where n is the length of the array.
2. Compare the current element (key) with the element in the sorted subarray on the left.
3. If the current element is smaller, shift the element to the right.
4. Repeat step 3 until the correct position for the key is found.
5. Insert the key into its correct position in the sorted subarray.

Example

Let's see an implementation of Insertion Sort in Java:

1${code}

xxxxxxxxxx

import java.util.Arrays;

​

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;

​

            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 = {64, 34, 25, 12, 22, 11, 90};

        insertionSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));

    }

}

Merge Sort

Merge Sort is a popular sorting algorithm that follows the Divide and Conquer approach. It divides the input array into smaller subarrays, sorts them recursively, and then merges the subarrays to produce the final sorted output.

Algorithm

The Merge Sort algorithm can be summarized in three steps:

1. Divide: Divide the unsorted array into two halves, which are roughly of equal size.
2. Conquer: Recursively sort the two halves using the Merge Sort algorithm.
3. Combine: Merge the two sorted halves to produce the final sorted array.

Time Complexity

Merge Sort has a time complexity of O(n log n) in all three cases: best case, average case, and worst case. This makes it an efficient sorting algorithm for large data sets.

Space Complexity

Merge Sort has a space complexity of O(n), as it requires additional space to store the temporary subarrays during the merging process.

Example

Let's see an implementation of Merge Sort in Java:

1${code}

In this example, we have an array of integers arr and we first print the original array. Then, we apply the Merge Sort algorithm to sort the array in ascending order and print the sorted array.

Output:

1Original Array:
210 7 8 9 1 5 
3Sorted Array:
41 5 7 8 9 10 

xxxxxxxxxx

}

class MergeSort {

​

    public static void merge(int[] arr, int left, int mid, int right) {

        int n1 = mid - left + 1;

        int n2 = right - mid;

​

        int[] L = new int[n1];

        int[] R = new int[n2];

​

        for (int i = 0; i < n1; i++) {

            L[i] = arr[left + i];

        }

        for (int j = 0; j < n2; j++) {

            R[j] = arr[mid + 1 + j];

        }

​

        int i = 0;

        int j = 0;

        int k = left;

​

        while (i < n1 && j < n2) {

            if (L[i] <= R[j]) {

                arr[k] = L[i];

                i++;

            } else {

                arr[k] = R[j];

                j++;

            }

            k++;

Quick Sort

Quick Sort is an efficient, comparison-based sorting algorithm that falls under the Divide and Conquer category. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This process is repeated for each sub-array until the entire array is sorted. The pivot selection and partitioning steps make Quick Sort faster than other sorting algorithms.

Algorithm

1. Partition: Select a pivot element and partition the array into two sub-arrays, one with elements less than the pivot and the other with elements greater than the pivot.
2. Sort: Recursively apply the Quick Sort algorithm to the sub-arrays.
3. Combine: The final sorted array is obtained by combining the sorted sub-arrays.

Time Complexity

The time complexity of Quick Sort depends on the choice of pivot. In the average case, Quick Sort has a time complexity of O(n log n), where n is the number of elements to be sorted. However, in the worst case, Quick Sort has a time complexity of O(n^2). To mitigate the effect of the worst-case scenario, various techniques, such as choosing a random pivot or using the Median of Three method, can be employed.

Space Complexity

Quick Sort has a space complexity of O(log n) for the recursive call stack. However, the sorting is done in-place, so the overall space complexity is O(1).

Example

1${code}

In this example, we have an array of integers arr and we first print the original array. Then, we apply the Quick Sort algorithm to sort the array in ascending order and print the sorted array.

Output:

1Original Array:
28 4 2 7 1 5 9 
3Sorted Array:
41 2 4 5 7 8 9 

xxxxxxxxxx

}

class QuickSort {

  public static void quickSort(int[] arr, int low, int high) {

    if (low < high) {

      int pivotIndex = partition(arr, low, high);

      quickSort(arr, low, pivotIndex - 1);

      quickSort(arr, pivotIndex + 1, high);

    }

  }

​

  public static int partition(int[] arr, int low, int high) {

    int pivot = arr[high];

    int i = low - 1;

​

    for (int j = low; j < high; j++) {

      if (arr[j] < pivot) {

        i++;

        swap(arr, i, j);

      }

    }

​

    swap(arr, i + 1, high);

​

    return i + 1;

  }

​

  public static void swap(int[] arr, int i, int j) {

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It is an in-place algorithm and has a time complexity of O(n log n), making it efficient for large datasets.

Algorithm

The Heap Sort algorithm consists of the following steps:

1. Build a Max Heap from the input data.
2. Swap the root node with the last node and remove the last node from the heap.
3. Repeat steps 2 and 3 until the heap is empty.
4. Restore the heap property by comparing the swapped element with its children and swapping if necessary.

Example

To demonstrate the Heap Sort algorithm, consider the following array of integers:

1int[] arr = {4, 10, 3, 5, 1};

Step 1: Build a Max Heap

In the first step, we build a max heap from the given array. The max heap is represented as an array with the following values:

1{10, 5, 3, 4, 1}

Step 2: Swap and Remove the Root Node

Next, we swap the root node (the largest element) with the last node and remove the last node from the heap. After the first swap and removal, the heap becomes:

1{5, 4, 3, 1}

Step 3: Repeat Swapping and Removal

We repeat the swapping and removal process until the heap is empty. After each iteration, the largest element is moved to the end of the array. The sorted array at each step is as follows:

1{1, 5, 3, 4}
2{1, 4, 3}
3{1, 3}
4{1}

Step 4: Restore the Heap Property

After the sorting process, we restore the heap property by comparing the swapped element with its children and swapping if necessary. The final sorted array is:

1{1, 3, 4, 5, 10}

Java Implementation

Here is a Java implementation of the Heap Sort algorithm:

1${code}

xxxxxxxxxx

```java

xxxxxxxxxx

Let's continue on the next screen!

​

Radix Sort

Radix Sort is a non-comparison-based sorting algorithm that sorts integers by grouping them by individual digits and sorting from least significant digit (LSD) to most significant digit (MSD). It has a time complexity of O(kn), where k is the number of digits in the largest number and n is the number of elements to be sorted.

Algorithm

The Radix Sort algorithm consists of the following steps:

1. Find the maximum element in the array to determine the number of digits in the largest number.
2. For each digit position, from the least significant digit to the most significant digit, perform a counting sort on the array.
3. Repeat step 2 for all digits, starting from the least significant digit to the most significant digit.

Example

To demonstrate the Radix Sort algorithm, consider the following array of integers:

1int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

Step 1: Find the maximum element

The maximum element in the array is 802, so the number of digits in the largest number is 3.

Step 2: Perform counting sort on each digit position

• For the least significant digit (1's place):

  • Counting sort: [170, 90, 802, 2, 24, 45, 75, 66]

• For the tens place:

  • Counting sort: [802, 2, 24, 45, 66, 170, 75, 90]

• For the hundreds place:

  • Counting sort: [2, 24, 45, 66, 75, 90, 170, 802]

Step 3: The array is now sorted

The sorted array is [2, 24, 45, 66, 75, 90, 170, 802].

Java Implementation

Here is a Java implementation of the Radix Sort algorithm:

1${code}

xxxxxxxxxx

}

class Main {

  public static void main(String[] args) {

    int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

    radixSort(arr);

    System.out.println("Sorted Array:");

    for (int i : arr) {

      System.out.print(i + " ");

    }

  }

​

  public static void radixSort(int[] arr) {

    int max = getMax(arr);

​

    for (int exp = 1; max / exp > 0; exp *= 10) {

      countSort(arr, exp);

    }

  }

​

  public static int getMax(int[] arr) {

    int max = arr[0];

    for (int i = 1; i < arr.length; i++) {

      if (arr[i] > max) {

        max = arr[i];

      }

    }

    return max;

  }

​

  public static void countSort(int[] arr, int exp) {