Bubble sort algorithm in java
Bubble sort works by comparing two items in the list at a time. Bubble sort will always compare two consecutive items in the list, and swap them if they are out of order. If we assume that we start at the beginning of the list, this means that at each pass through the algorithm, the largest remaining item in the list will be placed at its proper location in the list.
Algorithm for bubble sort:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
for i=N-1 to 2 { set swap flag to false for j=1 to i { if list[j-1] > list[j] swap list[j-1] and list[j] set swap flag to true } if swap flag is false, break. The list is sorted. } |
Notice that in each pass, the largest item “bubbles” down the list until it settles in its final position. This is where bubble sort gets its name.
Example:
Notice that only the largest value is correctly placed. All other values are still out of order, So we need to repeat this process.
Bubbling all the elements:
If we have N elements, And if each time we bubble an element, we place it in its correct location. Then we repeat the “bubble up” process N– 1 times. This guarantees we’ll correctly place all N elements.
Java implementation for bubble sort:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public void bubbleSort(int[] list) { // this variable will indicate if the list is sorted on this pass boolean isSorted; for (int i=0; i<list.length-1; i++) { isSorted = true; for (int j=0; j<list.length-i-1; j++) { if (list[j+1] < list[j]) { // two items are out of order, so swap them swap(list,j,j+1); isSorted = false; } } if (isSorted) { // we didn’t find anything to swap, so we’re done. break; } } } |
Performance of bubble sort algorithm:
- The best case for bubble sort occurs when the list is already sorted. In this case, bubble sort makes one pass through the list, performing no swaps and N-1 comparisons.
- The worst case for bubble sort occurs when the list is in reverse order. In this case, every item will have to be swapped with every other item on every pass through the algorithm. The number of swaps in the worst case is each comparison results in a swap, so there are O(N2 ) swaps in bubble sort!
- The average case looks like the worst case: O(N2 ) comparisons and O(N2 ) swaps.
Let’s see whether bubble sort is stable and in-place or not:
Stability:
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array
Selection sort algorithm is not stable because:
Selection sort algorithm picks the minimum and swaps it with the element at current position.
Suppose the array is:5 2 3 8 4 5 6
Let’s distinguish the two 5’s as 5(a) and 5(b) .
So our array is:
5(a) 3 4 5(b) 2 6 8
After iteration 1:
3 4 5(a) 2 5(b) 6 8
after last iteration our array becomes:
2 3 4 5(a) 5(b) 6 8
Since now our array is in sorted order and we clearly see that 5(a) comes before 5(b) in initial array and in the sorted array also.
So we can clearly see that bubble sort is stable.
In place:
An in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes
As explained above, bubble sort is structured so that on each pass through the list the next largest element of the data is moved to its proper place. Therefore, to get all n elements in their correct places, the outer loop must be executed n times. It takes small data structure for swapping purpose. so the bubble sort is one of the in place algorithm.
Leave a Reply