Searching and sorting Algorithm in C

Searching is a process of finding a particular record within a huge amount of data.
Data can be arrays,linked list,tress,etc.

There are 2 categories of searching. They are:
1.Sequential searching (linear search)
2.Interval searching (binary search)

Linear searching

• It is a type of sequential searching algorithm.
• Every element within the input array is traversed and compared with the item to be found . If the item matches in search,then it is successfull.
• The best case complexity is O(1) and the worst case complexity is O(n).

Example:

#include<stdio.h> int main() { int item,i,n=6; int a[6]={1,4,2,8,6,9}; printf("Enter the element to be found ",item); scanf("%d",&item); for(i=0;i<n;i++) { if(a[i]==item) { printf("item found at %d position",i+1); break; } } if(a[i]!=item) { printf("not"); } return 0; }

Binary Searching

• It is a searching algorithm used in sorted array by repeatedly dividing the search interval in half.
• It is very efficient.
• We compare the element with middle element of array

             mid=(1st term) +(last term)/2
         if the element is less than the middle element then we search it in part of the list till middle                     otherwise in the right side of the middle element. The searching process will continue until we               find the element has no left or right part to search.

• Conditions : Element must be present in sorted list.
• Algorithm

       4 6 9 10 12 15 16 20 25

       Mid = [ 1 + 9 ]/2 = 8.5 =8

      case1: equal to mid
      case2: greater than mid => move right side of mid
      case3: smaller than mid => move left side of mid

• Example

#include <stdio.h> int binarySearch(int a[], int beg, int end, int item) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == item) { return mid+1; } else if(a[mid] < item) { return binarySearch(a, mid+1, end, item); } else { return binarySearch(a, beg, mid-1, item); } } return -1; } int main() { int a[] = {11, 14, 25, 31, 40, 42, 52, 56, 80}; int item = 40; // value to be searched int n =sizeof(a) / sizeof(a[0]); int res = binarySearch(a, 0, n-1, item); printf("The elements of the array are - "); for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\nElement to be searched is - %d", item); if (res == -1) printf("\nElement is not present in the array"); else printf("\nElement is present at %d position of array", res); return 0; }

Selection sort

• In selection sort the smallest value among the unsorted element of the array is selected in every pass and inserted to its appropriate position into the array.

• In this algorithm the array is divided into 2 parts , 1st sorted part and another one is unsorted part. Initially sorted part is empty and another one is unsorted part which is the given array. Sorted part is placed at left while the unsorted part is placed at right.
• Example:

#include <stdio.h> int selection(int a[], int n) { int i, j, min; for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray { min = i; //minimum element in unsorted array for (j = i+1; j < n; j++) if (a[j] < a[min]) min = j; // Swap the minimum element with the first element int temp = a[min]; a[min] = a[i]; a[i] = temp; } } int printArr(int a[], int n) /* function to print the array */ { int i; for (i = 0; i < n; i++) printf("%d ", a[i]); } int main() { int a[] = { 12, 31, 25, 8, 32, 17 }; int n = sizeof(a) / sizeof(a[0]); printf("Before sorting array elements are - \n"); printArr(a, n); selection(a, n); printf("\nAfter sorting array elements are - \n"); printArr(a, n); return 0; }

Bubble sort

• It is also known as exchange sort. Simplest sorting method.
• If the array contains N elements then N-1 iterations or passes are required to sort the array.
• In  each pass two adjacent no. are compared , if they are out of order then swap those no.
• At the end of 1st iteration the highest value is placed at last position.
• At the end of 2nd pass, next highest no. is placed at 2nd last position and so on. 
• It is very efficient sorting algorithm.
• Example
• 
  

#include<stdio.h> int print(int a[], int n) //function to print array elements { int i; for(i = 0; i < n; i++) { printf("%d ",a[i]); } } int bubble(int a[], int n) // function to implement bubble sort { int i, j, temp; for(i = 0; i < n; i++) { for(j = i+1; j < n; j++) { if(a[j] < a[i]) { temp = a[i]; a[i] = a[j]; a[j] = temp; } } } } int main () { int i, j,temp; int a[5] = { 10, 35, 31, 5, 40}; int n = sizeof(a)/sizeof(a[0]); printf("Before sorting array elements are - \n"); print(a, n); bubble(a, n); printf("\nAfter sorting array elements are - \n"); print(a, n); }

Insertion sort

• This algorithm is similar to game of cards. It is assumed that the first card is already sorted in the game and then we select an unsorted card. If the selected unsorted card is greater than 1st card, it will be placed at the right side , otherwise to the left side . Similarly all unsorted card are put in perfect place.
• Example

#include <stdio.h> int insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i < n; i++) { temp = a[i]; j = i - 1; while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position ahead from their current position*/ { a[j+1] = a[j]; j = j-1; } a[j+1] = temp; } } int printArr(int a[], int n) /* function to print the array */ { int i; for (i = 0; i < n; i++) printf("%d ", a[i]); } int main() { int a[] = { 12, 30, 21, 8, 32, 17 }; int n = sizeof(a) / sizeof(a[0]); printf("Before sorting array elements are - \n"); printArr(a, n); insert(a, n); printf("\nAfter sorting array elements are - \n"); printArr(a, n); return 0; }

Quick sort

• One of the best sorting algorithm which follows divide and conquer rule.
• The basic idea behind Quicksort is to select a pivot element from the array and partition the other dements into 2 sub arrays according to whether they are of greater than or less than pivot.
• This algorithm basically requires implementation of 2 function
• Partition () function and Quick sort () function
• Example

#include <stdio.h> int partition (int a[], int start, int end) { int pivot = a[end]; int i = (start - 1); for (int j = start; j <= end - 1; j++) { if (a[j] < pivot) { i++; int t = a[i]; a[i] = a[j]; a[j] = t; } } int t = a[i+1]; a[i+1] = a[end]; a[end] = t; return (i + 1); } int quick(int a[], int start, int end) { if (start < end) { int p = partition(a, start, end); quick(a, start, p - 1); quick(a, p + 1, end); } } int printArr(int a[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", a[i]); } int main() { int a[] = { 20, 9, 39, 44, 19, 27 }; int n = sizeof(a) / sizeof(a[0]); printf("Before sorting array elements are - \n"); printArr(a, n); quick(a, 0, n - 1); printf("\nAfter sorting array elements are - \n"); printArr(a, n); return 0; }

Merge sort

• Merge sort is the most popular sorting algorithm that is based on principle of divide and conquer algorithm.
• A problem here is divided into multiple sub problems. Each problems is solved individually. Finally , sub problems are combined to form the final solution.
• The sub lists are divided again into halves until the list cannot be further divided.
• Example

#include <stdio.h> int merge(int a[], int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; int LeftArray[n1], RightArray[n2]; for (int i = 0; i < n1; i++) LeftArray[i] = a[beg + i]; for (int j = 0; j < n2; j++) RightArray[j] = a[mid + 1 + j]; i = 0; j = 0; k = beg; while (i < n1 && j < n2) { if(LeftArray[i] <= RightArray[j]) { a[k] = LeftArray[i]; i++; } else { a[k] = RightArray[j]; j++; } k++; } while (i<n1) { a[k] = LeftArray[i]; i++; k++; } while (j<n2) { a[k] = RightArray[j]; j++; k++; } } int mergeSort(int a[], int beg, int end) { if (beg < end) { int mid = (beg + end) / 2; mergeSort(a, beg, mid); mergeSort(a, mid + 1, end); merge(a, beg, mid, end); } } int printArray(int a[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); } int main() { int a[] = { 12, 22, 26, 9, 32, 18, 40, 45 }; int n = sizeof(a) / sizeof(a[0]); printf("Before sorting array elements are - \n"); printArray(a, n); mergeSort(a, 0, n - 1); printf("After sorting array elements are - \n"); printArray(a, n); return 0; }

Questions 

1.  List out any 3 differences between structure and Unions?

Structures:

•  In structures, each member has its own memory location.
•  The size of a structure is the sum of the sizes of its members plus any padding.
• Structures are used to represent a collection of different data types. 

Unions:

• In unions, all members share the same memory location.
• The size of a union is the size of its largest member. 
• Unions are used when different data types need to be stored in the same memory location, and only one value needs to be accessed at a time. 

2.