Bubble Sort

Bubble Sort By

Junaid Ali Siddiqui

What is sorting ?  Sorting refers to arranging the records in

some logical order.  In case of String or character data this order may be alphabetical.  In case of numerical data this order may be increasing or decreasing .  Sorting efficiently may be quite complicated.

Types of sorting algorithms  Bubble sort  Quick sort  Heap sort  Radix sort  Selection sort  Merge sort  Insertion sort

Bubble sort algorithm BUBBLE(DATA,N,PTR,K) Here DATA is an array with N elements. This algorithm sorts the elements of DATA in ascending order. Step 1 :Repeat steps 2 and 3 for K=1 to N-1. Step 2 :Set PTR:=1.[Initializes pass pointer PTR.] Step 3:Repeat while (PTR<=N-K):[ Executes pass.] (a) if( DATA[PTR]>DATA[PTR +1]),then: Interchange DATA[PTR] and DATA[PTR+1]. (b) Set PTR:=PTR+1 [End of inner loop.] [End of Step 1 outer loop.] Step 4 : Exit.

How it works ? This algorithm will be explained by the help of an example.

Complexity of Bubble sort algorithm  Traditionally the time for a sorting algorithm is measured

in terms of the number of comparisons.  The number f(n) of comparisons in the bubble sort is easily computed.  Specifically  There are n-1 comparisons during the first pass which places the largest element in the last position,.  There are n-2 comparisons in the 2nd step which places second largest element in the next-to-last position and so on.

Continued………..    



Thus f(n)=(n-1)+(n-2)+………..+2+1=n(n-1)/2=nxn/2+O(n)=O(nxn) Remark: Some programmers use a bubble sort algorithm that containsa 1bit variable FLAG (or a logical variable FLAG) to signalwhen no interchange takes place during a first pass. If FLAG = 0 after any pass ,then the list is already sorted and there is noneed to continue. This may cut down on the number of passes. Caution: However ,when using such a FLAG ,one must initialize ,change and test the variable FLAG during each pass. Hence the use of FLAG is efficient only when the list originally is “almost” in sorted order.

Any response? If there is any question in your mind you can ask. [email protected]

Time over Message from the presenter This world is an echo, all comes back good or bad, so give the world your best, best will return to you & always have good opinion about others because this is what you want from them. Thank you for your cooperation References: Schaum ‘s outline of theory & problems of Data structures.