Data Structures and
Algorithms
Searching and Sorting
Lecturer: Dr. Ali Anwar
2
Objectives
Introduction of Algorithms:
● Searching
• Linear search
• Binary search
● Sorting
• Merge sort
• Quick sort
• Bubble sort
• Insertion sort
• Selection sort
3
Part 1
Searching Algorithms
4
Example of Linear Search
Meaning:
1) if x does not occur in the array a, then i should be −1
2) if it does occur - then i should be a position where it occurs.
5
Example of Linear Search (cont.)
1. Start from the leftmost
element of array and one by
one compare x with each
element of a
2. If x matches with an
element, return the index
3. If x doesn’t match with any
of elements, return -1.
4. Complexity is O(n)
6
Binary Search
Binary Search works by
repeatedly dividing in half
the portion of the list that
could contain the item, until
you've narrowed down the
possible locations to just
one.
• Complexity is n / 2k = 1
or O(logn)
7
C++ Implementation of Binary Search
8
Part 2
Sorting Algorithms
9
Sorting
• Sorting is arranging the elements in a list or collection in
increasing or decreasing order of some property
• The list should be homogenous (all the elements in the
list should be of same type)
• Example:
• Input: 2, 3, 9, 4, 6
• Output:
• 2, 3, 4, 6, 9 (increasing order)
• 9, 6, 4, 3, 2 (decreasing order)
• 2, 3, 9, 4, 6 (increasing order of number of factors)
Sorting (contd.)
● Input to the sorting algorithms:
• a collection of records stored in an array
• Some examples include:
• Search results on websites
• Language Dictionaries
11
Analyzing Sorting Algorithms
● Running time: measure the number of comparisons made
between keys.
● In some situations: measure the number of swap operations,
when the records are “large”
12
Insertion Sort
● Real life example: when
assembling playing cards.
● Insertion sort iterates through a
list of records.
● Each record is inserted in turn at
the correct position within a
sorted list composed of those
records already processed.
13
Example of Insertion Sort
Unsorted set
Sorted set
14
Insertion Sort – Running Time
● Worst case: O(n²)
● In case of descending sorted array => n scans and n swaps
● Best case or Almost Sorted case: O(n)
● In case of ascending sorted array => n scans only
● Average case for a random array: O(n²)
15
Bubble Sort
● We scan the array from left to right multiple times
● Each time the scan happens, it is called a pass
● Algorithm:
• First iteration of the inner for loop moves through the record array from
bottom to top, comparing adjacent keys
• The second pass through the array repeats this process, but not to the top
(-1)
• → elements ‘bubble’ to the top
16
Example of Bubble Sort
Source: https://bit.ly/34sO15r
17
Bubble Sort – C++ Code
● Algorithm compares each item with every other item in some list
● Time complexity O(n²)
18
Bubble Sort – Running Time
● outer loop: n - 1
● inner loop: n - 1
● running time: (n-1)2
● # swaps ~ O(n²)
19
Selection Sort
● Selection Sort:
• first finds the smallest key in an unsorted list and places that value on
top
• then repeats with the second smallest, and so on.
● Algorithm: The i-th pass of selection sort “selects” the i-th
smallest key in the array, placing that record into position i.
20
Example of Selection Sort
Scan the element for minimum, compare with top and swap
21
Selection Sort – Running Time
● Just like in bubble sort:
• running time (#compairs) ~ O(n²)
● But we remember the position of the ‘next smallest’ element,
and perform one swap
• useful when the cost of swap is high
22
Quick Sort
● Typical “divide and conquer” strategy:
• Divide: divide the input data S in two disjoint subsets S1 and S2
• Recur: solve the subproblems associated with S1 and S2
• Conquer: combine the solutions for S1 and S2 into a solution for S
● Fastest general-purpose in-memory sorting algorithm in the
average case & space efficient.
● It is most practical sorting algorithm because of it efficiency
23
Quick Sort Algorithm
● Pick an element, called a pivot, from the array.
• typically: last element (or first, middle)
● Partitioning: re-order the array so that all elements with values
less than the pivot come before the pivot, while all elements with
values greater than the pivot come after it. After this partitioning,
the pivot is in its final position. This is called the partition
operation.
● Recursively apply the above steps to Left & Right subarray.
24
Example of Quick Sort
25
Quick Sort – C++ Code
● Algorithm picks a pivot and move all smaller items before it,
while all greater elements after it (=partition), recursively
repeated on lesser and greater sub-lists until their size is one or
zero
● Time complexity O(n log(n)) – for best case
c1
n
n/2
n/2
26
Quick Sort – Running Time
● Worst case: occurs when ‘pivot’ does a poor job of breaking the
array (unbalanced array)
• O(n²)
● Best case: occurs when ‘pivot’ always breaks the array into two
equal halves
• log n levels, each level n/2
• O(n log n)
● Average case:
• O(n log n)
27
Merge Sort
● Similar to Quick Sort, but does not do in place swaps (higher
space complexity)
● Algorithm splits a list into two similar sized lists (left and right)
and sorts each list and then merges the sorted lists back together
● Time complexity O(n log(n)) – Worst Case
28
Example of Merge Sort
29
Merge Sort – C++ Code
For arrays:
1. create a new array b
to store the results
2. repeatedly add the
next smallest item
into it until one sub-
array is finished
3. copy the remainder
of the unfinished
sub-array
4. copy b back into a
30
Summary of Sorting Algorithms
Algorithm Time Notes
Selection sort O(n2) • In-place
• Slow (good for small inputs)
Insertion sort O(n2) • In-place
• Slow (good for small inputs)
Quick sort O(n2) expected • In-place, randomized
• Fastest (good for large inputs)
Merge sort O(n log n) • Sequential data access
• Fast (good for huge inputs)
