In the first part of our exploration of data structures and algorithms, we learned that using a sorted array provides us with greater flexibility when it comes to tasks like finding, changing, or deleting elements. This becomes valuable when dealing with many elements, which are common in our daily activities. Since these actions are frequently used, it is essential to take some time to discuss sorting algorithms, especially when dealing with unordered arrays.
The article will be structured as follows:
How Would You Do It?
Bubble Sort
Selection Sort
Insertion Sort
How Would You Do It?
As a person, you have advantages over a computer program. You can look at all the kids at once and quickly pick out the tallest one without needing to measure and compare each one.
After some informal repositioning, you can easily arrange all the kids in a line, as shown in the illustration.
However, a computer program cannot process data in the same way. It can only compare two kids at a time due to how comparison operators work. This limited perspective is a common theme in algorithms. While things might seem straightforward to humans, algorithms cannot see the overall picture. Instead, they focus on specific details and follow straightforward rules.
The three algorithms in this chapter follow two steps repeatedly until the data is sorted
Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through a list of elements and compares adjacent items, swapping them if they are in the wrong order. It is called “Bubble Sort” because smaller elements “bubble” to the top of the list while larger elements “sink” to the bottom.
Here’s how Bubble Sort works:
- Start by comparing the first two elements of the list. If the first element is greater than the second, swap them.
- Move to the next pair of elements and compare them. Again, swap if necessary.
- Continue this process for the entire list, repeatedly comparing and swapping adjacent elements until no more swaps are needed.
- After one pass through the list, the largest element will have “bubbled up” to the last position. Repeat the process for the remaining unsorted elements.
- Keep repeating steps 1–4 until the entire list is sorted.
Bubble Sort is easy to understand and implement, but it is not very efficient for large lists. Its average and worst-case time complexity is O(n²), where “n” is the number of elements in the list. This makes it impractical for sorting large datasets. However, it can be an excellent choice for small lists or as a learning exercise to understand sorting algorithms.
Selection Sort
Selection Sort is a simple sorting algorithm that works by repeatedly selecting the minimum (or maximum) element from the unsorted part of the array and placing it at the beginning (or end) of the sorted part. It has a time complexity of O(n²) for average and worst-case scenarios, making it inefficient for large lists.
Here is how the Selection Sort algorithm works:
- Find the minimum (or maximum) element in the unsorted part of the array.
- Swap it with the first element of the unsorted part.
- Repeat the above steps for the remaining unsorted part of the array, excluding the element that was just placed in the sorted part.
Selection Sort is called so because it “selects” the smallest (or largest) element and “bubbles” it up to its correct position in the sorted part of the array. Despite its simplicity, Selection Sort is not efficient for large arrays due to its quadratic time complexity.
Unlike some other sorting algorithms, like Bubble Sort, Selection Sort does not continuously exchange elements as it scans the array. This characteristic can be advantageous in situations where swapping elements is costly.
Insertion Sort
Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is a comparison-based sorting algorithm where the array is divided into a sorted and an unsorted part. In each iteration, the algorithm takes an element from the unsorted part and inserts it into its correct position within the sorted part.
Here’s how Insertion Sort works:
- Start with the second element (index 1) and compare it with the first element (index 0).
- If the second element is smaller (or larger, depending on the sorting order) than the first element, swap them.
- Move to the third element (index 2) and compare it with the previous elements in the sorted part. Insert it at the correct position within the sorted part by shifting larger elements to the right.
- Repeat the process for the remaining unsorted elements, each time inserting the current element into its correct position within the sorted part.
Insertion Sort is efficient for small datasets or partially sorted arrays. It has a linear time complexity of O(n) for sorted arrays. However, its worst-case time complexity is quadratic, making it less suitable for large arrays.
In summary, Insertion Sort is a straightforward sorting algorithm that is easy to understand and implement. While it may not be the most efficient choice for large datasets, it can be a practical option for small or sorted arrays.
