public static void bubbleSort(int[] A, int n){
for(int pass = n - 1; pass >= 0; pass--){
if(A[i] > A[i + 1]){
int temp = A[i];
A[i] = A[i + 1];
A[i + 1] = temp;
}
}
}Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Time Complexity:
- Best Case: O(n) – This occurs when the list is already sorted, as only one pass is needed to confirm that the list is sorted.
- Average Case: O(n^2) – For an average unsorted list, bubble sort requires quadratic time to sort n elements.
- Worst Case: O(n^2) – This occurs when the list is sorted in reverse order, as the maximum number of comparisons and swaps are required.
Space Complexity:
Bubble sort has a space complexity of O(1) since only a single additional memory space is required (for temporary storage during swaps).
Comparison with Selection Sort and Insertion Sort:
Bubble sort, selection sort, and insertion sort are all comparison-based sorting algorithms with similar average and worst-case time complexities. However, in practice, bubble sort tends to be less efficient than both selection sort and insertion sort due to its need for more swaps. Selection sort minimizes the number of swaps by only performing a single swap at the end of each pass, while insertion sort is efficient for small datasets and partially sorted arrays due to its adaptive nature.
In conclusion, while bubble sort is a straightforward algorithm to implement, it is generally less efficient than both selection sort and insertion sort, especially for larger datasets.
public static void selectionSort(int[] A, int n){
for(int i = 0; i < n - 1; i++){
int position = i;
for(int j = i + 1; j < n; j++){
if(A[j] < A[position]){
position = j;
}
int temp = A[i];
A[i] = A[position];
A[position] = temp;
}
}
}Selection sort is a comparison-based sorting algorithm that divides the input list into two parts: the sorted and the unsorted sub-lists. It iterates through the unsorted sub-list to find the smallest element and then swaps it with the first unsorted element. This process continues until the entire list is sorted.
Time Complexity:
- Best Case: O(n^2) – In the best case scenario, selection sort still requires quadratic time as it must iterate through the list to find the minimum element for each position.
- Average Case: O(n^2) – The average case time complexity of selection sort is quadratic, making it inefficient for larger datasets.
- Worst Case: O(n^2) – Similarly, the worst case time complexity of selection sort remains quadratic.
Space Complexity:
Selection sort has a space complexity of O(1) as it only requires a constant amount of additional space (for temporary storage during swaps).
Comparison with Bubble Sort and Insertion Sort:
Despite having similar time and space complexities, selection sort generally outperforms bubble sort due to its reduced number of swaps. Selection sort makes only a single swap at the end of each pass, which theoretically makes it more efficient than bubble sort. In contrast, insertion sort is particularly effective for small datasets and partially sorted arrays due to its adaptive nature, making it more efficient in those specific cases.
In conclusion, while selection sort, bubble sort, and insertion sort have similar time and space complexities, selection sort’s reduced number of swaps makes it more efficient than bubble sort in practice, particularly for larger datasets. However, for specific scenarios like small datasets or partially sorted arrays, insertion sort’s adaptive nature can make it a more suitable choice.
public static void insertionSort(int[] A, int n){
for(int i = 1; i < n; i++){
int temp = A[i];
int position = i;
while(position > 0 && A[position - 1] > temp)
{
A[position] = A[position - 1];
position = position - 1;
}
A[position] = temp;
}
}Insertion sort is a simple comparison-based sorting algorithm that builds the final sorted array (or list) one item at a time. It iterates through the input data, removing one element from the input data, finding its location within the sorted list, and inserting it. This process is repeated until the entire list is sorted.
Time Complexity:
- Best Case: O(n) – Occurs when the list is already sorted, resulting in linear time complexity as there are no or fewer comparisons and swaps needed.
- Average Case: O(n^2) – For an average unsorted list, insertion sort requires quadratic time to sort n elements.
- Worst Case: O(n^2) – This occurs when the list is sorted in reverse order, leading to the maximum number of comparisons and swaps.
Space Complexity:
Insertion sort has a space complexity of O(1) as it only requires a constant amount of additional space (for temporary storage during swaps).
Comparison with Bubble Sort and Selection Sort:
Insertion sort, while having similar time and space complexities to bubble sort and selection sort, possesses characteristics that make it more efficient in specific scenarios. It is particularly effective for small datasets and partially sorted arrays due to its adaptive nature, making it more efficient in those cases. However, in general, both bubble sort and selection sort tend to be less efficient than insertion sort, especially for larger datasets, due to their need for more swaps and iterations.
In conclusion, insertion sort’s adaptive nature makes it more suitable for small datasets and partially sorted arrays, while remaining a generally more efficient sorting algorithm than both bubble sort and selection sort, particularly for larger datasets.
Let's Talk Digital Transformation 