Hello Friends, Come On... Let’s learn about Bubble Sort...
BUBBLE SORT
>One of
the characteristics of the bubble sort is that it is easy to understand and
it’s easy to program it.
>The
basic idea underlying the bubble sort is to pass through the file sequentially
several times.>Each pass consist of comparing each element in the file with it’s next element and interchanging if they are not in proper order.(i.e. Comparison between x[i] and x[i+1] ).
> Consider an example.
>The following comparisons are made on the first
pass
x[0] with x[1] (85 with 75) Interchange
(It becomes 75 85
65 110 120
77)
x[1] with x[2] (85 with 65) Interchange
(It becomes 75 65
85 110 120
77)
x[2] with x[3] (85 with 110) No Interchange
(It becomes 75 65
85 110 120
77)
x[3] with x[4] (110 with 120) No Interchange
(It becomes 75 65
85 110 120
77)
x[4] with x[5] (120 with 77) Interchange
(It becomes 75 65
85 110 77
120)
>Thus after the first pass, the file is in the
following order:
>After getting the first pass’s
result, notice that the largest element (i.e 120 in this example) is in its
proper position within the array.
>Hence in general the ‘x[n-1]’ will be in it’s
proper position after ‘i’ iterations. (Here ‘n’ denotes the number of elements
in array).
>The method is called the bubble
sort because each number slowly “bubbles” up to it’s proper position.
>Now after the second pass the
order of the file will be:
>Notice that 110 has now found
it’s way to the second highest position.
>Hence from this we can state that
since each iteration place a new element at it’s proper place/position; a file
of ‘n’ elements requires ‘maximum’ of (n-1) iterations. i.e. as in this example
there are 6 elements so total 5 iterations would be made to solve this example.
>See the complete list of the iterations that occur
in this example:
Original File: 85 75
65 110 120 77
Iteration 1 75 65 85
110 77 120
Iteration 2 65 75 85
77 110 120
Iteration 4 65 75 77 85 110 120
Iteration 5 65 75 77
85 110 120
>Thus, as the iterations proceeds
simultaneously one-by-one the elements gets positioned at the right place.
>Thus, due to this reason these
sorted elements would not be considered in the succeeding iterations. i.e. on
the first pass,(n-1) comparisons are made, on the second pass,(n-2) comparisons are made and so on and at the last only 1 comparison is done
between x[0] and x[1].
>Thus, due to this the process
speeds up as it proceeds through the successive passes.
>Now recall that earlier we have stated that
maximum (n-1) passes are required to sort the given (n-1) unsorted elements.
>However see in this example of 6
elements that we discussed earlier, the file is already sorted after 3
iterations making the last 2 iterations unnecessary.
>Thus to eliminate unnecessary
passes we must be able to detect the fact that the file is already sorted.
>So, Let’s see the Pseudo-Code for the Bubble Sort.
BubbleSort(A[ ],n)
{
for j<-0
to n-1 //It controls the no. of passes
{
//Initially no
interchange have been made on the pass
Change <- 0
//Inner loop
governs each individual pass
for i<- 0 to
n-k-1
{
if(A[i]
> A[i+1])
{
Swap(A[i],
A[i+1])
Change
<- 1
//As the
values are interchanged change value is changed to 1
}
}
if(change==0)
/*Checks
whether any value was interchanged in that particular pass*/
break
}
}
>Time Complexity
Best Case : O(n)
Average Case : O(n^2)
Worst Case : O(n^2)
THANK-YOU..!!
JAI-HIND..!!
Comments
Post a Comment