Sorting algorithms are often among the first topics introduced in computer science, as they provide a foundational understanding of algorithmic behavior and efficiency, which is essential for solving a wide range of computational problems. In this post, we will visualize three classic sorting algorithms — Bubble Sort, Insertion Sort, and Selection Sort — to understand their sorting process.
Brief Overview of Sorting Algorithms
Sorting algorithms arrange elements in a specific order, such as ascending or descending. They are widely used in various applications, including data analysis, search optimization, and database indexing.
Basic Sorting Algorithms
- Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order. After each iteration, the largest unsorted element ‘bubbles up’ to its correct position.
- Insertion Sort: Builds the sorted array one element at a time by inserting each element into its correct position in the sorted part.
- Selection Sort: Repeatedly selects the smallest element from the unsorted part of the array and swaps it with the first unsorted element.
Key Takeaways:
- Visualizing sorting algorithms helps in understanding their internal working.
- Comparing their performance for different data distributions (e.g., random, sorted, or reverse-sorted arrays), provides a more detailed overview of these algorithms.
- Visualizing helps recognize patterns in the sorting process, such as the bubbling effect in Bubble Sort.
Bubble Sort
void bubbleSort (int arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j + 1] < arr[j]) {
swap (arr[j], arr[j + 1]);
}
}
}
}
In Bubble Sort, each iteration involves comparing adjacent elements and swapping them if they are in the wrong order. After each complete iteration through the array, the largest unsorted element moves to its correct position, and the sorted portion grows from right to left.
The visual representation of this process shows how the unsorted portion of the array shrinks with each iteration, and how the largest elements move to their correct positions in sequence. However, the algorithm is generally inefficient due to the repeated comparisons and swaps, making it unsuitable for large datasets.
Explanation
- The algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order.
- As a result, the largest element gradually “bubbles up” to its correct position at the end of the array.
- After each iteration, the largest element among the unsorted portion is in its correct position, and the size of the unsorted portion reduces by one, while the sorted portion at the end grows by one.
- The process continues until the entire array is sorted.
Insertion Sort
void insertionSort (int arr[], int n) {
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;
}
}
Insertion Sort builds the sorted portion of the array one element at a time. It starts with the first element as the sorted portion and then takes the next unsorted element, inserting it into its correct position within the sorted portion. At each iteration, Insertion sort selects one element from the unsorted portion and places it in its correct position within the sorted portion. This process continues until all elements are sorted.
This involves shifting all larger elements to the right until the correct spot is found. The sorted portion expands gradually and elements are inserted into their correct positions. This process is particularly efficient for small or nearly sorted datasets, as the number of shifts required is less.
Explanation
- The algorithm iterates through the array, treating the first elements as sorted. It starts with the second element (index 1) which is considered the first “unsorted” element.
- Each unsorted element is compared with the elements in the sorted portion of the array.
- For each unsorted element of the current iteration, the algorithm “copies/shifts” elements larger than this element in the sorted portion to the right to make space for this new unsorted element.
- Starting from the last (rightmost) element of the sorted portion, the algorithm compares the current unsorted element with elements in the sorted portion moving from right to left.
- Elements are copied/shifted rightward until the correct position is found, and the unsorted element is then inserted into this position.
- As the process continues, the sorted portion grows, eventually sorting the entire array.
Selection Sort
void selectionSort (int arr[], int n) {
for (int i = 0; i < n; i++) {
int indexMin = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[indexMin]) {
indexMin = j;
}
}
if (indexMin != i) {
swap (arr[indexMin], arr[i]);
}
}
}
Selection Sort works by repeatedly finding the smallest element from the unsorted portion of the array and placing it in the sorted section. As a result, the sorted portion grows from left to right. Selection Sort performs fewer swaps compared to Bubble Sort since it swaps only once per iteration — when the smallest element is placed in its correct position. However, it is still inefficient for large datasets due to the repeated scans of the unsorted portion. The visual representation helps in understanding how the smallest elements are selected and moved to their correct positions in each iteration.
Explanation
- The algorithm divides the array into a sorted portion on the left and an unsorted portion on the right.
- It iteratively selects the smallest element from the unsorted portion and places it in its correct position in the sorted portion.
- Once the smallest element is located, it is swapped with the current element in the unsorted portion. Thus, at each step, the smallest remaining element is moved to its correct position.
- The sorted portion of the array gradually grows from left to right, eventually sorting the entire array.
Note: Unlike Optimized Bubble Sort and Insertion Sort, Selection Sort is not adaptive, meaning it will perform the same number of comparisons regardless of the initial order of the elements.
By visualizing these algorithms, you can better appreciate their working.
While Bubble Sort, Insertion Sort, and Selection Sort are easy to understand, their O(n2) worst case time complexity makes them impractical for large datasets. For practical applications, more efficient algorithms like Merge Sort, Quick Sort, or Timsort should be used.