Difference Between Bubble Sort and Selection Sort
Definition
Bubble sort is a simple sorting algorithm that continuously steps through the list and compares the adjacent pairs to sort the elements. In contrast, selection sort is a sorting algorithm that takes the smallest value (considering ascending order) in the list and moves it to the proper position in the array. Thus, this is the main difference between bubble sort and selection sort.
Functionality
Bubble sort compares the adjacent elements and swap accordingly while selection sort selects the minimum element from the unsorted sub-array and places it at the next position of the sorted subarray.
Efficiency
Furthermore, another difference between bubble sort and selection sort is that the selection sort is efficient compared to the bubble sort.
Speed
Also, speed is another difference between bubble sort and selection sort. Selection sort is faster compared to bubble sort.
Method
Moreover, one other difference between bubble sort and selection sort is that the bubble sort uses item exchanging while selection sort uses item selection.
Sorting is one of the major task in computer programs in which the elements of an array are arranged in some particular order. Sorting makes searching easier. Bubble sort and Selection sort are the sorting algorithms which can be differentiated through the methods they use for sorting. Bubble sort essentially exchanges the elements whereas selection sort performs the sorting by selecting the element.
Another considerable difference between the two is that bubble sort is stable algorithm while selection sort is an unstable algorithm. An algorithm is considered to be steady the elements with the same key occurring in the same order as they were occurring before sorting in the list or array. Generally, most stable and fast algorithms use additional memory.
Content: Bubble Sort Vs Selection Sort
- Comparison Chart
- Definition
- Key Differences
- Conclusion
Comparison Chart
| BASIS FOR COMPARISON | BUBBLE SORT | SELECTION SORT |
|---|---|---|
| Basic | Adjacent element is compared and swapped | Largest element is selected and swapped with the last element (in case of ascending order). |
| Best case time complexity | O(n) | O(n2) |
| Efficiency | Inefficient | Improved efficiency as compared to bubble sort |
| Stable | Yes | No |
| Method | Exchanging | Selection |
| Speed | Slow | Fast as compared to bubble sort |
Definition of Bubble Sort
Bubble sort is the simplest iterative algorithm operates by comparing each item or element with the item next to it and swapping them if needed. In simple words, it compares the first and second element of the list and swaps it unless they are out of specific order. Similarly, Second and third element are compared and swapped, and this comparing and swapping go on to the end of the list.
The number of comparisons in the first iteration are n-1 where n is the number elements in an array. The largest element would be at nth position after the first iteration. And after each iteration, the number of comparisons decreases and at last iteration only one comparison takes place.
This algorithm is the slowest sorting algorithm. The best case complexity (When the list is in order) of the Bubble sort is of order n (O(n)), and worst case complexity is O(n2). In the best case, it is of order n because it just compares the elements and doesn’t swap them. This technique also requires additional space to store the temporary variable.
Definition of Selection Sort
Selection sort has achieved slightly better performance and is efficient than bubble sort algorithm. Suppose we want to arrange an array in ascending order then it functions by finding the largest element and exchanging it with the last element, and repeat the following process on the sub-arrays till the whole list is sorted.
In selection sort, the sorted and unsorted array doesn’t make any difference and consumes an order of n2 (O(n2)) in both best and worst case complexity. Selection sort is faster than Bubble sort.
Next Example
What is Selection Sort
Selection sort is a sorting algorithm that sorts the elements in increasing order. After finding the smallest element in the unsorted part of the array, it swaps that element with the first position in the list.
An example is as follows.
7 8 5 4 9 2
We take the minimum value as 7. We check the value 8. It is not less than 7. So, we check 5. It is less than 7. Now, the minimum value is 5. Now, consider 4. It is less than the minimum value (5). Therefore, now the minimum value is 4. Next, we consider the number 9. It is not less than the current minimum value (4). So, we move to the next element, which is 2. It is less than the current minimum value (4). Now the minimum value is 2. We can swap 7 and 2. Now the list is as follows.
2 8 5 4 9 7
Now, 2 is already sorted, and it is the smallest number in the list. The rest is the unsorted list. We should now sort 8 5 4 9 7. We consider 8 as the minimum value. The value 5 is less than the minimum value (8). So, now the minimum value is 5. Then, value 4 is less than the minimum value. Now the minimum value is 4. Then 9 is not less than minimum value 4. Therefore, we consider the next element 7. It is not less than minimum value 4. Now the minimum is 4. Therefore, we swap the value 4 and value 8 (1st element in the list). Now the list is as follows.
2 4 5 8 9 7
Now, 2 and 4 are sorted. We can sort 5 8 9 7. We consider 5 as the minimum value and repeat the above process and obtain a sorted list at the end.
Key Differences Bubble Sort and Selection Sort
- In the bubble sort, each element and its adjacent element is compared and swapped if required. On the other hand, selection sort works by selecting the element and swapping that particular element with the last element. The selected element could be largest or smallest depending on the order i.e., ascending or descending.
- The worst case complexity is same in both the algorithms, i.e., O(n2), but best complexity is different. Bubble sort takes an order of n time whereas selection sort consumes an order of n2 time.
- Bubble sort is a stable algorithm, in contrast, selection sort is unstable.
- Selection sort algorithm is fast and efficient as compared to bubble sort which is very slow and inefficient.
Conclusion
In summary, the main difference between bubble sort and selection sort is that the bubble sort operates by repeatedly swapping the adjacent elements if they are in the wrong order. In contrast, selection sort sorts an array by repeatedly finding the minimum element from the unsorted part and placing that at the beginning of the array.
What is Bubble Sort
Bubble sort is a sorting algorithm, which sorts the elements in increasing order. It repeatedly compares the adjacent items. And, if the item in the left is larger than the item in the right, the items swap.
An example is as follows.
5 8 1 6 9 2
Consider 5 and 8. It is not necessary to swap the two numbers as 5 1; instead, we swap two items. Now the list is as follows.
5 1 8 6 9 2
Now consider 8 and 6. As 8 > 6, we swap those two numbers. The list is as follows.
5 1 6 8 9 2
Now consider 8 and 9. It is not necessary to swap the numbers as 8 < 9. Then consider 9 and 2. We should swap the two values as 9 > 2. After completing the first iteration, the list appears as below.
5 1 6 8 2 9
The largest item is in the rightmost position. Now, we only have to consider 5 1 6 9 2. We can compare 5 and 1. As 5 > 1, we swap the values. Then, as before, we can follow the same procedure. The list after completing the iteration is as follows.
1 5 6 2 8 9
Now, 8 and 9 are the largest items in the list, but they are already sorted. Now we have to consider 1 5 6 2. This process continues and finally, we can obtain a sorted list.
Conclusion
Bubble sort algorithm is considered to be the most simple and inefficient algorithm, but selection sort algorithm is efficient as compared to bubble sort. Bubble sort also consumes additional space for storing temporary variable and needs more swaps.
