Basic Sorting
Sorting algorithms are fundamental to computer science and are used to arrange elements in a specific order. This module covers the most common basic sorting algorithms, their implementations, and their time and space complexity analysis.
Module Contents
Introduction to Sorting
Sorting is the process of arranging elements in a specific order, typically in ascending or descending order. Sorting algorithms are essential in computer science and are used in various applications, from databases to search algorithms.
Why Study Sorting Algorithms?
- They demonstrate important algorithm design techniques
- They are used as building blocks in many other algorithms
- Different sorting algorithms have different trade-offs in terms of time and space complexity
- Understanding sorting algorithms helps in choosing the right one for specific use cases
Comparison of Basic Sorting Algorithms
| Algorithm | Best Case | Average Case | Worst Case | Space Complexity | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
Note: A stable sorting algorithm preserves the relative order of equal elements in the sorted output.
Bubble Sort
Bubble Sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
How Bubble Sort Works
- Start from the first element, compare it with the next element.
- If the current element is greater than the next element, swap them.
- Move to the next element and repeat steps 1-2 until the end of the array.
- After one complete pass, the largest element will be at the end of the array.
- Repeat steps 1-4 for all elements except the last sorted ones.
Java Implementation
// Bubble Sort implementation in Java
public void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
// Last i elements are already sorted
for (int j = 0; j < n - i - 1; j++) {
// Compare adjacent elements
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;
}
}
}Python Implementation
# Bubble Sort implementation in Python
def bubble_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
swapped = False
# Last i elements are already sorted
for j in range(0, n - i - 1):
# Compare adjacent elements
if arr[j] > arr[j + 1]:
# Swap the elements
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# If no swapping occurred in this pass, array is sorted
if not swapped:
break
return arrSelection Sort
Selection Sort is a simple sorting algorithm that divides the input list into two parts: a sorted sublist and an unsorted sublist. The algorithm repeatedly selects the smallest (or largest) element from the unsorted sublist and moves it to the end of the sorted sublist.
How Selection Sort Works
- Find the minimum element in the unsorted part of the array.
- Swap it with the element at the beginning of the unsorted part.
- Move the boundary between the sorted and unsorted parts one element to the right.
- Repeat steps 1-3 until the entire array is sorted.
Java Implementation
// Selection Sort implementation in Java
public void selectionSort(int[] arr) {
int n = arr.length;
// One by one move boundary of unsorted subarray
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;
}
}Python Implementation
# Selection Sort implementation in Python
def selection_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Find the minimum element in remaining unsorted array
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap the found minimum element with the first element
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arrInsertion 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, but it has several advantages: it is simple to implement, efficient for small data sets, and more efficient than other simple quadratic algorithms like selection sort or bubble sort.
How Insertion Sort Works
- Start with the second element (index 1) of the array.
- Compare it with the elements before it and insert it at the correct position in the sorted part.
- Move to the next element and repeat step 2 until the entire array is sorted.
Java Implementation
// Insertion Sort implementation in Java
public 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;
}
}Python Implementation
# Insertion Sort implementation in Python
def insertion_sort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are greater than key,
# to one position ahead of their current position
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arrMerge Sort
Merge Sort is an efficient, stable, comparison-based, divide and conquer sorting algorithm. It divides the input array into two halves, recursively sorts them, and then merges the sorted halves to produce a sorted output.
How Merge Sort Works
- Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining.
Java Implementation
// Merge Sort implementation in Java
public void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// Find the middle point
int mid = left + (right - left) / 2;
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
private void merge(int[] arr, int left, int mid, int right) {
// Find sizes of two subarrays to be merged
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temp arrays
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data to temp arrays
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];
}
// Merge the temp arrays
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray
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++;
}
// Copy remaining elements of L[] if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}Python Implementation
# Merge Sort implementation in Python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # Finding the mid of the array
L = arr[:mid] # Dividing the array elements into 2 halves
R = arr[mid:]
merge_sort(L) # Sorting the first half
merge_sort(R) # Sorting the second half
i = j = k = 0
# Copy data to temp arrays L[] and R[]
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
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return arrInteractive Sorting Visualization
Visualizing sorting algorithms helps in understanding how they work. Use the interactive visualization below to see the algorithms in action.
Sorting Algorithms
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Explanation:
Click play or step to start the visualization.
Use the controls above to select different sorting algorithms, adjust the array size, and control the visualization speed. The visualization shows each step of the algorithm, helping you understand how elements are compared and swapped.
Practice Problems
Apply your knowledge of sorting algorithms by solving these carefully selected problems:
1. Sort an Array
Implement a sorting algorithm to sort an array of integers in ascending order.
2. Merge Sorted Array
Merge two sorted arrays into a single sorted array.
3. Sort Colors
Sort an array of 0s, 1s, and 2s in-place (Dutch National Flag problem).
4. Insertion Sort List
Sort a linked list using insertion sort.