Chapter 4-Searching and Sorting
Chapter 4-Searching and Sorting
INTRODUCTION:
Sorting in c is the process of arranging the data in ascending order and descending order. There
are several types of sorting in data structures, namely – selection sort, bubble sort, insertion sort,
quick sort, merge sort, etc.
SELECTION SORT:
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 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.
INSERTION SORT:
Insertion Sort is basically the insertion of an element from a random set of numbers, to its
correct position where it should actually be, by shifting the other elements if required.
QUICK SORT:
Quick sort is a commonly used sorting algorithm that is often preferred over other sorting
algorithms due to its efficiency and effectiveness. It proceeds by splitting an array into two parts,
one with elements smaller than a selected pivot element and the other with elements bigger than
the pivot. The algorithm then applies this procedure recursively to each partition until the
complete array is sorted.
QUICK SORT LOGIC:
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.
In the following algorithm, arr is the given array, beg is the starting element, and end is the last
element of the array.
The important part of the merge sort is the MERGE function. This function performs the
merging of two sorted sub-arrays that are A[beg…mid] and A[mid+1…end], to build one sorted
array A[beg…end]. So, the inputs of the MERGE function are A[], beg, mid, and end.
Example Program 4
#include<stdio.h>
int i,j;
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
int Left[n1], Right[n2];
// Copy data to temporary arrays
for (i = 0; i < n1; i++) {
Left[i] = arr[left + i];
}
for (j = 0; j < n2; j++) {
Right[j] = arr[mid + 1 + j];
}
// Merge the temporary arrays back into arr[left..right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (Left[i] <= Right[j]) {
arr[k] = Left[i];
i++;
} else {
arr[k] = Right[j];
j++;
}
k++;
}
// Copy the remaining elements of Left[]
while (i < n1) {
arr[k] = Left[i];
i++;
k++;
}
// Copy the remaining elements of Right[]
while (j < n2) {
arr[k] = Right[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left+right) / 2;
// Divide first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the divided halves by sorting
merge(arr, left, mid, right);
}
}
void main() {
int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
SEARCHING:
Searching is the process of finding a particular element in a list.
LINEAR SEARCH:
Linear search is a sequential searching algorithm where we start from one end and check every element
of the list until the desired element is found. It is the simplest searching algorithm.
If we reach the end of the list without finding the element equal to the key, return some
value to represent that the element is not found.
Example Program 6
BINARY SEARCH:
Binary Search is a searching algorithm used only on sorted arrays. This algorithm follows the
divide and conquers approach, where the complete array is divided into two halves and the
element to be searched is compared with the middle element of the list. If the element to be
searched is less than the middle element, then the search is narrowed down to 1st half of the
array. Else, the search continues to the second half of the list.
BINARY SEARCH LOGIC:
BINARY SEARCH ALGORITHM:
Example Program 7
TIME COMPLEXITY AND SPACE COMPLEXITY:
TIMECOMPLEXITY: Time complexity is defined as the amount of time required to execute
an algorithm.
SPACE COMPLEXITY: Space complexity refers to the total amount of memory space used by
an algorithm.
===============================END==================================