UNIT – IV

Department of Computer Science

SEARCHING & SORTING
SEARCHING
 In C Programming searching is a process to
find whether a target element is present in
the given list of elements or not.

 Ifthe given element is present in the list, then

we have to find that what is the location of
target element.

 Following are the two common search

algorithms or techniques
 1) Linear Search
 2) Binary Search
LINEAR SEARCH
 Linear Search is defined as a sequential search
algorithm that starts at one end and goes through
each element of a list until the desired element is
found, otherwise the search continues till the end
of the data set.

 How Does Linear Search Algorithm Work?

 Every element is considered as a potential match
for the key and checked for the same.

 If any element is found equal to the key, the

search is successful and the index of that element
is returned.

 Ifno element is found equal to the key, the search

yields “No match found”.
LINEAR SEARCH (CONT…)
 Example of Linear Search Algorithm
 Consider an array of size 7 with elements 13, 9,
21, 15, 39, 19, and 27 that starts with 0 and ends
with size minus one, 6.
 Search element = 39

 Step 1: The searched element 39 is compared to

the first element of an array, which is 13.

 Thematch is not found, you now move on to the

next element and try to implement a comparison.
LINEAR SEARCH (CONT…)
 Step 2: Now, search element 39 is compared
to the second element of an array, 9.

 As both are not matching, you will continue

the search.
 Step 3: Now, search element 39 is compared
with the third element, which is 21.

 Again,
both the elements are not matching,
you move onto the next following element.
LINEAR SEARCH (CONT…)
 Step 4: Next, search element 39 is compared with the
fourth element, which is 15.

 As both are not matching, you move on to the next

element.
 Step 5: Next, search element 39 is compared with the
fifth element 39.

 A perfect match is found, you stop comparing any

further elements and terminate the Linear Search
Algorithm and display the element found at location 4.
LINEAR SEARCH ALGORITHM
 Linear Search ( Array Arr, Value a ) // Arr is the
name of the array, and a is the searched element.
 Step 1: Set i to 0 // i is the index of an array
which starts from 0
 Step 2: if i > n then go to step 7 // n is the number
of elements in array
 Step 3: if Arr[i] = a then go to step 6
 Step 4: Set i to i + 1
 Step 5: Goto step 2
 Step 6: Print element a found at index i and go to
step 8
 Step 7: Print element not found
 Step 8: Exit
LINEAR SEARCH PROGRAM
 #include<stdio.h>
 void main(){
 int i, key;
 int a[10]={1,2,3,4,5,6,7,8,9};
 printf("Enter Element to be searched \n");
 scanf("%d",&key);
 for(i=0;i<9;i++)
 {
 if(a[i]==key)
 {
 printf("Element found at %d position",i);
 break;
 }
 }
 if(i==9)
 printf("Element NOT FOUND");
 }
BINARY SEARCH
 Binary search technique is the faster search
mechanism as compared to linear search algorithm.

 To apply binary search technique the elements given

in the list must be in sorted sequence.

 In this technique first of all the element present at the

middle position is matched with the target value to be
searched.

 If the value found at the middle position then the

corresponding index (position) is returned otherwise
the process is repeated with the left half or right half of
the list depending upon whether the target value is
smaller or larger than the value present at the mid
position.
BINARY SEARCH ALGORITHM
 Step1: Find middle element at index ‘mid’.

 Step 2: Compare the value at ‘mid’ with the

target value ‘val’.

 Step 3: If the value ‘val’ is matched with the

middle value, then return middle value
otherwise check whether ‘val’ is smaller or
larger than ‘mid’ value.

 Step4: Repeat the process from step 1 to step

3 with left half if the ‘val’ is less than ‘mid’
value otherwise choose right half.
EXAMPLE
BINARY SEARCH PROGRAM
 #include<stdio.h>
 void main()
 {
 int i,mid,beg=0,end=9,key;
 int a[10];

 printf("Enter Sorted Elements of Array A \n");
 for(i=0;i<10;i++)
 scanf("%d",&a[i]);

 printf("Enter Element to be Searched \n");
 scanf("%d",&key);

 while(beg<=end)
 {
 mid=(beg+end)/2;

BINARY SEARCH PROGRAM
 if(a[mid]==key)
 {
 printf("Element found at position: %d \n",mid);
 break;
 }

 else
 {
 if(key<a[mid])
 end=mid-1;
 else
 beg=mid+1;
 }
 }

 if(beg>end)
 printf("Element Not Present in List \n");
 }
SORTING
 In programming sorting is defined as the
process of arranging the elements in the given
list in increasing or decreasing order.

 Followings are the most commonly used

techniques of sorting:
 Bubble Sort
 Selection Sort
 Insertion Sort
BUBBLE SORT
 It is the simplest sort method which performs
sorting by repeatedly moving the largest element
to the highest index of the array.

 It comprises of comparing each element to its

adjacent element and replace them accordingly.

 Itis called bubble sort because the movement of

array elements is just like the movement of air
bubbles in the water.

 Bubbles in water rise up to the surface; similarly,

the array elements in bubble sort move to the end
in each iteration.
BUBBLE SORT (CONT…)
 Althoughit is simple to use, it is primarily
used as an educational tool because the
performance of bubble sort is poor in the real
world.

 Itis not suitable for large data sets. The

average and worst-case complexity of Bubble
sort is O(n2), where n is a number of items.

 Bubbleshort is majorly used where –

 Complexity does not matter
 Simple and shortcode is preferred
BUBBLE SORT (CONT…)
Algorithm
 Step 1: Traverse from left and compare
adjacent elements and the higher one is
placed at right side.

 Step2: In this way, the largest element is

moved to the rightmost end at first.

 Step 3: Repeat step 2 & 3 to find the second

largest and place it and so on until the data is
sorted.
BUBBLE SORT (CONT…)
Algorithm
 begin BubbleSort(arr)

 for all array elements

 if arr[i] > arr[i+1]

 swap(arr[i], arr[i+1])
 end if
 end for

 return arr

 end BubbleSort
BUBBLE SORT (CONT…)
 How does Bubble Sort Work?
 Let us understand the working of bubble sort with the
help of the following illustration:

 Input: arr[] = {6, 3, 0, 5}

 First Pass:
 The largest element is placed in its correct position,
i.e., the end of the array.
BUBBLE SORT (CONT…)
 Second Pass:
 Place the second largest element at correct
position
BUBBLE SORT (CONT…)
 Third Pass:
 Place the remaining two elements at their
correct positions.
BUBBLE SORT (CONT…)
 #include<stdio.h>
 void main()
{
 int i,j,temp,n,a[10];

 printf("Enter Elements in Array \n");
 for(i=0;i<10;i++)
 {
 scanf("%d",&a[i]);
 }

 for(i=0;i<10;i++)
 {

BUBBLE SORT (CONT…)
 for(j=0;j<10-i;j++)
 {
 if(a[j]>a[j+1])
 {
 temp=a[j];
 a[j]=a[j+1];
 a[j+1]=temp;
 }
 }
 }

 printf("Sorted Array is: \n");
 for(i=0;i<10;i++)
 printf("%d \t",a[i]);
 }
INSERTION SORT
 Insertion sort is an algorithm used to sort a collection
of elements in ascending or descending order.

 The basic idea behind the algorithm is to divide the list

into two parts: a sorted part and an unsorted part.

 Initially, the sorted part contains only the first

element of the list, while the rest of the list is in the
unsorted part.

 The algorithm then iterates through each element in

the unsorted part, picking one at a time, and inserts it
into its correct position in the sorted part.

 To do this, the algorithm compares the current element

with each element in the sorted part, starting from the
rightmost element.
INSERTION SORT (CONT…)
 It continues to move to the left until it finds an element
that is smaller (if sorting in ascending order) or larger
(if sorting in descending order) than the current
element.

 Once the correct position has been found, the algorithm

shifts all the elements to the right of that position to
make room for the current element, and then inserts
the current element into its correct position.

 This process continues until all the elements in the

unsorted part have been inserted into their correct
positions in the sorted part, resulting in a fully sorted
list.

 It has a time complexity of O(n^2), which makes it

suitable for small datasets, but not for large ones.
INSERTION SORT (CONT…)
Algorithm
 Step 1 - If the element is the first element, assume that it
is already sorted. Return 1.

 Step2 - Pick the next element, and store it separately in a

key.

 Step3 - Now, compare the key with all elements in the

sorted array.

 Step 4 - If the element in the sorted array is smaller than

the current element, then move to the next element. Else,
shift greater elements in the array towards the right.

 Step 5 - Insert the value.

 Step 6 - Repeat until the array is sorted.

INSERTION SORT (CONT…)
 Working of Insertion Sort algorithm
 Consider an example: arr[]: {12, 11, 13, 5, 6}

 First Pass:
INSERTION SORT (CONT…)
 Second Pass:
INSERTION SORT (CONT…)
 Third Pass:
INSERTION SORT (CONT…)
 Fourth Pass:
INSERTION SORT (CONT…)
INSERTION SORT (CONT…)
INSERTION SORT (CONT…)
 Program:

#include <stdio.h>
void main()
{
int n, i, j, temp;
int arr[64];

printf("Enter number of elements\n");

scanf("%d", &n);

printf("Enter %d integers\n", n);

for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
INSERTION SORT (CONT…)
for (i = 1; i < n; i++)
{
j = i;
while (j > 0 && arr[j - 1] > arr[j])
{
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
printf("Sorted list in ascending order:\n");
for (i = 0; i < n; i++)
{
printf("%d \t", arr[i]);
}
}
SELECTION SORT
 In this algorithm, the array is divided into two parts,
first is sorted part, and another one is the unsorted
part.

 Initially, the sorted part of the array is empty, and

unsorted part is the given array. Sorted part is placed
at the left, while the unsorted part is placed at the
right.

 In selection sort, the first smallest element is selected

from the unsorted array and placed at the first
position. After that second smallest element is selected
and placed in the second position. The process
continues until the array is entirely sorted.

 The average and worst-case complexity of selection sort

is O(n2), where n is the number of items. Due to this, it
is not suitable for large data sets.
SELECTION SORT (CONT…)
 Algorithm
 Step 1 − Set MIN to location 0

 Step 2 − Search the minimum element in the

list.

 Step 3 − Swap with value at location MIN.

 Step4 − Increment MIN to point to next

element.

 Step 5 − Repeat until list is sorted.

SELECTION SORT (CONT…)
SELECTION SORT (CONT…)
 Selection Sort Algorithm working
 Lets consider the following array as an example: arr[]
= {64, 25, 12, 22, 11}

 First Pass:
 For the first position in the sorted array, the whole
array is traversed from index 0 to 4 sequentially.

 The first position where 64 is stored presently, after

traversing whole array it is clear that 11 is the lowest
value.

 Thus, replace 64 with 11. After one iteration 11, which

happens to be the least value in the array, tends to
appear in the first position of the sorted list.
SELECTION SORT (CONT…)
SELECTION SORT (CONT…)
 Second Pass:
 For the second position, where 25 is present,
again traverse the rest of the array in a
sequential manner.

 Aftertraversing, we found that 12 is the second

lowest value in the array and it should appear at
the second place in the array, thus swap these
values.
SELECTION SORT (CONT…)
 Third Pass:
 Now, for third place, where 25 is present again
traverse the rest of the array and find the third
least value present in the array.

 While traversing, 22 came out to be the third

least value and it should appear at the third place
in the array, thus swap 22 with element present
at third position.
SELECTION SORT (CONT…)
 Fourth Pass:
 Similarly, for fourth position traverse the rest
of the array and find the fourth least element
in the array

 As 25 is the 4th lowest value hence, it will

place at the fourth position.
SELECTION SORT (CONT…)
 Fifth Pass:
 At last the largest value present in the array
automatically get placed at the last position in
the array

 The resulted array is the sorted array.

SELECTION SORT (CONT…)
 Program

#include <stdio.h>
void main()
{
int array[100], n, i, j, min, t;

printf("Enter number of elements\n");

scanf("%d", &n);

printf("Enter %d integers\n", n);

for (i = 0; i < n; i++)
scanf("%d", &array[i]);

for (i = 0; i < (n - 1); i++) // finding minimum element (n-1) times

{
min = i;
SELECTION SORT (CONT…)
for (j = i + 1; j < n; j++)
{
if (array[min] > array[j])
min = j;
}
if (min != i)
{
t = array[i];
array[i] = array[min];
array[min] = t;
}
}

printf("Sorted list in ascending order:\n");

for (i = 0; i < n; i++)

printf("%d \t", array[i]);
}
LINEAR SEARCH VS BINARY SEARCH

S. No. Linear Search Binary Search

In linear search input data In binary search input data

1
need not to be in sorted. need to be in sorted order.

It is also called sequential It is also called half-interval

2
search. search.

The time complexity of linear The time complexity of binary

3
search O(n). search O(log n).

Multidimensional array can Only single dimensional

4
be used. array is used.

5 It is less complex. It is more complex.

6 It is very slow process. It is very fast process.

INSERTION SORT VS SELECTION SORT
S.
Insertion Sort Selection Sort
No.
Inserts the value in the pre-sorted Finds the minimum / maximum
1 array to sort the set of values in number from the list and sort it
the array. in ascending / descending order.

It is an unstable sorting
2 It is a stable sorting algorithm.
algorithm.

The best-case time complexity is

For best case, worst case and
Ω(N) when the array is already in
3 average selection sort have
ascending order. It have Θ(N2) in
complexity Θ(N2).
worst case and average case.

It is more efficient than the It is less efficient than the

4
Selection sort. Insertion sort.

The number of comparison The number of comparison

operations performed in this operations performed in this
5
sorting algorithm is less than the sorting algorithm is more than
swapping performed. the swapping performed.