Heap Sort

Here, We will discuss about Heap Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications.

What is Heap Sort?

Heap Sort is a comparison-based sorting algorithm. This sorting algorithm has more favorable worst-case O(n log n) runtime.

Heap Sort is an in-place algorithm but is not a stable sort.

Heaps can be used in sorting an array. In max-heaps, the maximum element will always be at the root.

Heap Sort uses this property of heap to sort the array.

Heap Sort Algorithm

  1. The tree satisfies Max-Heap property, then the largest element is stored at the root node.
  2. Swap: Remove the root element and put at the end of the array (nth position). Put the last item of the tree(heap) at the vacant place.
  3. Remove: Reduce the size of the heap by 1.
  4. Heapify: Heapify the root element again so that we have the largest element at root.
  5. The process is repeated until all items of the list are sorted.

Implementation of Radix Sort

Program Code in C

#include<stdio.h> //function to swap the position of two elements void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void heapify(int arr[], int n, int i) { //find largest among root, left and right child int largest = i; int left = 2*i+1; int right = 2*i+2; if(left<n && arr[left]>arr[largest]) largest = left; if(right<n && arr[right]>arr[largest]) largest = right; //swap and continue heapifying if root is not largest if(largest != i) { swap(&arr[i], &arr[largest]); heapify(arr, n, largest); } } //main function to do heap sort void heapsort(int arr[], int n) { //build max-heap for(int i=n/2-1; i>=0; i--) heapify(arr, n, i); //heap sort for(int i=n-1; i>=0; i--) { swap(&arr[0], &arr[i]); //heapify root element to get highest element at root again heapify(arr, i, 0); } } //print an array void printarray(int arr[], int n) { for(int i=0; i<n; i++) printf("%d ", arr[i]); printf("\n"); } //Driver code int main() { int data[] = {8, 4, 7, 1, 3, 5}; int n = sizeof(data)/sizeof(data[0]); heapsort(data, n); printf("Sorted array : "); printarray(data, n); }
Code language: C++ (cpp)

Output

Sorted array : 1 3 4 5 7 8
Code language: PHP (php)

Time and Space Complexity of Radix Sort

Time Complexity
Worst CaseO(n log n)
Best CaseO(n log n)
Average CaseO(n log n)
Space Complexity
Worst CaseO(1)

Applications of Radix Sort

Heap Sort is used when

  1. Systems concerned with security and embedded systems such as Linux Kernel.
  2. Want to extract smallest or largest from list of items without sorting the list

Radix Sort

Here, We will discuss about Radix Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is …
Read More

Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Quick Sort? Quick …
Read More

Merge Sort

Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Merge Sort? Merge …
Read More

Sorting Algorithms

Here, We will learn about sorting algorithms, why is sorting necessary, classification and complexity of sorting, types of sort. What is Sorting? Sorting refers to arranging data …
Read More

Counting Sort

Here, We will discuss about Counting Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Counting …
Read More

Bubble Sort

Here, We will learn about bubble sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Bubble Sort? Bubble Sort …
Read More

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to [email protected]. See your articles on the main page and help other coders.

Leave a Comment

Your email address will not be published. Required fields are marked *