Chapter Three:
Searching and Sorting Algorithm
Data Structures and Algorithms
Prepared by:
Ataklti Nguse
05/16/2025 Ataklti N. 1
3.1. Searching
There are some very common problems that we use computers to solve:
Searching: Looking for specific data item/record from list of data items or set of records.
Sorting : placing records/items in order
There are numerous algorithms to perform searches and sorts.
Searching is a process of looking for a specific element in a list of items or determining that the item is
not in the list.
Search an element in a given array, there are two popular algorithms available:
1. Sequential Search, and
2. Binary Search
05/16/2025 Ataklti N. 2
3.1.1 Sequential or linear search
Linear search is a very basic and simple search algorithm.
linear search or sequential search is a method for finding an element within a list.
It sequentially checks each element of the list until a match is found or the whole list has been
searched.
Linear search runs in at worst linear time and makes at most n comparisons, where n is the
length of the list.
05/16/2025 Ataklti N. 3
Continued…
Example Implementation:
int linear_search(int list[], int n, int key){
for (int i=0;i<n; i++){
if(list[i]==key)
return i;
}
return -1;
}
05/16/2025 Ataklti N. 4
…Continued
In Linear search, we search an element or value in a given array by traversing the array from
the starting, till the desired element or value is found.
by compares the element to be searched with all the elements present in the array and when
the element is matched successfully,
it returns the index of the element in the array, else it return -1.
Features of Linear Search Algorithm
• It is used for unsorted and unordered small list of elements.
• It has a time complexity of O(n), which means the time is linearly dependent on the number
of elements, which is not bad, but not that good too.
05/16/2025 Ataklti N. 5
3.1.2. Binary search
Binary search looks for a particular item by comparing the middle most item of the collection.
Binary searching algorithm works only on an ordered list either descending or ascending
order.
Uses the divide-and-conquer technique to search the list
05/16/2025 Ataklti N. 6
…Continued
The basic idea is:
Locate midpoint of array to search
If a match occurs, then the index of item is returned.
If the middle item is greater than the item, then the item is searched in the sub-array to
the left of the middle item.
Otherwise, the item is searched for in the sub-array to the right of the middle item.
Binary search halves the searchable items and thus reduces the count of comparisons to
be made to very less numbers.
05/16/2025 7
…Continued
• In binary search, we follow the following steps:
1. We start by comparing the element to be searched with the element in the middle of
the list/array.
2. If we get a match, we return the index of the middle element.
3. If we do not get a match, we check whether the element to be searched is less or
greater than in value than the middle element.
4. If the element/number to be searched is greater in value than the middle number,
then we pick the elements on the right side of the middle element(as the list/array is
sorted, hence on the right, we will have all the numbers greater than the middle
number), and start again from the step 1.
5. If the element/number to be searched is lesser in value than the middle number, then
we pick the elements on the left side of the middle element, and start again from the
step 1.
• Binary Search is useful when there are large
05/16/2025 Atakltinumber
N. of elements in an array and they
8 are
Features of Binary Search
1.It is great to search through large sorted arrays.
2.It has a time complexity of O(log n) which is a very good time complexity.
05/16/2025 Ataklti N. 9
…Continued
The computational time for this algorithm is proportional to log 2 n.
Therefore, the time complexity is O(log n).
int low=0,c=0;
int high=s-1;int mid;
do
{ mid=(low+high)/2;
if(sn==array[mid])
{ cout<<sn<<" is fount at ["<<mid<<"]\t"<<array[mid]<<endl;
c=c+1;}
else if(sn<array[mid])
{
high=mid-1;
} else if(sn>array[mid])
{ low=mid+1;
}
}while(low<=high&&c==0);
05/16/2025 Ataklti N. 10
if (c==0) cout<<“ element is not found”);
3.1.3 Exponential Search and Jump Search
• Exponential search is also known as doubling or galloping search.
• This mechanism is used to find the range where the search key may present.
• Exponential search involves two steps:
1. Find range where element is present
2. Do Binary Search in above found range.
Jump Search
• like Binary Search, Jump Search is a searching algorithm for sorted arrays.
• The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed
steps or skipping some elements in place ofAtaklti
05/16/2025
searching
N.
all elements. 11
3.1.4 Sub-list Search (Search a linked list in another list)
• Given two linked lists, the task is to check whether the first list is present in 2nd list or not.
• Algorithm:
1- Take first node of second list.
2- Start matching the first list from this first node.
3- If whole lists match return true.
4- Else break and take first list to the first node again.
5- And take second list to its second node.
6- Repeat these steps until any of linked lists becomes empty.
7- If first list becomes empty then list found else not.
05/16/2025 Ataklti N. 12
3.2. Sorting Algorithms
Sorting is one of the most important operations performed by computers.
Sorting is a process of reordering a list of items in either increasing or decreasing order.
Sorting is nothing but arranging the data in ascending or descending order.
Sorting arranges data in a sequence which makes searching easier.
The following are simple sorting algorithms used to sort small-sized lists.
1. Insertion Sort
2. Selection Sort
3. Bubble Sort
Advanced Sorting
1) Quick Sort
2)05/16/2025
Merge Sort Ataklti N. 13
3.2.1. Insertion sort
The insertion sort works just like its name suggests - it inserts each item into its proper place
in the final list.
Insertion sorts works by taking elements from the list one by one and inserting them in their
current position into a new sorted list.
This approach is the same approach that you use for sorting a set of cards in your hand.
While playing cards, you pick up a card, start at the beginning of your hand and find the place
to insert the new card, insert it and move all the others up one place.
05/16/2025 Ataklti N. 14
….Continued
Basic Idea:
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be
sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
05/16/2025 Ataklti N. 15
….Continued
The array is searched sequentially and unsorted items are moved and inserted into the sorted
sub-list (in the same array).
This algorithm is not suitable for large data sets as its average and worst case complexity are
of Ο(n2), where n is the number of items.
05/16/2025 Ataklti N. 16
Insertion sort implementation
int temp;
for(int i=0;i<n;i++)
{
temp=array[i];
for(int j=i; j>0&&temp<array[j-1]; j--)
{
array[j]=array[j-1];
array[j-1]=temp;
}
05/16/2025 Ataklti N. 17
3.2.2. Selection Sort
Selection sort is a simple sorting algorithm.
The smallest element is selected from the unsorted array and swapped with the leftmost element, and
that element becomes a part of the sorted array.
This process continues moving unsorted array boundary by one element to the right.
Basic Idea:-
Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted
05/16/2025 Ataklti N. 18
This algorithm is not suitable for large data sets as its average and worst case complexities are of Ο(n 2),
Selection sort implementation
int temp,smallest;
for(int i=0;i<n;i++)
{
smallest=i;
for(int j=i+1;j<n;j++)
{
if(array[j]<array[smallest])
smallest=j;
}
temp=array[smallest];
array[smallest]=array[i];
array[i]=temp;
}
05/16/2025 Ataklti N. 19
3.2.3. Bubble sort
Bubble sort is a simple sorting algorithm.
This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements
are swapped if they are not in order.
Basic Idea:-
We assume list is an array of n elements.
Starting at the front, traverse the array, find the largest item, and move (or bubble) it to the top
With each subsequent iteration, find the next
largest item and bubble it up towards the top of the array
swap function swaps the values of the given array elements.
this algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n 2) where n is the number of
items.
05/16/2025 Ataklti N. 20
Implementation
Starting with the first item, assume that it is the largest
Compare it with the second item:
If the first is larger, swap the two,
Otherwise, assume that the second item is the largest
After one pass, the largest item must be the last in the list Start at the front again:
the second pass will bring the second largest element into the second last position
Repeat n – 1 times, after which, all entries will be in place
05/16/2025 Ataklti N. 21
Bubble sort Implementation
int temp;
for(int i=0;i<n;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(array[j]>array[j+1])
{
temp=array[j+1];
array[j+1]=array[j];
array[j]=temp;
05/16/2025
} Ataklti N. 22
3.2.4. Quick Sort
Quick sort is the fastest known algorithm.
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data
into smaller arrays.
It uses divide and conquer strategy and in the worst case its complexity is O(n logn).
Basic Idea:-
Choose a pivot value (mostly the first element is taken as the pivot value)
Position the pivot element and partition the list so that:
the left part has items less than or equal to the pivot value
the right part has items greater than or equal to the pivot value
Recursively sort the left part
Recursively sort the right part
05/16/2025 Ataklti N. 23
3.2.5. Merge Sort
Merge sort first divides the array into equal halves and then combines them in a sorted manner.
Like quick sort, merge sort uses divide and conquer strategy and its time complexity is O(nlogn).
• Basic Idea:
– Divide the array in to two halves.
– Recursively sort the first n/2 items.
– Recursively sort the last n/2 items.
– Divide these arrays and we achieve atomic value which can no more be divided.
– Merge the smaller lists into new list in sorted order.
05/16/2025 Ataklti N. 24
3.2.6 Heap Sort
• Heap sort is a comparison-based sorting technique based on Binary Heap data structure.
• A Binary Heap is a Complete Binary Tree where items are stored in a special order such that
the value in a parent node is greater(or smaller) than the values in its two children nodes.
• The parent node is greater than the values in its two children nodes all over the tree is called
max heap and parent node is smaller than the values in its two children nodes all over the
tree is called min-heap.
• The heap can be represented by a binary tree or array in term of Max Heap or min heap.
05/16/2025 Ataklti N. 25
Working of Heap Sort
1. Since the tree satisfies Max-Heap property, then the largest item is stored at the root node.
2. Swap: Remove the root element and put at the end of the array (nth position) Put the last
item of the tree (heap) at the vacant place.
3. Remove: Reduce the size of the heap by 1.
4. Heapify: Heapify the root element again so that we have the highest element at root.
5. The process is repeated until all the items of the list are sorted.
05/16/2025 Ataklti N. 26
3.2.7 Radix Sort
• The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most
significant digit.
• Radix sort uses counting sort as a subroutine to sort.
• The Radix Sort Algorithm
1. Do following for each digit i where i varies from least significant digit to the most significant
digit.
1. Sort input array using counting sort (or any stable sort) according to the i’th digit.
2. Now, go through each significant place one by one.
05/16/2025 Ataklti N. 27
