[go: up one dir, main page]

0% found this document useful (0 votes)
114 views20 pages

Chapter 4-Searching and Sorting

Uploaded by

bokadarisuck
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
114 views20 pages

Chapter 4-Searching and Sorting

Uploaded by

bokadarisuck
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 20

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.

SELECTION SORT LOGIC:


ALGORITHM OF SELECTION SORT:

Step 1 − Set MIN to location 0


Step 2 − Search the minimum element in the list
Step 3 − Swap minimum element with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 – Repeat Step 2, 3, 4 until list is sorted
Example Program 1:
BUBBLE SORT:
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent
elements if they are in the wrong order.
BUBBLE SORT LOGIC:
Example Program 2
ALGORITHM OF BUBBLE SORT:
The algorithm to sort data of the list in increasing order using bubble sort in C is:
 Run two loops nested in one another.
 The outer loop will run from i = 0 to i < n – 1, where n is the number of elements in the list.
 The inner loop will run from j = 0 to j < n – i – 1. It is because, after each iteration of
the outer loop, one element at the end (or at the start if the order is decreasing order)
will be in its right place so we can leave it as it is.
 In the inner loop, we will check if the arr[ j ] > arr[ j + 1 ].
 If it’s true, then we will swap places of these elements.
 If false, we will continue to the next iteration.
 This process will be repeated till the conditions of the loop are satisfied.

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.

ALGORITHM OF INSERTION SORT:


To sort an array of size N in ascending order:

 Iterate from arr[1] to arr[N] over the array.


 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.
INSERTION SORT LOGIC:
Example Program 3

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:

ALGORITHM OF QUICK SORT:


Example Program 4
#include <stdio.h>
int i,j;
// Partition function for Quick Sort
int partition(int arr[], int low, int high)
{ int pivot = arr[high];
int i = (low - 1);
for ( j = low; j < high; j++)
{ //If current element is smaller than the pivot
if (arr[j] <= pivot)
{ i++;
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
int temp2=arr[i+1];
arr[i+1]=arr[high];
arr[high]=temp2;
return (i + 1);
}
// Recursive Quick Sort implementation
void quickSort(int arr[], int low, int high)
{ if (low < high)
{ // pi is partitioning index
int pi = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, pi - 1);//left
quickSort(arr, pi + 1, high);//right
}
}
void main()
{ int arr[] = {8,2,7,1,6,5};
int n = sizeof(arr) / sizeof(int);
printf("Original array: ");
for ( i = 0; i < n; i++)
{ printf("%d ", arr[i]);
}
quickSort(arr2, 0, n - 1);
printf("Sorted array (Quick Sort): ");
for ( i = 0; i < n; i++)
{ printf("%d ", arr2[i]);
}
}

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.

MERGE SORT LOGIC:


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

ALGORITHM OF MERGE SORT:

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.

LINEAR SEARCH LOGIC:

LINEAR SEARCH ALGORITHM:


Let key be the element we are searching for.
 Check each element in the list by comparing it to the key.

 If any element is equal to the key, return its index.

 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==================================

You might also like