Unit-V
Searching: finding a specific elements in a given list of elements.
2 types of searchings:
1.Linear search
2.Binary search
Pseudo code:- is a code to write an algorith.
Linear Search: element is searched in sequential manner.
===========
Algorithm
Linear Search ( Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
Pseudocode
procedure linear_search (list,value)
for each item in the list
if match item ==value
return the item's location
end if
end for
end procedure
//C program for linear search using a function
#include <stdio.h>
int linear_search(int [], int, int);
int main()
{
int array[100], search, c, n, position;
printf("Input number of elements in array\n");
scanf("%d", &n);
printf("Input %d numbers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Input a number to search\n");
scanf("%d", &search);
position = linear_search(array, n, search);
if (position == -1)
printf("%d isn't present in the array.\n", search);
else
printf("%d is present at location %d.\n", search, position+1);
return 0;
}
int linear_search(int a[], int n, int find) {
for (int c = 0 ;c < n ; c++ ) {
if (a[c] == find)
return c;
}
return -1;
}
output2
Linear search without function
=======================
//C program for linear search using a function
#include <stdio.h>
int main()
{
int a[100], search, c, n, position;
printf("Input number of elements in array\n");
scanf("%d", &n);
printf("Input %d numbers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &a[c]);
printf("Input a number to search\n");
scanf("%d", &search);
for ( c = 0 ;c < n ; c++ )
{
if (a[c] == search)
{
printf("%d is found at %d",search,c+1);
break;
}
}
if(c>=n)
printf("%d is not found in the given list",search);
}
output2
Binary Search
Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].
A simple approach is to do linear search.The time complexity of above algorithm is O(n).
Another approach to perform the same task is using Binary Search.
Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin
with an interval covering the whole array. If the value of the search key is less than the item in
the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper
half. Repeatedly check until the value is found or the interval is empty.
Example :
The idea of binary search is to use the information that the array is sorted and reduce the time
complexity to O(Log n)
We basically ignore half of the elements just after one comparison.
1. Compare x with the middle element.
2. If x matches with middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in right half subarray after the
mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half.
Iterative Binary SearchProgram(Non-recursive)
// C program to implement iterative Binary Search
#include <stdio.h>
// A iterative binary search function. It returns
// location of x in given array arr[l..r] if present,
// otherwise -1
intbinarySearch(intarr[], intl, intr, intx) //x=20
{
while(l <= r) {
intm = (l + r) / 2; 3
// Check if x is present at mid
if(arr[m] == x)
returnm;
// If x greater, ignore left half
if(arr[m] < x)
l = m + 1; //4
// If x is smaller, ignore right half
else
r = m - 1; //3
}
// if we reach here, then element was
// not present
return-1;
}
intmain()
{
intarr[] = { 2, 3, 4, 10, 40 };
intn = sizeof(arr) / sizeof(arr[0]);
intx = 10;
intresult = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present"
" in array")
: printf("Element is present at "
"index %d",
result);
return0;
}
Recursive Binary Search Program
// C program to implement recursive Binary Search
#include <stdio.h>
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
intbinarySearch(intarr[], intl, intr, intx)
{
if(r >= l) {
intmid = (l + r) / 2;
// If the element is present at the middle
// itself
if(arr[mid] == x)
returnmid;
// If element is smaller than mid, then
// it can only be present in left subarray
if(arr[mid] > x)
returnbinarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
returnbinarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return-1;
}
intmain(void)
{
intarr[] = { 2, 3, 4, 10, 40 };
intn = sizeof(arr) / sizeof(arr[0]);
intx = 10;
intresult = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return0;
}
Time Complexity of Binary Search Algorithm is O(log2n).
Sorting Algorithms
sorting means arranging the given elements in sorting order i.e,, either ascending or descending
order.
Sorting algorithms are the algorithms meant for sorting the given elements i.e, either ascending
or descending order.
1.Bubble sort
2.Insertion sort
3.Selection sort
Bubble sort:
How Bubble Sort Works?
Example:
We take an unsorted array for our example. Bubble sort takes Ο(n 2) time so we're keeping it
short and precise.
Bubble sort starts with very first two elements, comparing them to check which one is greater.
In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33
with 27.
We find that 27 is smaller than 33 and these two values must be swapped.
The new array should look like this −
Next we compare 33 and 35. We find that both are in already sorted positions.
Then we move to the next two values, 35 and 10.
We know then that 10 is smaller 35. Hence they are not sorted.
We swap these values. We find that we have reached the end of the array. After one iteration,
the array should look like this −
To be precise, we are now showing how an array should look like after each iteration. After the
second iteration, it should look like this −
Notice that after each iteration, at least one value moves at the end.
And when there's no swap required, bubble sorts learns that an array is completely sorted.
Algorithm:
We assume list is an array of n elements. We further assume that swap function swaps the
values of the given array elements.
beginBubbleSort(list)
for all elements of list
if list[i]> list[i+1]
swap(list[i], list[i+1])
endif
endfor
return list
endBubbleSort
Pseudocode of BubbleSort algorithm can be written as follows −
procedure bubbleSort( list : array of items )
loop = list.count;
for i =0 to loop-1do:
swapped =false
for j =0 to loop-1do:
/* compare the adjacent elements */
if list[j]> list[j+1]then
/* swap them */
swap( list[j], list[j+1])
swapped =true
endif
endfor
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped)then
break
endif
endfor
end procedure return list
Program:
/ C program for implementation of Bubble sort
#include <stdio.h>
voidswap(int*xp, int*yp)
{
inttemp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
voidbubbleSort(intarr[], intn)
{
inti, j;
for(i = 0; i < n-1; i++) //rounds=0,1,2,3,4, 5 =6 rounds= n-1 rounds
// Last i elements are already in place
for(j = 0; j < n-i-1; j++) iteration=<6=0-----4=
if(arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
/* Function to print an array */
voidprintArray(intarr[], intsize)
{
inti;
for(i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
intmain()
{
intarr[] = {64, 34, 25, 12, 22, 11, 90};
intn = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return0;
}
Sorted array:
11 12 22 25 34 64 90
Selection sort
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-
based algorithm in which the list is divided into two parts, the sorted part at the left end and the
unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the
entire list.
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.
This algorithm is not suitable for large data sets as its average and worst case complexities are
of Ο(n2), where n is the number of items.
How Selection Sort Works?
Consider the following depicted array as an example.
For the first position in the sorted list, the whole list is scanned sequentially. The first position
where 14 is stored presently, we search the whole list and find that 10 is the lowest value.
So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the
list, appears in the first position of the sorted list.
For the second position, where 33 is residing, we start scanning the rest of the list in a linear
manner.
We find that 14 is the second lowest value in the list and it should appear at the second place.
We swap these values.
After two iterations, two least values are positioned at the beginning in a sorted manner.
The same process is applied to the rest of the items in the array.
Following is a pictorial depiction of the entire sorting process −
Now, let us learn some programming aspects of selection sort.
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
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted
Pseudocode
procedure selection sort
list : array of items
n : size of list
for i =1 to n -1
/* set current element as minimum*/
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j]< list[min]then
min = j;
endif
endfor
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min]and list[i]
endif
endfor
end procedure
Program:
#include<stdio.h>
#include<stdbool.h>
#define MAX 7
int intArray[MAX]={4,6,3,2,1,9,7};
void printline(int count){
int i;
for(i =0;i < count-1;i++){
printf("=");
}
printf("=\n");
}
void display(){
int i;
printf("[");
// navigate through all items
for(i =0;i < MAX;i++){
printf("%d ", intArray[i]);
}
printf("]\n");
}
void selectionSort(){
int indexMin,i,j;
// loop through all numbers
for(i =0; i < MAX-1; i++){
// set current element as minimum
indexMin = i;
// check the element to be minimum
for(j = i+1;j < MAX;j++){
if(intArray[j]< intArray[indexMin]){
indexMin = j;
}
}
if(indexMin != i){
printf("Items swapped: [ %d, %d ]\n", intArray[i], intArray[indexMin]);
// swap the numbers
int temp = intArray[indexMin];
intArray[indexMin]= intArray[i];
intArray[i]= temp;
}
printf("Iteration %d#:",(i+1));
display();
}
}
void main(){
printf("Input Array: ");
display();
printline(50);
selectionSort();
printf("Output Array: ");
display();
printline(50);
}
If we compile and run the above program, it will produce the following result −
Output
Input Array: [4 6 3 2 1 9 7 ]
==================================================
Items swapped: [ 4, 1 ]
Iteration 1#:[1 6 3 2 4 9 7 ]
Items swapped: [ 6, 2 ]
Iteration 2#:[1 2 3 6 4 9 7 ]
Iteration 3#:[1 2 3 6 4 9 7 ]
Items swapped: [ 6, 4 ]
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
Items swapped: [ 9, 7 ]
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================
Funda is : Every time find the smallest element and place it in its position
https://www.youtube.com/watch?v=9oWd4VJOwr0 (source)
Time complexity in both best and worst cases is : O(n2)
Insetion sort:
This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is
always sorted. For example, the lower part of an array is maintained to be sorted. An element
which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has to
be inserted there. Hence the name, insertion sort.
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.
How Insertion Sort Works?
We take an unsorted array for our example.
Insertion sort compares the first two elements.
It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.
Insertion sort moves ahead and compares 33 with 27.
And finds that 33 is not in the correct position.
It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the
sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list
remains sorted after swapping.
By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.
These values are not in a sorted order.
So we swap them.
However, swapping makes 27 and 10 unsorted.
Hence, we swap them too.
Again we find 14 and 10 in an unsorted order.
We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items.
This process goes on until all the unsorted values are covered in a sorted sub-list. Now we shall
see some programming aspects of insertion sort.
Algorithm
Now we have a bigger picture of how this sorting technique works, so we can derive simple
steps by which we can achieve insertion sort.
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
Pseudocode
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i =1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition >0and A[holePosition-1]> valueToInsert
do:
A[holePosition]= A[holePosition-1]
holePosition = holePosition -1
endwhile
/* insert the number at hole position */
A[holePosition]= valueToInsert
endfor
end procedure
Program:
Live Demo
#include<stdio.h>
#include<stdbool.h>
#define MAX 7
int intArray[MAX]={4,6,3,2,1,9,7};
void printline(int count){
int i;
for(i =0;i < count-1;i++){
printf("=");
}
printf("=\n");
}
void display(){
int i;
printf("[");
// navigate through all items
for(i =0;i < MAX;i++){
printf("%d ",intArray[i]);
}
printf("]\n");
}
void insertionSort(){
int valueToInsert;
int holePosition;
int i;
// loop through all numbers
for(i =1; i < MAX; i++){
// select a value to be inserted.
valueToInsert = intArray[i];
// select the hole position where number is to be inserted
holePosition = i;
// check if previous no. is larger than value to be inserted
while(holePosition >0&& intArray[holePosition-1]> valueToInsert){
intArray[holePosition]= intArray[holePosition-1];
holePosition--;
printf(" item moved : %d\n", intArray[holePosition]);
}
if(holePosition != i){
printf(" item inserted : %d, at position : %d\n", valueToInsert,holePosition);
// insert the number at hole position
intArray[holePosition]= valueToInsert;
}
printf("Iteration %d#:",i);
display();
}
}
void main(){
printf("Input Array: ");
display();
printline(50);
insertionSort();
printf("Output Array: ");
display();
printline(50);
}
If we compile and run the above program, it will produce the following result −
Output
Input Array: [4 6 3 2 1 9 7 ]
==================================================
Iteration 1#:[4 6 3 2 1 9 7 ]
item moved : 6
item moved : 4
item inserted : 3, at position : 0
Iteration 2#:[3 4 6 2 1 9 7 ]
item moved : 6
item moved : 4
item moved : 3
item inserted : 2, at position : 0
Iteration 3#:[2 3 4 6 1 9 7 ]
item moved : 6
item moved : 4
item moved : 3
item moved : 2
item inserted : 1, at position : 0
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
item moved : 9
item inserted : 7, at position : 5
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================
source is: https://www.youtube.com/watch?v=yCxV0kBpA6M
Key Point:-We keep on dividing the current list into sorted and unsorted sub lists, we take one
element at a time from every new unsorted sublist and place it in a correct position in a every
new sorted list. We compare element in unsorted list with the elements of sorted list in reverse
direction to place in correct place.
Best case time complexity: O(n)
Wortst case time complxity: O(n2)
