Unit-3

Searching and Sorting

What is Searching?

Searching is the fundamental process of locating a specific element or item

within a collection of data. This collection of data can take various forms,
such as arrays, lists, trees, or other structured representations. The primary
objective of searching is to determine whether the desired element exists
within the data, and if so, to identify its precise location or retrieve it. It plays
an important role in various computational tasks and real-world applications,
including information retrieval, data analysis, decision-making processes,
and more.

Linear Search Algorithm:

The linear search algorithm 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 dataset.
Linear search is a method for searching for an element in a collection of
elements. In linear search, each element of the collection is visited one by
one in a sequential fashion to find the desired element. Linear search is also
known as sequential search. For searching operations in smaller arrays,
and linear search is applicable for both sorted array and unsorted array.

Program for linear search

#include<stdio.h>
int main()
{
int array[10];
int value_search;
int i,n=10;
printf("enter the elements");
for(i=0;i<10;i++)
{
scanf("%d",&array[i]);
}
printf("enter the element to be searched\n");
scanf("%d",&value_search);
for(i=0;i<10;i++)
{
if(array[i]==value_search)
{
printf("\nelement is found at %d index",i);
break;
}
 }
if(i==n)
{
printf("\nelement is not in the list");
}

How Linear Search Works?

The following steps are followed to search for an element k = 1 in the list
below.

Input elements:

1.Start from the first element, compare k with each element x.

2.If x == k, return the index

 3.Else, return not found.

Binary Search

Binary Search is a searching algorithm for finding an element's position in a

sorted array.
Binary search can be implemented only on a sorted list of items. If the
elements are not sorted already, we need to sort them first.

1. The array in which searching is to be performed is:

Let x = 4 be the element to be searched.

2. Set two pointers low and high at the lowest and the highest positions

respectively.
Setting pointers
3. Find the middle position mid of the array ie. mid = (low +
high)/2 and arr[mid] = 6.

Mid element
4. If x == arr[mid], then return mid. Else, compare the element to be
searched with arr[mid].
5. If x > arr[mid], compare x with the middle element of the elements on
the right side of arr[mid]. This is done by setting low to low = mid + 1.
 6. Else, compare x with the middle element of the elements on the left
side of arr[mid]. This is done by setting high to high = mid - 1.

7. Finding mid element

8. Repeat steps 3 to 6 until low meets high.

9. Mid element

10. x = 4 is found.

Advantages of Binary Search:

 Binary search is faster than linear search, especially for large arrays.
 More efficient than other searching algorithms with a similar time
complexity, such as interpolation search or exponential search.
 Binary search is well-suited for searching large datasets that are stored
in external memory, such as on a hard drive or in the cloud.
Disadvantages of Binary Search:
 The array should be sorted.
 Binary search requires that the data structure being searched be
stored in contiguous memory locations.
 Binary search requires that the elements of the array be comparable,
meaning that they must be able to be ordered.
 Sorting algorithm:

A Sorting Algorithm is used to rearrange a given array or list of elements

according to a comparison operator on the elements. The comparison
operator is used to decide the new order of elements in the respective data
structure.
 In-place Sorting: An in-place sorting algorithm uses constant space for
producing the output (modifies the given array only) or copying
elements to temporary storage. Examples: Selection Sort, Bubble Sort
Insertion Sort and Heap Sort.
 Internal Sorting: Internal Sorting is when all the data is placed in
the main memory or internal memory. In internal sorting, the problem
cannot take input beyond its size. Example: heap sort, bubble sort,
selection sort, quick sort, shell sort, insertion sort.
 External Sorting : External Sorting is when all the data that needs to be
sorted cannot be placed in memory at a time, the sorting is called
external sorting. External Sorting is used for the massive amount of
data. Examples: Merge sort, Tag sort, Polyphase sort, Four tape sort,
External radix sort, etc.
 Stable sorting: When two same items appear in the same order in
sorted data as in the original array called stable sort. Examples: Merge
Sort, Insertion Sort, Bubble Sort.
 Unstable sorting: When two same data appear in the different order in
sorted data it is called unstable sort. Examples: Selection Sort, Quick
Sort, Heap Sort, Shell Sort.

1. Quick Sort: A highly efficient divide-and-conquer algorithm that

partitions the array around a pivot element, and recursively sorts the
sub-arrays.
2. Insertion Sort: A simple and efficient algorithm for sorting small
datasets or partially sorted arrays by iteratively inserting elements into
their correct positions.
3. Bubble Sort: A straightforward algorithm that repeatedly swaps
adjacent elements if they are in the wrong order, gradually “bubbling”
the largest elements to the end of the array.
4. Selection Sort: An in-place sorting algorithm that repeatedly finds the
minimum element from the unsorted part of the array and swaps it
with the first element of the unsorted part.
5. Merge Sort:

Explanation of sorting algorithms

Bubble Sort:
Bubble sort is a sorting stable, in place, comparison and internal sorting
algorithm.
Bubble sort is a sorting algorithm that compares two adjacent elements and
swaps them until they are in the intended order.

Suppose we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)
1. Starting from the first index, compare the first and the second
elements.
2. If the first element is greater than the second element, they are
swapped.
3. Now, compare the second and the third elements. Swap them if they
are not in order.
4. The above process goes on until the last element.

The same process goes on for the remaining iterations.

After each iteration, the largest element among the unsorted elements is
placed at the end.
Put the largest element at the end
In each iteration, the comparison takes place up to the last unsorted
element.

Compare the adjacent elements

Insertion sort:

Insertion sort is a simple sorting algorithm that works by iteratively inserting

each element of an unsorted list into its correct position in a sorted portion of
the list. It is a stable sorting algorithm, meaning that elements with equal
values maintain their relative order in the sorted output or Insertion sort is
a simple sorting algorithm that works by building a sorted array one element
at a time. It is considered an ” in-place ” sorting algorithm, meaning it
doesn’t require any additional memory space beyond the original array.

Program for insertion sort:

#include<stdio.h>
int main()
{
int array[5];
int key, j,i;
printf("enter the values of array\n");
for(i=0;i<5;i++)
{
scanf("%d",&array[i]);
}
for(i = 1; i<5; i++) {
key = array[i];//take value
j = i;
while(j >= 0 && array[j-1]>key) {
array[j] = array[j-1];
j--;
}
array[j] = key; //insert in right place
}
printf("sorted ouptout\n");
for(i=0;i<5;i++)
{
printf(" %d",array[i]);
}
}

Working of insertion sort algorithm:

To achieve insertion sort, follow these steps:
 We start with second element of the array as first element in the array
is assumed to be sorted.
 Compare second element with the first element and check if the
second element is smaller then swap them.
 Move to the third element and compare it with the second element,
then the first element and swap as necessary to put it in the correct
position among the first three elements.
 Continue this process, comparing each element with the ones before it
and swapping as needed to place it in the correct position among the
sorted elements.
 Repeat until the entire array is sorted.
Working of Insertion Sort
Suppose we need to sort the following array.

Initial array
1. The first element in the array is assumed to be sorted. Take the second
element and store it separately in key.

Compare key with the first element. If the first element is greater
than key, then key is placed in front of the first element.

If the first element is greater than key, then key is placed in front of the
first element.
2. Now, the first two elements are sorted.

Take the third element and compare it with the elements on the left of
it. Placed it just behind the element smaller than it. If there is no
 element smaller than it, then place it at the beginning of the array.

Place 1 at the beginning

3. Similarly, place every unsorted element at its correct position.

Selection sort:

Selection sort is a simple sorting algorithm. This sorting algorithm, like

insertion sort, 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 boundaries by one element to
the right.

Algorithm:
Algorithm: Selection-Sort (A)
fori← 1 to n-1 do
min j ←i;
min x ← A[i]
for j ←i + 1 to n do
if A[j] < min x then
 min j ← j
min x ← A[j]
A[min j] ← A [i]
A[i] ← min x

Working of Selection Sort

1. Set the first element as minimum. Select first element as minimum

2. Compare minimum with the second element. If the second element is
smaller than minimum, assign the second element as minimum.

Compare minimum with the third element. Again, if the third element
is smaller, then assign minimum to the third element otherwise do
nothing. The process goes on
until the last element. Compare minimum with the remaining elements

3. After each iteration, the minimum is placed in the front of the unsorted
list.

Swap the first with minimum

4. For each iteration, indexing starts from the first unsorted element. Step
1 to 3 are repeated until all the elements are placed at their correct
positions.
Quick sort:

Quick sort is a highly efficient sorting algorithm and is based on partitioning

of array of data into smaller arrays. A large array is partitioned into two
arrays one of which holds values smaller than the specified value, say pivot,
based on which the partition is made and another array holds values greater
than the pivot value.
Quicksort partitions an array and then calls itself recursively twice to sort the
two resulting subarrays. This algorithm is quite efficient for large-sized data
sets as its average and worst-case complexity are O(n2), respectively

Algorithm:
1. Choose the highest index value has pivot
2. Take two variables to point left and right of the list
excluding pivot
3. Left points to the low index
4. Right points to the high
5. While value at left is less than pivot move right
6. While value at right is greater than pivot move left
7. If both step 5 and step 6 does not match swap left and right
8. If left ≥ right, the point where they met is new pivot

Merge Sort:

Merge Sort is one of the most popular sorting algorithms that is based on the
principle of Divide and Conquer Algorithm.
Here, a problem is divided into multiple sub-problems. Each sub-problem is
solved individually. Finally, sub-problems are combined to form the final
solution.