Lecture 4
Array Sorting, Merging
P R E PA R E D B Y:
AKLEMA SHORNA
LECTURER
S O F T WA R E E N G I N E E R I N G D E PA R T M E N T,
D A F F O D I L I N T E R N AT I O N A L U N I V E R S I T Y.
Contents
Bubble Sort
Sorting
There different kind of Sorting. Today we will
see a new kind of sorting called “Bubble
Sort”.
Some other kinds of sorting are:
a. Quick Sorting
b. Insertion Sorting
c. Selection Sorting
d. Merge Sorting
e. Radix Sorting.
Sorting : Bubble sort
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 3 4 5 6
42Swap77
42 35 12 101 5
77
"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 77Swap
35 77
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 3 4 5 6
35 12
77Swap
77
12 101 5
42
"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 5 6
42 35 12 77 5Swap101
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
"Bubbling Up" the Largest Element
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
After n-1
comparisons
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.
“Bubbling” All the Elements
1 2 3 4 5 6
42 35 12 77 5 101
1 2 3 4 5 6
35 12 42 5 77 101
1 2 3 4 5 6
N-1
12 35 5 42 77 101
1 2 3 4 5 6
12 5 35 42 77 101
1 2 3 4 5 6
5 12 35 42 77 101
Reducing the Number of Comparisons
1 2 3 4 5 6
77 42 35 12 101 5
1 2 3 4 5 6
42 35 12 77 5 101
1 2 3 4 5 6
35 12 42 5 77 101
1 2 3 4 5 6
12 35 5 42 77 101
1 2 3 4 5 6
12 5 35 42 77 101
Main Part of Codes
Let int array[10]={….}, c,d; Here n=10 , Then :
for (c = 0 ; c < ( n - 1 ); c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (array[d] > array[d+1])
/* For decreasing order use < */
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}
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
We reduce the number of elements we
compare each time one is correctly placed
Questions?
