• SORT
  • Approaches and Complexities of 3 Sorting Algorithms
    • Selection Sort
    • Bubble Sort
    • Insertion Sort
  • Practical Operations of Three Sorting Algorithms
    • Selection Sort
    • Bubble Sort
    • Insertion Sort

SORT

Approaches and Complexities of 3 Sorting Algorithms

Selection Sort

1.Algorithmic Approach of Selection Sort

In selection sort, we choose the smallest element from the unsorted sub-array and append it to the end of the sorted sub-array. We repeat this process until all elements are sorted.

2.Time and Space Complexity of Selection Sort

Selection sort has a time complexity of O(n^2), which makes it inefficient for sorting large datasets. However, its space complexity is small, only O(1), making it suitable for cases where memory is limited.

Bubble Sort

1.Algorithmic Approach of Bubble Sort

Bubble sort compares adjacent elements in the unsorted sub-array and swaps them if the first element is greater than the second element. We repeat this process until all elements are sorted.

2.Time and Space Complexity of Bubble Sort

Bubble sort also has a time complexity of O(n^2), but if the sequence is already sorted, bubble sort can finish early and have a time complexity of O(n).

Insertion Sort

1.Algorithmic Approach of Insertion Sort

Insertion sort divides the unsorted array into sorted and unsorted sub-arrays. We take each element from the unsorted sub-array and insert it into the correct position in the sorted sub-array. We repeat this process until all elements are sorted.

2.Time and Space Complexity of Insertion Sort

Insertion sort has a time complexity of O(n^2), but if the sequence is already sorted or mostly sorted, the efficiency of insertion sort is higher than that of selection sort or bubble sort. Furthermore, its space complexity is also small, only O(1).

Practical Operations of Three Sorting Algorithms

Take the array [3, 5, 1, 4, 2] as an example.

Selection Sort

1. In the first round of sorting, find the smallest element 1 and put it in the first position. The array of elements at this time is [1, 5, 3, 4, 2].
2. In the second round of sorting, find the smallest element 2 in the unsorted array and put it at the end of the sorted array. The array of elements at this time is [1, 2, 3, 4, 5].

Bubble Sort

1. First pass: Compare adjacent elements 3 and 5, find that 3 is smaller than 5, so no swap is made. The array now is [3, 5, 1, 4, 2]. Then compare 5 and 1, find that 5 is larger than 1, swap their positions, and the array now is [3, 1, 5, 4, 2]. Next, compare 5 and 4, find that 5 is larger than 4, swap their positions, and the array now is [3, 1, 4, 5, 2]. Finally, compare 5 and 2, find that 5 is larger than 2, swap their positions, and the array now is [3, 1, 4, 2, 5].
2. Second pass: Compare adjacent elements 3 and 1, find that 3 is larger than 1, swap their positions, and the array now is [1, 3, 4, 2, 5]. Then compare 4 and 2, find that 4 is larger than 2, swap their positions, and the array now is [1, 3, 2, 4, 5].
3. Third pass: Compare adjacent elements 1 and 3, find that 1 is smaller than 3, so no swap is made. The array now is [1, 3, 2, 4, 5]. Then compare 3 and 2, find that 3 is larger than 2, swap their positions, and the array now is [1, 2, 3, 4, 5].

Insertion Sort

1. First round of sorting: The sorted part only contains one element, which is 3. The unsorted part includes [5, 1, 4, 2]. [3]

   5 1 4 2;

2. Second round of sorting: Take the first element 5 from the unsorted part and compare it with the elements in the sorted part. We find that 5 is greater than 3, so we insert it after 3 in the sorted part. Now the sorted part is [3, 5] and the unsorted part is [1, 4, 2]. [3 5]

   1 4 2;

3. Third round of sorting: Take the first element 1 from the unsorted part and insert it into the sorted part. First, compare it with the last element 5 in the sorted part. We find that 1 is smaller than 5, so we insert it before 5. Then compare it with the first element 3 in the sorted part. We find that 1 is smaller than 3, so we insert it before 3. Now the sorted part is [1, 3, 5] and the unsorted part is [4, 2]. [1 3 5]

   4 2;

4. Fourth round of sorting: Take the first element 4 from the unsorted part and insert it into the sorted part. First, compare it with the last element 5 in the sorted part. We find that 4 is smaller than 5, so we insert it before 5. Then compare it with the second element 3 in the sorted part. We find that 4 is greater than 3, so we insert it after 3. Now the sorted part is [1, 3, 4, 5] and the unsorted part is [2]. [1 3 4 5]

   2;

5. Fifth round of sorting: Insert the first element 2 from the unsorted part into the sorted part. Since 2 is smaller than 5, we insert it before 5. At the same time, 2 is also smaller than 3, so we insert it before 3. Finally, 2 is also smaller than 4, so we insert it before 4. Now the sorted part becomes [1, 2, 3, 4, 5] and the unsorted part is empty. [1 2 3 4 5]

   .