Bubble sort

BIOINFORMATICS BUBBLE SORTING

1. Pandit Ravishankar Shukla University S.O.S In Biotechnology Topic :- Bubble Sort Concept and Usage Guided by :- Dr. Jaishankar Paul Submitted by :- P. Sujata Msc II sem 1

2. Content Sorting Category of sorting Bubble sort Bubble sort coding Example of bubble sort Bubble sort analysis Time complexity of bubble sort Application of bubble sort Merits of bubble sort Demerits of bubble sort Conclusion Reference 2

3. Sorting Sorting refers to the arranging a set of data in some logical order. It is used to rearrange a given elements according to a comparison operator. Sorting is the operation performed to arrange the records of a table or list according to some specific ordering criterion. The records are arranged either in numerically or alphanumerically. Example :- phone number directory can be thought as a list of where each record has three fields – name of the person , address of the person, their phone numbers . Being unique phone number can work as a key to locate any record in the list. 3

4. Category of sorting 4 Sorting can divided into two categories:- Internal sorting :- If all the data that is to be sorted can be adjusted at a time in the main memory, the internal sorting is being performed. External sorting :- When the data that is to be sorted cannot be accommodated in the memory at the same time and some has to be kept in auxiliary memory such as had disk , floppy disk, etc,.

5. Bubble sort is one of the type of sorting . Bubble Sort  is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort compares all the element one by one and sort them based on their values. If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of the array with the second element, if the first element is greater than the second element, it will  swap  both the elements, and then move on to compare the second and the third element, and so on. If we have total n elements, then we need to repeat this process for n-1  times. It is known as  bubble sort , because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface. Sorting takes place by stepping through all the elements one-by-one and comparing it with the adjacent element and swapping them if required . 5 Bubble sort

6. Bubble sort coding   Sub Bubble sort( ) for i =1 to 7 for j = 1 to 7 If cells (j,1) > cells (j+1,1)then swap the two values temp= cells (j,1) cells(j,1)=cells (j+1,1 ) cells(j+1,1) = temp Application.wait (Now + Timevalue (“0:00:01”) End if Next j Next i End sub 6

7. Before bubble sorting 7

8. After bubble sorting 8

9. In this case all the conditions are true . So no swapping is required. No exchange of data will occur . 9

10. In this case 2 nd and 3 rd conditions are false so swapping is required . Exchange of data will take place . 10

11. Bubble sort : Example 11

12. 12

13. Bubble S ort Analysis 13

14. 14

15. Bubble sort: Time complexity Best case : The data is already sorted no swapping is required. For example: 1 2 3 4 5 Worst case : The data is arranged in reverse order . Swapping is required in each step . For example :6 5 4 3 2 1 Average case : The data is arranged randomly swapping is not required in every step. For example : 8 9 1 4 5 7 15

16. 16 Bubble sort : Time Complexity

17. Bubble sort :Application 17 It is a simple algorithm used to sort an unsorted data in ascending or descending order. Bubble sort is used in arranging data according to their dates also. Bubble sort can be used in central tendency because to calculate mean median mode we have to arrange data in ascending order bubble sort can be used in this case. Biologists are interested in comparing species. So bubble sort is used in arranging nucleotide sequence. Bubble sort is used in bioinformatics and used in biological data analysis. Bubble sort is used in   National Center for Biotechnology Information  (NCBI).

18. Bubble sort :Merits Bubble sort is the oldest and simplest in use. Bubble sort is easy to understand and implement. Bubble sort requires very little memory. The bubble sort is comprised of relatively few lines of code. Bubble sort is stable and elements are swapped in place and do not use extra array. 18

19. Bubble sort : Demerits Bubble sort requires much time to complete. It is highly inefficient for large data sets. The coding becomes complex for large amount of data. We can not sort selected data . Bubble sort takes half day or more than that in case of arranging large base pairs of human genome. 19

20. Conclusion Bubble Sort takes several passes to sort elements in an array. Every pass need to do comparisons between elements and exchange the data if the elements are not in the right order. To perform bubble sorting we need coding. Bubble sorting swaps until the data is sorted. Bubble sorting takes place in ascending or descending order. Now a days it is not used because of its high time consuming performance. 20

21. Reference 21 www.slideshare.com www.slideplayer.com

22. Thank you 22