Data Structure Using ‘c’

Unit-2 Searching & Sorting

Linear Search
Linear search is to check each element one by one in sequence.
Linear search is the most basic search algorithm in the data structure. It is
used to search any element in a linear data structure like arrays and linked
lists. Linear Search algorithm compares the search element to each element of
the Data Structure and returns the location of the element if found.

Method to use Linear Search

1. Start from the first element and compare each element with the search
element.
2. If the element is found, return at which position element was found.
3. If the element is not found, return -1.

Algorithm for Linear Search

Steps for Linear search are as follows:

Linear_Search ( Array A [ n ], search_element x)

1: Set i to 1
2: if i > n then go to step 7
3: if A[i] = x then go to step 6
4: assign i+1 to i
5: Go to Step 2
6: Print Element x Found at index i and exit
7: display “element not found”

Implementation of Linear Search using String

in C
# include<stdio.h>
# include<conio.h>
void main()
{
char Listt[100][100];
char Search[100];

1
Data Structure Using ‘c’

int i,f=0;
int op;
clrscr();
printf("\nHow Many Strings We Enter : \n");
scanf("%d",&op);
for(i=0;i<op;i++)
{
scanf("%s",Listt[i]);
}
printf("\nEnter String Which we Find : \n");
scanf("%s",Search);
for(i=0;i<op;i++)
{
if(strcmp(Search,Listt[i]) == 0)
{
f = 1;
printf("\nString Found At %d Row \n",i+1);

2
 Data Structure Using ‘c’

}
}
if(f==0)
{
printf("\nString Not Available in given list \n");
}
getch();

Time Complexity of Linear Search

Complexity Best Case Average Case Worst Case
Time Complexity O(1) O(n) O(n)
Space complexity O(1)

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

In this approach, the element is always searched in the middle of a portion of

an 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.

Binary Search Working

Binary Search Algorithm can be implemented in two ways which are

discussed below.

1. Iterative Method

3
 Data Structure Using ‘c’

2. Recursive Method

The recursive method follows the divide and conquer approach.

The general steps for both methods are discussed below.

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

Initial array
Let x = 4 be the element to be searched.
2. Set two pointers low and high at the lowest and the highest position
respectively

Find the
3. middle element mid of the array ie. arr[(low + high)/2] = 6 .

Mid element

3. If x == mid, then return mid.Else, compare the element to be searched with m.

4. If x > mid , compare x with the middle element of the elements on the right side
of mid . This is done by setting low to low = mid + 1 .

5. Else, compare x with the middle element of the elements on the left side
of mid . This is done by setting high to high = mid - 1 .

4
 Data Structure Using ‘c’

Finding mid element

Repeat steps 3 to 6 until low meets high. Mid element

6. . X=4 is Found

/ Binary Search in C

#include <stdio.h>

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

// Repeat until the pointers low and high meet each other
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;
}

int main(void)
{

5
Data Structure Using ‘c’

int array[] = {3, 4, 5, 6, 7, 8, 9};

int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
return 0;
}

Bubble Sort Algorithm

Bubble sort is a simple sorting algorithm. This sorting algorithm is

comparison-based algorithm in which each pair of adjacent elements is

6
Data Structure Using ‘c’

compared and the elements are swapped if they are not in order. 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.
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.

7
Data Structure Using ‘c’

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.

Now we should look into some practical aspects of bubble sort.

Bubble sort Programme…

# include<stdio.h>
# include<conio.h>
void main()
{
int Size,i,j,Temp;
int Array[100];
clrscr();
printf("\nEnter Size of an Array : \n");
scanf("%d",&Size);
printf("\nEnter %d Elements in Array : \n",Size);
for(i=0;i<Size;i++)
{
scanf("%d",&Array[i]);
8
Data Structure Using ‘c’

}
printf("\n\nGiven Elements Are : \n\n");
for(i=0;i<Size;i++)
{
printf("%d\t",Array[i]);
}
printf("\n\nBubble Sorted List is : \n\n");
for(i=0;i<Size;i++)
{
for(j=i+1;j<Size;j++)
{
if(Array[i]>Array[j])
{

9
Data Structure Using ‘c’

Temp = Array[i];
Array[i]=Array[j];
Array[j]=Temp;
}
}
}
for(i=0;i<Size;i++)
{
printf("%d\t",Array[i]);
}
getch();
}

Selection Sort Algorithm

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.

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.

10
Data Structure Using ‘c’

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 −

11
Data Structure Using ‘c’

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

12
Data Structure Using ‘c’

#include <stdio.h>
int main() {
int arr[10]={6,12,0,18,11,99,55,45,34,2};
int n=10;
int i, j, position, swap;
for (i = 0; i < (n - 1); i++)
{
position = i;
for (j = i + 1; j < n; j++) {
if (arr[position] > arr[j])
position = j;
}
if (position != i)
{
swap = arr[i];
arr[i] = arr[position];
arr[position] = swap;
}
}
for (i = 0; i < n; i++)
printf("%d\t", arr[i]);
return 0;
}

Insertion Sort
The idea behind the insertion sort is that first take one element, iterate it through
the sorted array. Although it is simple to use it is not appropriate for large data sets
as the time complexity of insertion sort in the average case and worst case is O(n2),

13
Data Structure Using ‘c’

where n is the number of items. Insertion sort is less efficient than the other sorting
algorithms like heap sort, quick sort, merge sort, etc.

Insertion sort has various advantages such as -

o Simple implementation
o Efficient for small data sets
o Adaptive, i.e., it is appropriate for data sets that are already substantially sorted

Algorithm
The simple steps of achieving the insertion sort are listed as follows -

Step 1 - If the element is the first element, assume that it is already sorted. Return 1.

tep2 - 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.

Working of Insertion sort Algorithm

Let the elements of array are -

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending order.
So, for now, 12 is stored in a sorted sub-array.

14
Data Structure Using ‘c’

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25.
Along with swapping, insertion sort will also check it with all elements in the sorted
array.

For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12. Hence,
the sorted array remains sorted after swapping.
freestar

Now, two elements in the sorted array are 12 and 25. Move forward to the next
elements that are 31 and 8.

Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted.

So, swap them.

15
Data Structure Using ‘c’

Now, elements 12 and 8 are unsorted.

So, swap them too.

Now, the sorted array has three items that are 8, 12 and 25. Move to the next items that
are 31 and 32.

Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.

Move to the next elements that are 32 and 17.

17 is smaller than 32. So, swap them.

Swapping makes 31 and 17 unsorted. So, swap them too.

16
Data Structure Using ‘c’

Now, swapping makes 25 and 17 unsorted. So, perform swapping again.

Now, the array is completely sorted.

Program Insertion Sort

1. #include <stdio.h>
2. int main(void)
3. {
4. int n, i, j, temp;
5. int arr[64];
6. printf("Enter number of elements\n");
7. scanf("%d", &n);
8. printf("Enter %d integers\n", n);
9. for (i = 0; i < n; i++)
10. {
11. scanf("%d", &arr[i]);
12. }
13. for (i = 1; i < n; i++)
14. {
15. j = i;
16. while (j > 0 && arr[j - 1] > arr[j])
17. {
18. temp = arr[j];
19. arr[j] = arr[j - 1];
20. arr[j - 1] = temp;
21. j--;
22. }
23. }
24. printf("Sorted list in ascending
order:\n");
25. for (i = 0; i < n; i++)

17
Data Structure Using ‘c’

26. {
27. printf("%d\n", arr[i]);
28. }
29. return 0;
30. }

Quick Sort Algorithm

Sorting is a way of arranging items in a systematic manner. Quicksort is the widely used
sorting algorithm that makes n log n comparisons in average case for sorting an array
of n elements. It is a faster and highly efficient sorting algorithm.

This algorithm follows the divide and conquer approach.

Divide and conquer is a technique of breaking down the algorithms into subproblems,
then solving the subproblems, and combining the results back together to solve the
original problem.

Divide: In Divide, first pick a pivot element. After that, partition or rearrange the array
into two sub-arrays such that each element in the left sub-array is less than or equal to
the pivot element and each element in the right sub-array is larger than the pivot
element.

Conquer: Recursively, sort two subarrays with Quicksort.

Combine: Combine the already sorted array.

Quicksort picks an element as pivot, and then it partitions the given array around the
picked pivot element. In quick sort, a large array is divided into two arrays in which one
holds values that are smaller than the specified value (Pivot), and another array holds
the values that are greater than the pivot.

After that, left and right sub-arrays are also partitioned using the same approach. It will
continue until the single element remains in the sub-array.

18
 Data Structure Using ‘c’

Choosing the pivot

Picking a good pivot is necessary for the fast implementation of quicksort. However, it is
typical to determine a good pivot. Some of the ways of choosing a pivot are as follows -

o Pivot can be random, i.e. select the random pivot from the given array.
o Pivot can either be the rightmost element of the leftmost element of the given array.
o Select median as the pivot element.

Algorithm
1. QUICKSORT (array A, start, end)
2. {
3. 1 if (start < end)
4. 2{
5. 3 p = partition(A, start, end)
6. 4 QUICKSORT (A, start, p - 1)
7. 5 QUICKSORT (A, p + 1, end)
8. 6 }
9. }

Let the elements of array are -

19
Data Structure Using ‘c’

In the given array, we consider the leftmost element as pivot. So, in this case, a[left] =
24, a[right] = 27 and a[pivot] = 24.

Since, pivot is at left, so algorithm starts from right and move towards left.

Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. -

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot
moves to right, as -

20
Data Structure Using ‘c’

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so algorithm
starts from left and moves to right.

As a[pivot] > a[left], so algorithm moves one position to right as -

Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm
moves one position to right as -

21
Data Structure Using ‘c’

Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap a[pivot]
and a[left], now pivot is at left, i.e. -

Since, pivot is at left, so algorithm starts from right, and move to left. Now, a[left] = 24,
a[right] = 29, and a[pivot] = 24. As a[pivot] < a[right], so algorithm moves one position
to left, as -

22
Data Structure Using ‘c’

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap a[pivot]
and a[right], now pivot is at right, i.e. -

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the algorithm starts
from left and move to right.

Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are pointing
the same element. It represents the termination of procedure.

Element 24, which is the pivot element is placed at its exact position.

Elements that are right side of element 24 are greater than it, and the elements that are
left side of element 24 are smaller than it.

23
Data Structure Using ‘c’

Now, in a similar manner, quick sort algorithm is separately applied to the left and right
sub-arrays. After sorting gets done, the array will be -

Quicksort complexity
Now, let's see the time complexity of quicksort in best case, average case, and in worst
case. We will also see the space complexity of quicksort.

1. Time Complexity

Case Time Complexity

Best Case O(n*logn)

Average Case O(n*logn)

Worst Case O(n2)

Advantages of quick sort

1. Fast and efficient
2. Cache friendly
3. Time complexity
4. Space complexity

24
Data Structure Using ‘c’

Disadvantages of quick sort

1. Unstable
2. Worst-case time complexity

Merge Sort:-
• Merge sort is similar to the quick sort algorithm as it uses the divide and conquer
approach to sort the elements.
• It is one of the most popular and efficient sorting algorithm. It divides the given
list into two equal halves, calls itself for the two halves and then merges the two
sorted halves.
• We have to define the merge() function to perform the merging.
• The sub-lists are divided again and again into halves until the list cannot be
divided further. Then we combine the pair of one element lists into two-element
lists, sorting them in the process.
• The sorted two-element pairs is merged into the four-element lists, and so on
until we get the sorted list.

Merge Sort
The Merge Sort algorithm is a divide-and-conquer algorithm that sorts an array
by first breaking it down into smaller arrays, and then building the array back
together the correct way so that it is sorted.

Divide: The algorithm starts with breaking up the array into smaller and
smaller pieces until one such sub-array only consists of one element.

Conquer: The algorithm merges the small pieces of the array back together by
putting the lowest values first, resulting in a sorted array.

The breaking down and building up of the array to sort the array is done
recursively.

In the animation above, each time the bars are pushed down represents a
recursive call, splitting the array into smaller pieces. When the bars are lifted
up, it means that two sub-arrays have been merged together.

25
 Data Structure Using ‘c’

The Merge Sort algorithm can be described like this:

How it works:

1. Divide the unsorted array into two sub-arrays, half the size of the original.
2. Continue to divide the sub-arrays as long as the current piece of the array has
more than one element.
3. Merge two sub-arrays together by always putting the lowest value first.
4. Keep merging until there are no sub-arrays left.

Manual Run Through

26
Data Structure Using ‘c’

Let's try to do the sorting manually, just to get an even better understanding of
how Merge Sort works before actually implementing it in a programming
language.

Step 1: We start with an unsorted array, and we know that it splits in half until
the sub-arrays only consist of one element. The Merge Sort function calls itself
two times, once for each half of the array. That means that the first sub-array
will split into the smallest pieces first.

[ 12, 8, 9, 3, 11, 5, 4]
[ 12, 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8] [ 9] [ 3, 11, 5, 4]

Step 2: The splitting of the first sub-array is finished, and now it is time to
merge. 8 and 9 are the first two elements to be merged. 8 is the lowest value,
so that comes before 9 in the first merged sub-array.

[ 12] [ 8, 9] [ 3, 11, 5, 4]

Step 3: The next sub-arrays to be merged is [ 12] and [ 8, 9]. Values in both
arrays are compared from the start. 8 is lower than 12, so 8 comes first, and 9
is also lower than 12.

[ 8, 9, 12] [ 3, 11, 5, 4]

Step 4: Now the second big sub-array is split recursively.

[ 8, 9, 12] [ 3, 11, 5, 4]
[ 8, 9, 12] [ 3, 11] [ 5, 4]
[ 8, 9, 12] [ 3] [ 11] [ 5, 4]

Step 5: 3 and 11 are merged back together in the same order as they are
shown because 3 is lower than 11.

[ 8, 9, 12] [ 3, 11] [ 5, 4]

27
Data Structure Using ‘c’

Step 6: Sub-array with values 5 and 4 is split, then merged so that 4 comes
before 5.

[ 8, 9, 12] [ 3, 11] [ 5] [ 4]
[ 8, 9, 12] [ 3, 11] [ 4, 5]

Step 7: The two sub-arrays on the right are merged. Comparisons are done to
create elements in the new merged array:

1. 3 is lower than 4
2. 4 is lower than 11
3. 5 is lower than 11
4. 11 is the last remaining value

[ 8, 9, 12] [ 3, 4, 5, 11]

Step 8: The two last remaining sub-arrays are merged. Let's look at how the
comparisons are done in more detail to create the new merged and finished
sorted array:

3 is lower than 8:

Before [ 8, 9, 12] [ 3, 4, 5, 11]

After: [ 3, 8, 9, 12] [ 4, 5, 11]

Step 9: 4 is lower than 8:

Before [ 3, 8, 9, 12] [ 4, 5, 11]

After: [ 3, 4, 8, 9, 12] [ 5, 11]

Step 10: 5 is lower than 8:

Before [ 3, 4, 8, 9, 12] [ 5, 11]

After: [ 3, 4, 5, 8, 9, 12] [ 11]

28
Data Structure Using ‘c’

Step 11: 8 and 9 are lower than 11:

Before [ 3, 4, 5, 8, 9, 12] [ 11]

After: [ 3, 4, 5, 8, 9, 12] [ 11]

Step 12: 11 is lower than 12:

Before [ 3, 4, 5, 8, 9, 12] [ 11]

After: [ 3, 4, 5, 8, 9, 11, 12]

The sorting is finished!

Algorithm of Merge Sort

Step 1: Start
Step 2: Declare an array and left, right, mid variable
Step 3: Perform merge function.
mergesort(array,left,right)
mergesort (array, left, right)
if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
Step 4: Stop

Advantages :-
1. It has a timing complexity O(n log n)
2. It can be used both internal as well as External sorting,
3. It is stable sorting algorithm.

Disadvantages:-
1. It require additional memory for sorting of merged data.

29
Data Structure Using ‘c’

2. It can take advantages of partially sorted nature of data number of

passes are fixed.

30