Heap Sort
Heap sort is a comparison-based sorting technique. It works on the data
structure known as “the binary heap”. It is one of the most efficient sorting
algorithms. It takes relatively less time than selection sort, bubble sort,
and insertion sort. Heap sort is an unstable sorting algorithm since the
position of a similar element gets changed. Heap sort works with Max
Heap (Heap is a complete binary tree. A max heap has a parent node
greater than the child nodes).
In this article, we going to deep dive into the sorting algorithm and working
of heap sort. We are also going to implement heap sort in C language.
Heap Sort Algorithm
Step 1 : Create a MaxHeap function. This function will change the given
array data to the max heap.
Step 2 : Swap the root node(the largest element) with the last element.
Then heapify the root node of the current tree to maintain the property of
Max Heap.
Step 3 : Repeat Step 2 until the max heap becomes empty. Place the
element in the correct position.
Step 4 : Repeat Step 2 and Step 3 until every element of the array is the
correct sport.
Step 5 : End
Heapify Method (Algorithm)
Step 1 : Compare the value at the current node(index i) with its left child
(indexed at 2*i + 1) and its right child (indexed at 2*i + 2), if they exist.
Step 2 : Find the largest of current node, left child and right child.
Step 3 : Swap the largest of all with the current node( if needed).
Step 4 : If a swap was done, make sure the subtree that was rooted at the
index where the highest value was found also meets the max-heap
property by recursively applying the heapify() to it.
Example of the Heap Sort
Step 1: Array Input Taken and then inserting the elements in a Binary Tree.
Step 2: Using Max Heapify to get the maximum element at the top.
Step 3: Removing the element from the Binary Tree and then adding the
element in result array(Maximum element).
Step 4: Continue the above step to get the second top element. Continue it till
Tree is Empty.
Step 5: After Removing all the elements we get the sorted Array created
using the removed elements.
Program For Heap Sort
#include <stdio.h>
void heapify(int arr[], int n, int i)
{
int temp, maximum, left_index, right_index;
maximum = i;
right_index = 2 * i + 2;
left_index = 2 * i + 1;
if (left_index < n && arr[left_index] > arr[maximum])
maximum = left_index;
if (right_index < n && arr[right_index] > arr[maximum])
maximum = right_index;
if (maximum != i) {
temp = arr[i];
arr[i] = arr[maximum];
arr[maximum] = temp;
heapify(arr, n, maximum);
}
}
void heapsort(int arr[], int n)
{
int i, temp;
for (i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// the current array is changed to max heap
for (i = n - 1; i > 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main()
{
int arr[] = { 20, 18, 5, 15, 3, 2 };
int n = 6;
printf("Original Array : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
heapsort(arr, n);
printf("Array after performing heap sort: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Merge Sort – Data Structure and Algorithms
Merge sort is a sorting algorithm that follows the divide-and-conquer approach. It works by
recursively dividing the input array into smaller subarrays and sorting those subarrays then
merging them back together to obtain the sorted array.
In simple terms, we can say that the process of merge sort is to divide the array into two
halves, sort each half, and then merge the sorted halves back together. This process is
repeated until the entire array is sorted.
How does Merge Sort work?
Merge sort is a popular sorting algorithm known for its efficiency and stability. It
follows the divide-and-conquer approach to sort a given array of elements.
Here’s a step-by-step explanation of how merge sort works:
1. Divide: Divide the list or array recursively into two halves until it can no more be
divided.
2. Conquer: Each subarray is sorted individually using the merge sort algorithm.
3. Merge: The sorted subarrays are merged back together in sorted order. The
process continues until all elements from both subarrays have been merged.
sort the array or list [38, 27, 43, 10] using Merge Sort
#include <stdio.h>
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];
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) {
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};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
printf("Sorted array: \n");
printArray(arr, size);
}
Linear Search Algorithm
The linear search algorithm is defined as a sequential search algorithm that starts
at one end and goes through each element of a list until the desired element is
found; otherwise, the search continues till the end of the dataset. In this article, we
will learn about the basics of the linear search algorithm, its applications,
advantages, disadvantages, and more to provide a deep understanding of linear
search.
What is Linear Search Algorithm?
Linear search is a method for searching for an element in a collection of
elements. In linear search, each element of the collection is visited one by one
in a sequential fashion to find the desired element. Linear search is also known
as sequential search.
Algorithm for Linear Search Algorithm:
The algorithm for linear search can be broken down into the following steps:
Start: Begin at the first element of the collection of elements.
Compare: Compare the current element with the desired element.
Found: If the current element is equal to the desired element, return true or
index to the current element.
Move: Otherwise, move to the next element in the collection.
Repeat: Repeat steps 2-4 until we have reached the end of collection.
Not found: If the end of the collection is reached without finding the desired
element, return that the desired element is not in the array.
How Does Linear Search Algorithm Work?
In Linear Search Algorithm,
Every element is considered as a potential match for the key and checked for
the same.
If any element is found equal to the key, the search is successful and the index
of that element is returned.
If no element is found equal to the key, the search yields “No match found”.
For example: Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key =
30
Step 1: Start from the first element (index 0) and compare key with each element
(arr[i]).
Comparing key with first element arr[0]. SInce not equal, the iterator moves to
the next element as a potential match.
// C code to linearly search x in arr[].
#include <stdio.h>
int search(int arr[], int N, int x)
{
for (int i = 0; i < N; i++)
if (arr[i] == x)
return i;
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
int result = search(arr, N, x);
(result == -1)
? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
Binary Search Algorithm
Binary Search Algorithm is a searching algorithm used in a sorted array
by repeatedly dividing the search interval in half. The idea of binary
search is to use the information that the array is sorted and reduce the
time complexity to O(log N).
What is Binary Search Algorithm?
Binary search is a search algorithm used to find the position of a target value
within a sorted array. It works by repeatedly dividing the search interval in half until
the target value is found or the interval is empty. The search interval is halved by
comparing the target element with the middle value of the search space.
Binary Search Algorithm
Below is the step-by-step algorithm for Binary Search:
Divide the search space into two halves by finding the middle index
“mid”.
Compare the middle element of the search space with the key.
If the key is found at middle element, the process is terminated.
If the key is not found at middle element, choose which half will be
used as the next search space.
o If the key is smaller than the middle element, then
the left side is used for next search.
o If the key is larger than the middle element, then
the right side is used for next search.
This process is continued until the key is found or the total search
space is exhausted.
How does Binary Search Algorithm work?
To understand the working of binary search, consider the following illustration:
Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23.
// C program to implement iterative Binary Search
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half
else
high = mid - 1;
}
// If we reach here, then element was not present
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if(result == -1) printf("Element is not present in array");
else printf("Element is present at index %d",result);
