Bubble Sort | Running time O(n2) and Memory O(1)
This algorithm compares two adjacent elements of an
array, and swaps them if they are in the wrong order.
If we have to sort an array of n elements,
- This algorithm makes n-1 passes of the array
- In every pass, it compares each pair of adjacent
elements in the unsorted part of the array, and swaps them if they are in the
wrong order.
- Thus, each pass "bubbles out" the smallest
(or largest) element from the unsorted part of the array.
Algorithm
//bubble sorting in descending order i.e. largest to
smallest
for ( i=0; i< n-1; i++ ) //i controls the number of passes
{
for( j=0;
j< n-i; j++ )
{
if( a[j] < a[j+1]) //using > will change sorting order
{ //swap
temp = a[j];
a[j] = a[j+1];
a[j+1]
= temp;
}
}
}
Example:
Array
to be sorted : 1
7 2 8 5 3 9 ( 7 elements)
Sorting
order : Descending (largest to smallest)
: Sorted
part of array
As we can easily see, bubble sort involves multiple
swaps in each pass, which means it cannot be used when swapping is a costly
action. Also, its complexity O(n2)
means that the time taken for sorting increases as the square of the number of
elements, meaning it can’t be used for large lists. So, it is not a popular
sorting technique.
No comments:
Post a Comment