Aim:

Solution :

C program that implements Heap sort sorting methods to sort a given list of integers in ascending order

#include <stdio.h>

// Function to swap two elements
void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

/* heapify the subtree with root i */
void heapify(int* arr, int n, int i)
{
    // store largest as the root element
    int largest = i;
    int left = 2 * i + 1;
    int right  = 2 * i + 2;
    // now check whether the right and left right is larger than the root or not
    if (left < n && arr[left] > arr[largest])
    {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest])
    {
        largest = right;
    }
    // if the root is smaller than the children then swap it with the largest children's value
    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);
        // again heapify that side of the heap where the root has gone
        heapify(arr, n, largest);
    }
}

/* sorts the given array of n size */
void heapsort(int* arr, int n)
{
    // build the binary max heap
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        heapify(arr, n, i);
    }
    // sort the max heap
    for (int i = n - 1; i >= 0; i--)
    {
        // swap the root node and the last leaf node
        swap(&arr[i], &arr[0]);
        // again heapify the max heap from the root 
        heapify(arr, i, 0);
    }
}

int main()
{
    int i, count, number[25];
    printf("How many elements are u going to enter?: ");
    scanf("%d",&count);
    for(i=0;i<count;i++)
    {
        printf("\nEnter %d element: ", i+1);
        scanf("%d",&number[i]);
    }
    heapsort(number,count);
    printf("Order of Sorted elements: ");
    for(i=0;i<count;i++)
    printf(" %d",number[i]);
    return 0;
}

How many elements are u going to enter?: 10
Enter 1 element: 2
Enter 2 element: 5
Enter 3 element: 8
Enter 4 element: 10
Enter 5 element: 3
Enter 6 element: 1
Enter 7 element: 4
Enter 8 element: 6
Enter 9 element: 7
Enter 10 element: 9
Order of Sorted elements:  1 2 3 4 5 6 7 8 9 10

Related Content :

Data Structures Lab Programs

1) Write a program that uses functions to perform the following operations on singly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

2) Write a program that uses functions to perform the following operations on doubly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

3) Write a program that uses functions to perform the following operations on circular linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

4) Write a program that implement Stack (its operations) using Array View Solution

5) Write a program that implement Stack (its operations) using Linked List (Pointer) View Solution

6) Write a program that implement Queue(its operations) using Array View Solution

7) Write a program that implement Queue (its operations) using Linked List (Pointer) View Solution

8) Write a program that implements Quick sort sorting methods to sort a given list of integers in ascending order View Solution

9) Write a program that implements Merge sort sorting methods to sort a given list of integers in ascending order View Solution

10) Write a program that implements Heap sort sorting methods to sort a given list of integers in ascending order View Solution

11) Write a program to implement the tree traversal methods using Recursive View Solution

12) Write a program to implement the tree traversal methods using Non Recursive View Solution

13) Write a program to implement Binary Search Tree (its operations) View Solution

14) Write a program to implement AVL Tree (its operations) View Solution

15) Write a program to implement Red - Black Tree (its operations) View Solution

16) Write a program to implement B Trees (its operations) View Solution

17) Write a program to implement B+ Trees (its operations) View Solution

18) Write a program to implement the graph traversal methods (Breadth First Search) View Solution

19) Write a program to implement the graph traversal methods (Depth First Search) View Solution

20) Write a program to Implement a Pattern matching algorithms using Boyer- Moore View Solution

21) Write a program to Implement a Pattern matching algorithms using Knuth-Morris-Pratt View Solution