What is Sorting?
Sorting is the process of arranging data in a particular order or sequence, typically either ascending (from smallest to largest) or descending (from largest to smallest). The goal of sorting is to simplify searching, make the data easier to analyze, and improve overall performance in some algorithms.
There are various sorting algorithms to sort data, and they vary in terms of their approach, efficiency, and usage. Two basic and commonly known sorting algorithms are Selection Sort and Bubble Sort.
1. Selection Sort
Selection Sort is an in-place comparison-based algorithm. It works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and swapping it with the first unsorted element. It keeps selecting the next smallest (or largest) element until the entire array is sorted.
Steps of Selection Sort:
Start with the first element of the list.
Find the smallest element in the unsorted portion of the list.
Swap this smallest element with the first unsorted element.
Move to the next unsorted element and repeat the process until the entire list is sorted.
Example:
Let’s consider an example where we sort an array of numbers in ascending order: [64, 25, 12, 22, 11].
Initial Array: [64, 25, 12, 22, 11]
Pass 1:
Find the smallest element in the array (11).
Swap 11 with 64.
New array: [11, 25, 12, 22, 64]
Pass 2:
Find the smallest element in the unsorted part [25, 12, 22, 64] (12).
Swap 12 with 25.
New array: [11, 12, 25, 22, 64]
Pass 3:
Find the smallest element in [25, 22, 64] (22).
Swap 22 with 25.
New array: [11, 12, 22, 25, 64]
Pass 4:
Find the smallest element in [25, 64] (25).
No swap needed.
Final array: [11, 12, 22, 25, 64]
Sorted Array: [11, 12, 22, 25, 64]
Time Complexity:
Best, Worst, and Average Case: O(n²)
Selection sort is inefficient on large lists and generally performs worse than the optimized algorithms like Merge Sort or Quick Sort.
2. Bubble Sort
Bubble Sort is another simple comparison-based sorting algorithm. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The algorithm “bubbles” the largest element to the end of the list after each full pass through the array. This process continues until the list is sorted.
Steps of Bubble Sort:
Compare the first two elements of the list.
If the first element is larger than the second, swap them.
Move to the next pair of elements and repeat step 2.
After completing a full pass through the list, the largest element will have “bubbled” to the last position.
Repeat the process for the remaining unsorted elements until the entire list is sorted.
Example:
Let’s consider an example with the same array: [64, 25, 12, 22, 11].
Initial Array: [64, 25, 12, 22, 11]
Pass 1:
Compare 64 and 25: Swap → [25, 64, 12, 22, 11]
Compare 64 and 12: Swap → [25, 12, 64, 22, 11]
Compare 64 and 22: Swap → [25, 12, 22, 64, 11]
Compare 64 and 11: Swap → [25, 12, 22, 11, 64] (Largest element 64 is now in its correct place)
Pass 2:
Compare 25 and 12: Swap → [12, 25, 22, 11, 64]
Compare 25 and 22: Swap → [12, 22, 25, 11, 64]
Compare 25 and 11: Swap → [12, 22, 11, 25, 64] (Largest element 25 is now in its correct place)
Pass 3:
Compare 12 and 22: No swap → [12, 22, 11, 25, 64]
Compare 22 and 11: Swap → [12, 11, 22, 25, 64] (Largest element 22 is now in its correct place)
Pass 4:
Compare 12 and 11: Swap → [11, 12, 22, 25, 64] (Now the list is sorted)
Sorted Array: [11, 12, 22, 25, 64]
Time Complexity:
Best Case (Already Sorted): O(n)
Worst and Average Case: O(n²)
Bubble sort is generally inefficient for large datasets, though it can perform well when the data is already mostly sorted.
Comparison of Selection Sort and Bubble Sort:
Selection Sort:
Always performs O(n²) comparisons.
Fewer swaps compared to Bubble Sort, as it only swaps once for each pass.
Bubble Sort:
More swaps than Selection Sort, as it may swap elements multiple times in a single pass.
Best case (already sorted) time complexity can be O(n) if optimized.
In summary, both Selection Sort and Bubble Sort are simple algorithms, but neither is suitable for large datasets due to their O(n²) time complexity.
