Heap Sort
With heap sort, the elements are created using the min-heap and max-heap based on the elements of the given array.
In a min-heap or max-heap, the root element represents the minimum or maximum element of the array.
The heap sort recursively performs two main operations -
- Create a heap H with the elements of the array.
- Delete the root element of the heap formed in the first phase repeatedly.
What is a Heap?
A heap is a complete binary tree, and a binary tree is a tree in which a node can have utmost two children.
Complete binary trees are trees in which all the levels except for the last one, i.e., the leaf node, are completely filled and all the nodes are left-justified.
What is a Heap sort?
Heapsort is an efficient and popular sorting algorithm.
Heap sort involves removing the elements one by one from the heap part of the list.
Then, insert the elements into the sorted portion of the list.
Time Complexity
Case | Time Complexity |
---|---|
Best Case | O(n log n) |
Average Case | O(n log n) |
Worst Case | O(n log n) |
- Best Case O(n log n):It occurs when there is no sorting needed, i.e. the array is already sorted.
- Average Case O(n log n): The array elements are in a jumbled order that is not properly ascending and descending.
- Worst Case O(n log n): This occurs when the array elements need to be sorted in reverse order.
Space Complexity
Space Complexity | O(1) |
Stable | No |
- The space complexity of heap sort is
O (1)
.
Shell Sort
#include <stdio.h>
/* function to heapify a subtree. Here 'i' is the
index of root node in array a[], and 'n' is the size of heap. */
void heapify(int a[], int n, int i) {
// Initialize largest as root
int largest = i;
// left child
int left = 2 * i + 1;
// right child
int right = 2 * i + 2;
// If left child is larger than root
if (left < n && a[left] > a[largest])
largest = left;
// If right child is larger than root
if (right < n && a[right] > a[largest])
largest = right;
// If root is not largest
if (largest != i) {
// swap a[i] with a[largest]
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a, n, largest);
}
}
/*function to implement the heap sort*/
void heap_sort(int a[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
/* Move current root element to end*/
// swap a[0] with a[i]
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a, i, 0);
}
}
/* function to print the array elements */
void print(int arr[], int n) {
for (int i = 0; i < n; ++i) {
printf("%d", arr[i]);
printf(" ");
}
}
int main() {
int a[] = {42, 12, 17, 25, 40, 10, 33, 31};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
print(a, n);
heap_sort(a, n);
printf("\nAfter sorting array elements are - \n");
print(a, n);
return 0;
}
public class HeapSort {
/* function to heapify a subtree. Here 'i' is the
index of root node in array a[], and 'n' is the size of heap. */
static void heapify(int a[], int n, int i) {
// Initialize largest as root
int largest = i;
// left child
int left = 2 * i + 1;
// right child
int right = 2 * i + 2;
// If left child is larger than root
if (left < n && a[left] > a[largest])
largest = left;
// If right child is larger than root
if (right < n && a[right] > a[largest])
largest = right;
// If root is not largest
if (largest != i) {
// swap a[i] with a[largest]
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a, n, largest);
}
}
/*function to implement the heap sort*/
static void heapSort(int a[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
/* Move current root element to end*/
// swap a[0] with a[i]
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a, i, 0);
}
}
/* function to print the array elements */
static void print(int a[], int n) {
for (int i = 0; i < n; ++i)
System.out.print(a[i] + " ");
}
public static void main(String args[]) {
int a[] = {42, 12, 17, 25, 40, 10, 33, 31};
int n = a.length;
System.out.print("Before sorting array elements are - \n");
print(a, n);
heapSort(a, n);
System.out.print("\nAfter sorting array elements are - \n");
print(a, n);
}
}