Sorting In Bubble

Programming and Data Structures SORTING Dr. B.B.Biswal Computer Science & Engineering GIET UNIVERSITY Introduction Sorting has acquired immense significance in the discipline of Computer Science. Sorting is a process in which keys(data items) are arranged in ascending/descending order. Objective: Imagine a situation, where you might have to locate a telephone number in the telephone directory, if the numbers were listed in random order. CS 11001 : Programming and Data Structures 2 SORTING Types of Sorting CS 10001 : Programming and Data Structures INTERNAL EXTERNAL 3 Types of Sorting CS 10001 : Programming and Data Structures 4 Sorting • Given an array x[0], x[1], … , x[n-1] reorder entries so that x[0] <= x[1] <= . . . <= x[n-1] Here, List is in increasing order CS 10001 : Programming and Data Structures 5 Sorting – Example • Original list: – 10, 30, 20, 80, 70, 10, 60, 40, 70 • Sorted in increasing order: – 10, 10, 20, 30, 40, 60, 70, 70, 80 • Sorted in decreasing order: – 80, 70, 70, 60, 40, 30, 20, 10, 10 CS 10001 : Programming and Data Structures 6 Sorting Algorithms CS 11001 : Programming and Data Structures 7 Sorting by Comparison Sorting by comparison – Insertion: • From a given list of items, one item is considered at a time. The item chosen is then inserted into an appropriate position relative to the previously sorted items. The item can be inserted into the same list or to a different list. e.g.: Insertion sort Sorting by comparison – Selection: • First the smallest (or largest) item is located and it is separated from the rest; then the next smallest (or next largest) is selected and so on until all item are separated. e.g.: Selection sort, Heap sort CS 10001 : Programming and Data Structures 8 Lecture #07: © DSamanta Sorting by Comparison Sorting by comparison – Exchange: • If two items are found to be out of order, they are interchanged. The process is repeated until no more exchange is required. e.g.: Bubble sort, Shell Sort, Quick Sort Sorting by comparison – Enumeration: • Two or more input lists are merged into an output list and while merging the items, an input list is chosen following the required sorting order. e.g.: Merge sort CS 10001 : Programming and Data Structures 9 Lecture #07: © DSamanta Bubble Sort CS 10001 : Programming and Data Structures 10 Lecture #07: © DSamanta Bubble sort belongs to the family of sorting by exchange. Bubble sort is the oldest, simplest and the slowest sorting in use. In this algorithm, smallest element move up or bubble to the top of the list, hence the name bubble sort. Basic idea behind the bubble sort is to compare the adjacent elements and move the smallest element to the top of the list. CS 10001 : Programming and Data Structures 11 Bubble Sort CS 10001 : Programming and Data Structures 12 Sorting • Sorting takes an unordered collection and makes it an ordered one. 1 2 3 4 5 6 77 42 35 12 101 5 1 2 3 4 5 6 5 12 35 42 77 101 "Bubbling Up" the Largest Element • Traverse a collection of elements – Move from the front to the end – “Bubble” the largest value to the end using pair-wise comparisons and swapping 1 2 3 4 5 6 77 42 35 12 101 5 "Bubbling Up" the Largest Element • Traverse a collection of elements – Move from the front to the end – “Bubble” the largest value to the end using pair-wise comparisons and swapping 1 2 42Swap 77 42 77 3 4 5 6 35 12 101 5 "Bubbling Up" the Largest Element • Traverse a collection of elements – Move from the front to the end – “Bubble” the largest value to the end using pair-wise comparisons and swapping 1 42 2 3 35Swap35 77 77 4 5 6 12 101 5 "Bubbling Up" the Largest Element • Traverse a collection of elements – Move from the front to the end – “Bubble” the largest value to the end using pair-wise comparisons and swapping 1 2 42 35 3 4 12Swap12 77 77 5 6 101 5 "Bubbling Up" the Largest Element • Traverse a collection of elements – Move from the front to the end – “Bubble” the largest value to the end using pair-wise comparisons and swapping 1 2 3 4 5 6 42 35 12 77 101 5 No need to swap "Bubbling Up" the Largest Element • Traverse a collection of elements – Move from the front to the end – “Bubble” the largest value to the end using pair-wise comparisons and swapping 1 2 3 4 42 35 12 77 5 6 5 Swap101 101 5 "Bubbling Up" the Largest Element • Traverse a collection of elements – Move from the front to the end – “Bubble” the largest value to the end using pair-wise comparisons and swapping 1 2 3 4 5 6 42 35 12 77 5 101 Largest value correctly placed Items of Interest • Notice that only the largest value is correctly placed • All other values are still out of order • So we need to repeat this process 1 2 3 4 5 6 42 35 12 77 5 101 Largest value correctly placed Repeat “Bubble Up” How Many Times? • If we have N elements… • And if each time we bubble an element, we place it in its correct location… • Then we repeat the “bubble up” process N – 1 times. • This guarantees we’ll correctly place all N elements. N-1 “Bubbling” All the Elements 1 42 2 35 3 12 4 77 5 5 6 101 1 35 2 12 3 42 4 5 5 77 6 101 1 12 2 35 3 5 4 42 5 77 6 101 1 12 2 5 3 35 4 42 5 77 6 101 1 5 2 12 3 35 4 42 5 77 6 101 Reducing the Number of Comparisons 1 77 1 42 2 42 2 35 3 35 3 12 4 12 4 77 5 101 5 5 6 5 6 101 1 35 2 12 3 42 4 5 5 77 6 101 1 12 2 35 2 5 3 5 3 35 4 42 5 77 6 101 4 42 5 77 6 101 1 12 Reducing the Number of Comparisons • On the Nth “bubble up”, we only need to do MAX-N comparisons. • For example: – This is the 4th “bubble up” – MAX is 6 – Thus we have 2 comparisons to do 1 12 2 35 3 5 4 42 5 77 6 101 An Animated Example N 8 to_do 7 did_swap true index 98 23 45 14 1 2 3 4 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 1 did_swap false 98 23 45 14 1 2 3 4 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 1 did_swap false Swap 98 23 45 14 1 2 3 4 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 1 did_swap true Swap 23 98 45 14 1 2 3 4 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 2 did_swap 23 98 45 14 1 2 3 4 true 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 2 did_swap true Swap 23 98 45 14 1 2 3 4 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 2 did_swap true Swap 23 45 98 14 1 2 3 4 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 3 did_swap 23 45 98 14 1 2 3 4 true 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 3 did_swap true Swap 23 45 98 14 1 2 3 4 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 3 did_swap true Swap 23 45 14 98 1 2 3 4 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 4 did_swap 23 45 14 98 1 2 3 4 true 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 4 did_swap true Swap 23 45 14 98 1 2 3 4 6 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 4 did_swap true Swap 23 45 14 6 1 2 3 4 98 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 5 did_swap 23 45 14 6 1 2 3 4 true 98 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 5 did_swap true Swap 23 45 14 6 1 2 3 4 98 67 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 5 did_swap true Swap 23 45 14 6 1 2 3 4 67 98 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 6 did_swap 23 45 14 6 1 2 3 4 true 67 98 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 6 did_swap true Swap 23 45 14 6 1 2 3 4 67 98 33 42 5 6 7 8 An Animated Example N 8 to_do 7 index 6 did_swap true Swap 23 45 14 6 1 2 3 4 67 33 98 42 5 6 7 8 An Animated Example N 8 to_do 7 index 7 did_swap 23 45 14 6 1 2 3 4 true 67 33 98 42 5 6 7 8 An Animated Example N 8 to_do 7 index 7 did_swap true Swap 23 45 14 6 1 2 3 4 67 33 98 42 5 6 7 8 An Animated Example N 8 to_do 7 index 7 did_swap true Swap 23 45 14 6 1 2 3 4 67 33 42 98 5 6 7 8 After First Pass of Outer Loop N 8 to_do 7 index 8 did_swap Finished first “Bubble Up” 23 45 14 6 1 true 2 3 4 67 33 42 98 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 1 did_swap false 23 45 14 6 1 2 3 4 67 33 42 98 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 1 did_swap false No Swap 23 45 14 6 1 2 3 4 67 33 42 98 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 2 did_swap false 23 45 14 6 1 2 3 4 67 33 42 98 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 2 did_swap false Swap 23 45 14 6 1 2 3 4 67 33 42 98 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 2 did_swap true Swap 23 14 45 6 1 2 3 4 67 33 42 98 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 3 did_swap 23 14 45 6 1 2 3 4 true 67 33 42 98 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 3 did_swap true Swap 23 14 45 6 1 2 3 4 67 33 42 98 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 3 did_swap true Swap 23 14 6 1 2 3 45 67 33 42 98 4 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 4 did_swap 23 14 6 1 2 3 true 45 67 33 42 98 4 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 4 did_swap true No Swap 23 14 6 1 2 3 45 67 33 42 98 4 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 5 did_swap 23 14 6 1 2 3 true 45 67 33 42 98 4 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 5 did_swap true Swap 23 14 6 1 2 3 45 67 33 42 98 4 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 5 did_swap true Swap 23 14 6 1 2 3 45 33 67 42 98 4 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 6 did_swap 23 14 6 1 2 3 true 45 33 67 42 98 4 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 6 did_swap true Swap 23 14 6 1 2 3 45 33 67 42 98 4 5 6 7 8 The Second “Bubble Up” N 8 to_do 6 index 6 did_swap true Swap 23 14 6 1 2 3 45 33 42 67 98 4 5 6 7 8 After Second Pass of Outer Loop N 8 to_do 6 index 7 did_swap Finished second “Bubble Up” 23 14 6 1 true 2 3 45 33 42 67 98 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 1 did_swap false 23 14 6 1 2 3 45 33 42 67 98 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 1 did_swap false Swap 23 14 6 1 2 3 45 33 42 67 98 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 1 did_swap true Swap 14 23 6 1 2 3 45 33 42 67 98 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 2 did_swap 14 23 6 1 2 3 true 45 33 42 67 98 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 2 did_swap true Swap 14 23 6 1 2 3 45 33 42 67 98 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 2 did_swap true Swap 14 6 1 2 23 45 33 42 67 98 3 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 3 did_swap 14 6 1 2 true 23 45 33 42 67 98 3 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 3 did_swap true No Swap 14 6 1 2 23 45 33 42 67 98 3 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 4 did_swap 14 6 1 2 true 23 45 33 42 67 98 3 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 4 did_swap true Swap 14 6 1 2 23 45 33 42 67 98 3 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 4 did_swap true Swap 14 6 1 2 23 33 45 42 67 98 3 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 5 did_swap 14 6 1 2 true 23 33 45 42 67 98 3 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 5 did_swap true Swap 14 6 1 2 23 33 45 42 67 98 3 4 5 6 7 8 The Third “Bubble Up” N 8 to_do 5 index 5 did_swap true Swap 14 6 1 2 23 33 42 45 67 98 3 4 5 6 7 8 After Third Pass of Outer Loop N 8 to_do 5 index 6 did_swap Finished third “Bubble Up” 14 6 1 true 2 23 33 42 45 67 98 3 4 5 6 7 8 The Fourth “Bubble Up” N 8 to_do 4 index 1 did_swap false 14 6 1 2 23 33 42 45 67 98 3 4 5 6 7 8 The Fourth “Bubble Up” N 8 to_do 4 index 1 did_swap false Swap 14 6 1 2 23 33 42 45 67 98 3 4 5 6 7 8 The Fourth “Bubble Up” N 8 to_do 4 index 1 did_swap true Swap 6 1 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fourth “Bubble Up” N 8 to_do 4 index 2 6 1 did_swap true 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fourth “Bubble Up” N 8 to_do 4 index 2 did_swap true No Swap 6 1 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fourth “Bubble Up” N 8 to_do 4 index 3 6 1 did_swap true 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fourth “Bubble Up” N 8 to_do 4 index 3 did_swap true No Swap 6 1 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fourth “Bubble Up” N 8 to_do 4 index 4 6 1 did_swap true 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fourth “Bubble Up” N 8 to_do 4 index 4 did_swap true No Swap 6 1 14 23 33 42 45 67 98 2 3 4 5 6 7 8 After Fourth Pass of Outer Loop N 8 to_do 4 index 5 6 1 did_swap true Finished fourth “Bubble Up” 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fifth “Bubble Up” N 8 to_do 3 index 1 6 1 did_swap false 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fifth “Bubble Up” N 8 to_do 3 index 1 did_swap false No Swap 6 1 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fifth “Bubble Up” N 8 to_do 3 index 2 6 1 did_swap false 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fifth “Bubble Up” N 8 to_do 3 index 2 did_swap false No Swap 6 1 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fifth “Bubble Up” N 8 to_do 3 index 3 6 1 did_swap false 14 23 33 42 45 67 98 2 3 4 5 6 7 8 The Fifth “Bubble Up” N 8 to_do 3 index 3 did_swap false No Swap 6 1 14 23 33 42 45 67 98 2 3 4 5 6 7 8 After Fifth Pass of Outer Loop N 8 to_do 3 index 4 6 1 did_swap false Finished fifth “Bubble Up” 14 23 33 42 45 67 98 2 3 4 5 6 7 8 Finished “Early” N 8 to_do 3 index 4 did_swap false We didn’t do any swapping, so all of the other elements must be correctly placed. We can “skip” the last two passes of the outer loop. 6 1 14 23 33 42 45 67 98 2 3 4 5 6 7 8 Algorithm Bubblesort(A,n) 1.I=0 [INITIALIZE I=0] 2.REPEAT THROUGH STEP5 WHILE (I A[J+1]) i. TEMP=A[J] ii. A[J]=A[J+1] iii. A[J+1]=TEMP 6. DISPLAY THE SORTED ELEMENTS OF ARRAY A 7. EXIT Summary • “Bubble Up” algorithm will move largest value to its correct location (to the right) • Repeat “Bubble Up” until all elements are correctly placed: – Maximum of N-1 times – Can finish early if no swapping occurs • We reduce the number of elements we compare each time one is correctly placed ANALYSIS Case1(Best case):The best case condition occurs, if the array is already sorted. The outer loop is to be executed n-1 times and the inner loop will be for n1,n-2, n-3,……1 time for each iteration but never enters the true block. Hence O(n) Case2:(Average case) n(n-1)/2=O(n2) Case3:(Worst Case)When array is in reverse order f(n)=n-1+n-2+…….+2+1 =n(n-1)/2=O(n2) Questions?