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
Try this exercise. Fill in the missing part by typing it in.
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 the previous screen, we took 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
Now, let's fill in the blank: The choice of sorting algorithm depends on ___.
Write the missing line below.
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:
- Start with the first element and compare it with the next element.
- If the next element is smaller, swap the two elements.
- Move to the next pair of elements and repeat step 2.
- Repeat steps 1-3 for the remaining elements.
- 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] + " ");
}
}
}
Are you sure you're getting this? Click the correct answer from the options.
What is the time complexity of Bubble Sort?
Click the option that best answers the question.
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
- Find the minimum element in the unsorted part.
- Swap the minimum element with the first element of the unsorted part.
- Increment the boundary of the sorted part.
- 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);
Let's test your knowledge. Click the correct answer from the options.
Which of the following statements about Selection Sort is true?
A. Selection Sort has a best-case time complexity of O(n) B. Selection Sort is an unstable sorting algorithm C. Selection Sort is a recursive sorting algorithm D. Selection Sort is the most efficient sorting algorithm
Click the option that best answers the question.
- A
- B
- C
- D
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
- Iterate from arr[1] to arr[n], where n is the length of the array.
- Compare the current element (key) with the element in the sorted subarray on the left.
- If the current element is smaller, shift the element to the right.
- Repeat step 3 until the correct position for the key is found.
- 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));
}
}
Try this exercise. Is this statement true or false?
The time complexity of Insertion Sort is O(n^2)
Press true if you believe the statement is correct, or false otherwise.
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:
- Divide: Divide the unsorted array into two halves, which are roughly of equal size.
- Conquer: Recursively sort the two halves using the Merge Sort algorithm.
- 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++;
Are you sure you're getting this? Fill in the missing part by typing it in.
Merge Sort is a popular sorting algorithm that follows the ___ approach. It divides the input array into smaller subarrays, sorts them recursively, and then merges the subarrays to produce the final sorted output.
Write the missing line below.
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
- 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.
- Sort: Recursively apply the Quick Sort algorithm to the sub-arrays.
- 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;
Are you sure you're getting this? Click the correct answer from the options.
Which of the following best describes the time complexity of Quick Sort?
Click the option that best answers the question.
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:
- Build a Max Heap from the input data.
- Swap the root node with the last node and remove the last node from the heap.
- Repeat steps 2 and 3 until the heap is empty.
- 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!
Try this exercise. Fill in the missing part by typing it in.
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It has a time complexity of O(n log n). The Heap Sort algorithm consists of the following steps:
- Build a ____ from the input data.
- Swap the root node with the last node and remove the last node from the heap.
- Repeat steps 2 and 3 until the heap is empty.
- Restore the heap property by comparing the swapped element with its children and swapping if necessary.
Write the missing line below.
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:
- Find the maximum element in the array to determine the number of digits in the largest number.
- For each digit position, from the least significant digit to the most significant digit, perform a counting sort on the array.
- 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) {
Build your intuition. Fill in the missing part by typing it in.
Radix Sort is a ___-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.
Write the missing line below.
Generating complete for this lesson!