Bubble sort is a straightforward sorting method. This sorting algorithm is a comparison-based method that compares each pair of adjacent elements and swaps them if they are out of order. Because the average and worst case complexity of this technique are O(n2), where n is the number of items, it is not suitable for huge data sets.
What is the procedure for sorting bubbles?
As an example, we'll use an unsorted array. We're keeping it brief and accurate because bubble sort takes (n2) time.
Bubble sort begins with the first two components and compares them to see which is greater.
Because the value 33 is bigger than 14, it is already in sorted places in this scenario. After that, we compare 33 to 27.
We discover that 27 is less than 33, hence the two numbers must be exchanged.
This is how the new array should look:
After that, we'll compare 33 and 35. We discover that both have previously been sorted.
Then we move to the next two values and that will be 35 and 10.
We know then that 10 is smaller than 35. Hence they are not sorted.
We swap these values. We find that we have reached the end of the array. After one iteration, the array should look like this −
To be precise, we are now showing how an array should look like after each iteration. After the second iteration, it should look like this −
Notice that after each iteration, at least one value moves at the end.
And when there's no swap required, bubble sort learns that an array is completely sorted.
Now we should look into some practical aspects of bubble sort.
A list is assumed to be an array of n elements. We also suppose that the swap function swaps the values of the array members passed to it. begin BubbleSort(list)
if list[i] > list[i+1] for all list items
swap(list[i], list[i+1]) is a function that swaps two lists.
end if and only if
list of returns
end SortBubbles
Bubble Sort, we notice in an algorithm, compares each pair of array elements unless the entire array is sorted in ascending order. This could lead to some complications, such as what if the array doesn't need any more swapping because all of the elements are ascending.
To make the problem go away, we use one flag variable switched to see if any swaps have occurred. It will exit the loop if no swap has occurred, i.e. the array requires no further processing to be sorted.
The pseudocode for the BubbleSort algorithm is as follows:
bubbleSort procedure ( list : array of items )
list.count; loop = list.count;
swapped = false for I = 0 to loop-1
Do the following for j = 0 to loop-1:
/* compare nearby elements */ swap(list[j], list[j+1]) if list[j] >
list[j+1] if list[j] > list[j+1] if list[j] > list[j+1] if list[j]
> list[j+1] if list[j] > list[j+1] if list[j] > list[
If switched = true, the end result will be true.
the conclusion of
/*If no numbers were swapped, the array is now sorted; end the loop./
if(not swapped) then break if(not swapped) then break if(not swapped) then break if(not
the conclusion of
return list at the end of the process
Another issue we didn't solve in our original method and its improvised pseudocode is that the highest values settle at the end of the array after each iteration. As a result, the following iteration does not need to contain elements that have already been sorted. In order to avoid previously sorted values, we restrict the inner loop in our implementation.
|
|
