SORTING & SEARCHING

LINEAR SEARCH

Assume that item is in an array in random order and we have to find an item. Then the only
way to search for a target item is, to begin with, the first position and compare it to the target.
If the item is at the same, we will return the position of the current item. Otherwise, we will
move to the next position. If we arrive at the last position of an array and still can not find the
target, we return -1. This is called the Linear search or Sequential search.

Code for linear search

// Linear Search in C

#include <stdio.h>

int search(int array[], int n, int x)

{

// Going through array sequencially

for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}

BINARY SEARCH

In a binary search, however, cut down your search to half as soon as you find the middle of a
sorted list. The middle element is looked at to check if it is greater than or less than the value
to be searched. Accordingly, a search is done to either half of the given list
Below is the code syntax for the binary search.
#include <stdio.h>

int binarySearch(int array[], int x, int low, int high)

{
// Repeat until the pointers low and high meet each
// other

1
 while (low <= high) {
int mid = low + (high - low) / 2;

if (array[mid] == x)
return mid;

if (array[mid] < x)
low = mid + 1;

else
high = mid - 1;
}

return -1;
}

2
SORTING:
Sorting means arranging a set of data in some order. There are different methods that
are used to sort the data in ascending or descending order. These methods can be divided into
two types internal sorting and external sorting.
The internal sorting is a sorting in which the resides in the main memory of the
computer. For many applications it is not possible to store the entire data on the main
memory for two reasons, amount of main memory available is smaller than amount of data.
Secondly the main memory is a volatile device and thus will lose the data when the power is
shut down. To overcome these problems the data is stored on the secondary storage devices.
The technique which is used to sort the data which resides on the secondary devices are
called external sorting.
Internal sorting:
Sorting is an important activity and every time we insert or delete the data we need to sort the
remaining data. Therefore it should be carried out efficiently. Various algorithms are
developed for sorting such as
1. Bubble sort
2. Selection sort
3. Insertion sort
4. Merge sort
5. Shell sort
6. Heap sort
Bubble sort
This is the simplest kind of sorting method in this method. We do this bubble sort procedure
in several iterations, which are called passes.
Algorithm:
1. Read the total number of elements says n
2. Store the elements in the array
3. Set i=0
4. Compare the adjacent elements
5. Repeat the step 4 for all n elements.
6. Increment the value of I by 1 and repeat step 4,5 for I<n

3
 7. Print the sorted list of elements.
8. Stop
For example

‘C’ Program
/*Bubble sort. */
#include <stdio.h>
#include <conio.h>
void main( )
{
int n,a[20];
int i, j, temp ;
clrscr( );
printf("enter the limit");
scanf("%d",&n);
printf("enter the array values:");
for(i=0;i<n;i++)

4
 {
scanf("%d",&a[i]);
}
printf ( "Bubble sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;

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

printf ( "%d\t", a[i] ) ;

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

{
for ( j = 0 ; j <n-i-1; j++ )
{
if ( a[j] > a[j + 1] )
{
temp = a[j] ;
a[j] = a[j + 1] ;
a[j + 1] = temp ;
}
}
}

printf ( "\n\nArray after sorting:\n") ;

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

printf ( "%d\t", a[i] ) ;

getch( ) ;
}
Selection sort:

5
selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting
the smallest (or largest) element from the unsorted portion of the list and moving it to the
sorted portion of the list.

The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion
of the list and swaps it with the first element of the unsorted part. This process is repeated for
the remaining unsorted portion until the entire list is sorted.

6
// Selection sort in C

#include <stdio.h>

// function to swap the the position of two elements

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

void selectionSort(int array[], int size) {

for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {

// To sort in descending order, change > to < in this line.

// Select the minimum element in each loop.
if (array[i] < array[min_idx])
min_idx = i;
}

// put min at the correct position

swap(&array[min_idx], &array[step]);
}
}

// function to print an array

void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);

7
 }
printf("\n");
}

// driver code
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("Sorted array in Acsending Order:\n");
printArray(data, size);
}
Insertion sort:
Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing
cards in your hands. The array is virtually split into a sorted and an unsorted part. Values
from the unsorted part are picked and placed in the correct position in the sorted part.

Insertion Sort Algorithm

To sort an array of size N in ascending order iterate over the array and compare the current
element (key) to its predecessor, if the key element is smaller than its predecessor, compare it
to the elements before. Move the greater elements one position up to make space for the
swapped element.
In this method elements are inserted at their appropriate places. Let us see the example.

8
/* C Program to sort an array in ascending order using Insertion Sort */

#include <stdio.h>
int main(void)
{
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]);
}
for (i = 1; i < n; i++)

9
 {
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\n", arr[i]);
}
return 0;
}
Shell sort:
This method is improvement over the simple insertion sort. In this method the elements at
fixed distance are compared. The distance will then be decremented by some fixed amount
and again the comparison will be made. Finally, individual elements will be compared. Let
us take some example.
Example:

0 1 2 3 4 5 6 7
x
25 57 48 37 12 92 86 33

step 1: let us take the distance k = 5

so in the first iteration compare
(x [0] , x[5])
(x[1], x[6])

10
(x[2], x[7])
(x[3])
(x[4])
i.e. first iteration

0 1 2 3 4 5 6 7

x 25 57 48 37 12 92 86 33

After first iteration,

0 1 2 3 4 5 6 7

25 57 33 37 12 92 86 48

Step 2: initially K was 5. take some d and decrement k by d. let us take d=2
k= k-d i.e. k=5-2= 3
so now compare
(x[0],x[3],x[6])
(x[1],x[4],x[7])
(x[2], x[5])
Second iteration

0 1 2 3 4 5 6 7

25 57 48 37 12 92 86 33

11
After second iteration

0 1 2 3 4 5 6 7

25 12 33 37 48 92 86 57
x

step 3: Now k=k-d k=3-2 = 1

so now compare
(x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7])
this sorting is then done by simple insertion sort. Because simple insertion sort is highly
efficient on sorted file. So we get

0 1 2 3 4 5 6 7

12 25 33 37 48 57 86 92

12
// C implementation of Shell Sort
#include <stdio.h>
int main()
{
int i,n,gap,arr[10],temp,j;
printf("\nenter the number of elements");
scanf("%d",&n);
printf("\nenter the array values");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("\n array before sorting");
for(i=0;i<n;i++)
printf("\t%d",arr[i]);
//shell sort begins here
for (gap=n/2;gap>0;gap=gap/2)
{
for (i=gap;i<n;i++)
{
temp = arr[i];
for (j = i;j>=gap&&arr[j - gap]>temp; j=j-gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
printf("\n after sorting");
for (i=0; i<n; i++)

printf("\t%d",arr[i]);
return 0;
}

13
Heap sort
Heap sort is a method in which a binary tree is used. In this method first the heap is created
using binary tree and then heap is sorted using prority queue.
Example for heap sort

Transform into max heap: After that, the task is to construct a tree from that unsorted array
and try to convert it into max heap.

To transform a heap into a max-heap, the parent node should always be greater than or equal
to the child nodes
Here, in this example, as the parent node 4 is smaller than the child node 10, thus, swap them
to build a max-heap.
Now, 4 as a parent is smaller than the child 5, thus swap both of these again and the resulted
heap and array should be like this:

14
Perform heap sort: Remove the maximum element in each step (i.e., move it to the end
position and remove that) and then consider the remaining elements and transform it into a
max heap.

Delete the root element (10) from the max heap. In order to delete this node, try to swap it
with the last node, i.e. (1). After removing the root element, again heapify it to convert it into
max heap.
Resulted heap and array should look like this:

Repeat the above steps and it will look like the following:

15
Now remove the root (i.e. 3) again and perform heapify.

Now when the root is removed once again it is sorted. and the sorted array will be like arr[] =
{1, 3, 4, 5, 10}.

16
// Heap Sort in C
#include <stdio.h>
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

void heapify(int arr[], int n, int i) {

// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

// Swap and continue heapifying if root is not largest

if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}

// Main function to do heap sort

void heapSort(int arr[], int n) {
// Build max heap

17
 for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);

// Heapify root element to get highest element at root again

heapify(arr, i, 0);
}
}

// Print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}

// Driver code
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);

heapSort(arr, n);

printf("Sorted array is \n");

printArray(arr, n);
}

Merge Sort:

18
In this sorting method, we divide the main list into two sub-lists, then go on dividing those
sub-list till we get sufficient length of that sub-list. Then we compare and sort the elements of
each list. Merge the two sub-list and sort the merged the list. This process will be repeated
until we get only one sorted list.
For example

// Merge sort in C

#include <stdio.h>

// Merge two subarrays L and M into arr

void merge(int arr[], int p, int q, int r) {

// Create L ← A[p..q] and M ← A[q+1..r]

int n1 = q - p + 1;
int n2 = r - q;

int L[n1], M[n2];

for (int i = 0; i < n1; i++)

L[i] = arr[p + i];

19
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];

// Maintain current index of sub-arrays and main array

int i, j, k;
i = 0;
j = 0;
k = p;

// Until we reach either end of either L or M, pick larger among

// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}

// When we run out of elements in either L or M,

// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

while (j < n2) {

20
 arr[k] = M[j];
j++;
k++;
}
}

// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {

// m is the point where the array is divided into two subarrays

int m = l + (r - l) / 2;

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

// Merge the sorted subarrays

merge(arr, l, m, r);
}
}

// Print the array

void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Driver program
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};

21
 int size = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, 0, size - 1);

printf("Sorted array: \n");

printArray(arr, size);
}

Time complexity analysis of sorting algorithms:

Sorting Best case Average case Worst case

O(n2) O(n2) O(n2)
Bubble sort
O(n) O(n2) O(n2)
Insertion Sort
O(n) O(n2) O(n2)
Shell Sort
O(n log n) O(n log n) O(n log n)
Heap Sort
O(n log n) O(n log n) O(n log n)
Merge Sort
O(log n) O(log n) O(n2)
Quick Sort

22