## Bubble Sort

Another known sorting method is Bubble sort.

• It differs from the selection sort in that, instead of finding the smallest record and then performing an interchange, two records are interchanged immediately upon discovering that they are out of order.
• In bubble sort element is Compare with the next element if they are not in order than interchabging procedure is occure if they are in oeder then elemnt are as it is  and procedure is continue are as it is and proceure is continue the next element logical graph of this Sorting is like a Bubble that’s why is Known as BUBBLE SORT.
• When this approach is used, there are at most n-1 passes required. During the first pass, K1 and K2 are compared and if they are out of order, then records R1 and R2 are interchanged.

• The process is repeated until all the records are compared. This method will cause records with the small keys to move up (bubble up).
• After the first pass the record with the largest key will be in the nth position.
• On each successive pass, the records with the next largest key will be placed in position n-1, n-2, …..,2, respectively, thus resulting in sorted table.
• After each pass through the table, a check can be made to determine whether any interchanges were made during that pass. If no interchanges occurred, then the table must be sorted and no further passes are required.

Procedure BUBBLE_SORT(K, N).

Given a vector K of N elements, this procedure sorts the elements into ascending order.

• The variables PASS and LAST denote the pass counter and position of the last unsorted element, respectively. The variable I is used to index the vector elements.
• The variable EXCH is used to count the number of exchanges made on any pass. All variables are integer.

K – Vector to be sorted

N – Size of the vector

LAST – Position of last sorted element

PASS – Pass counter

EXCH – Count for number of exchanges

1)    [Initialize]

LAST ß N    (entire list assumed unsorted at this point)

2)    [Loop of pass index]

Repeat thru step 5 for PASS = 1, 2,….N-1

3)    [Initialize exchange counter for this pass]

EXCH <– 0

4)    [Perform pairwise comparisons on unsorted elements]

Repeat for I = 1, 2, …….., LAST –1

If K[I] > K[I+1]

then  K[I] « K[I+1]

EXCH <– EXCH + 1

5)    [Were any exchanges performed in this pass?]

If EXCH = 0

then    Return  (mission accomplished; return early)

else     LAST ß LAST – 1  (reduce size of unsorted list)

6)    [Finished]

Return   (maximum number of passes required)

Tracing

1.) At the end of First pass Biggest Element is on their position(last position).At the end of second pass.Second biggest element is on their position(second last)So on…

2.) No any predication For the No.of Passes.