Data Structure
Lecture 5: Sorting
Dr. Tauheed
Contents
Binary Searching
Bubble Sort
2
Question
1. Where is linear searching used
a) When the list has only a few elements d)
b) When performing a single search in an unordered list
c) Used all the time
d) When the list has only a few elements and When performing a single search in an unordered list
2. Which of the following is a disadvantage of linear search?
a) Requires more space
b) Greater time complexities compared to other searching algorithms
b)
c) Not easy to understand
d) Not easy to implement
Binary search : Approach
Input: An array of elements and the number to be searched (say x) in the array
Output: Return position of , if is found in the array
Let Small(P) be true if n = 1.
In Binary Searching, S(P)will take the value if
Otherwise it will take the value 0
If has more than one element, it should be divided into a sub-problems
Binary search :
Algorithm
A=[2] A=[2]
X=3 X=2
Example
Search Key: 42
index 0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 16
0 1 2 3 4 5
value -4 2 7 10 15 20 22 25 30 36 42 50 56 68 85 92 103
𝑖 𝑚𝑖𝑑
𝑖
𝑖 𝑚𝑖𝑑 𝑙
𝑚𝑖𝑑 𝑙
Key found at index location 10
Binary Search: Complexity
Let T be the time required to find element x in the given array of n element using binary search
T
Comparison with linear search
index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
value -4 2 7 10 15 20 22 25 30 36 42 50 56 68 85 92 103
Time complexity: O(n)
Note: Linear search is better than binary search if data is not sorted
Sorting
Sorting refers to ordering data in an increasing or decreasing manner according to some linear
relationship among the data items.
1 2 3 4 5 6
77 42 35 12 101 5
Sorting takes an unordered
collection and makes it an
ordered one
1 2 3 4 5 6
5 12 35 42 77 101
Sorting Algorithms
Bubble Sort
Insertion Sort
Selection Sort
Quick Sort
Radix Sort
Heap Sort
Bubble Sorting
Bubble Sort is a sorting algorithm that repeatedly steps through the data, compares adjacent
elements, and swaps them if they are in the wrong order. This process continues until the list is
sorted.
Approach
Traverse the collection of data
• 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
Example 12 101
77 42 35 5
Example 1
1 2 3 4 5
6
77 42 35 12 101 5
42
42 77
77 35 12 101 5
Largest value
42 35
35 77
77 12 101 5 correctly placed
42 35 12
12 77 101 5
42 35 12 77 55 101
101
Bubble Sort
42 35 12 77 5 101
only the largest value is
correctly placed
All other values are still out of order
So we need to repeat the process
• Consider the array consists of N elements
• Also in each iteration we bubble an element and place
How Many Times to repeat the process? it in its correct location
• Then we repeat the “bubble up” process N – 1 times.
• This guarantees that all N elements are correctly
placed.
Bubble Sort: Sorting all
elements
42 35 12 77 5 101
35 12 42 5 77 101
35 5 42 77 101
Total no. of elements n=6
12
No. of iteration = 5 (n-1)
12 5 35 42 77 101 Reducing the Number
of Comparisons
5 12 35 42 77 101
Bubble Sort: Sorting all
elements
Consider that we have an array of size N, then how many comparisons do we need in the
iteration to sort the array data.
𝑁 −𝑘
