Question

WRITE USING C++ CODE, TOPIC :Analysis of Algorithms Computer Science. PLEASE DONT FORGET RUNNING TIME

In this lab, you will implement Heap Sort algorithm for the same inputs.

For each algorithm, and for each n = 100, 200, 300, 400, 500, 1000, 4000, 10000, measure its running time and number of steps when the input is (1) already sort, i.e. n, n-1, …, 3, 2,1; (2) reversely sorted 1, 2, 3, … n; (3) random permutation of 1, 2, …, n; (4) 50 instances of n random numbers generated in the range of [1..n].

Note:

(1) You may have to repeat the algorithm many times, each time you need to initialize the array.

(2) Your running time should exclude the time for initialization.

(3) All measurement should be done in a single run, i.e. you do not need to run once for n=100, another time for n=200, etc

Answer 1

#include <iostream>
 
using namespace std;
 
// A function to heapify the array.
void MaxHeapify(int a[], int i, int n)
{
        int j, temp;
        temp = a[i];
        j = 2*i;
 
        while (j <= n)
        {
                if (j < n && a[j+1] > a[j])
                j = j+1;
                // Break if parent value is already greater than child value.
                if (temp > a[j])
                        break;
                // Switching value with the parent node if temp < a[j].
                else if (temp <= a[j])
                {
                        a[j/2] = a[j];
                        j = 2*j;
                }
        }
        a[j/2] = temp;
        return;
}
void HeapSort(int a[], int n)
{
        int i, temp;
        for (i = n; i >= 2; i--)
        {
                // Storing maximum value at the end.
                temp = a[i];
                a[i] = a[1];
                a[1] = temp;
                // Building max heap of remaining element.
                MaxHeapify(a, 1, i - 1);
        }
}
void Build_MaxHeap(int a[], int n)
{
        int i;
        for(i = n/2; i >= 1; i--)
                MaxHeapify(a, i, n);
}
int main()
{
        int n, i;
        cout<<"\nEnter the number of data element to be sorted: ";
        cin>>n;
        n++;
        int arr[n];
        for(i = 1; i < n; i++)
        {
                cout<<"Enter element "<<i<<": ";
                cin>>arr[i];
        }
        // Building max heap.
        Build_MaxHeap(arr, n-1);
        HeapSort(arr, n-1);
 
        // Printing the sorted data.
        cout<<"\nSorted Data ";
 
        for (i = 1; i < n; i++)
                cout<<"->"<<arr[i];
 
        return 0;
}

Output

Case 1:
 
Enter the number of data element to be sorted: 10
Enter element 1: 9
Enter element 2: 6
Enter element 3: 4
Enter element 4: 3
Enter element 5: 8
Enter element 6: 7
Enter element 7: 5
Enter element 8: 2
Enter element 9: 0
Enter element 10: 1
 
Sorted Data ->0->1->2->3->4->5->6->7->8->9

Code 2

// C++ program for implementation of Heap Sort 
#include <iostream> 
using namespace std; 

// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
        int largest = i; // Initialize largest as root 
        int l = 2 * i + 1; // left = 2*i + 1 
        int r = 2 * i + 2; // right = 2*i + 2 

        // If left child is larger than root 
        if (l < n && arr[l] > arr[largest]) 
                largest = l; 

        // If right child is larger than largest so far 
        if (r < n && arr[r] > arr[largest]) 
                largest = r; 

        // If largest is not root 
        if (largest != i) { 
                swap(arr[i], arr[largest]); 

                // Recursively heapify the affected sub-tree 
                heapify(arr, n, largest); 
        } 
} 

// main function to do heap sort 
void heapSort(int arr[], int n) 
{ 
        // Build heap (rearrange array) 
        for (int i = n / 2 - 1; i >= 0; i--) 
                heapify(arr, n, i); 

        // One by one extract an element from heap 
        for (int i = n - 1; i >= 0; i--) { 
                // Move current root to end 
                swap(arr[0], arr[i]); 

                // call max heapify on the reduced heap 
                heapify(arr, i, 0); 
        } 
} 

/* A utility function to print array of size n */
void printArray(int arr[], int n) 
{ 
        for (int i = 0; i < n; ++i) 
                cout << arr[i] << " "; 
        cout << "\n"; 
} 

// Driver program 
int main() 
{ 
        int arr[] = { 12, 11, 13, 5, 6, 7 }; 
        int n = sizeof(arr) / sizeof(arr[0]); 

        heapSort(arr, n); 

        cout << "Sorted array is \n"; 
        printArray(arr, n); 
} 

Code 3

// Heap Sort in C++
  
  #include <iostream>
  using namespace std;
  
  void heapify(int arr[], int n, int i) {
    // Find largest among root, left child 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)
      cout << arr[i] << " ";
    cout << "\n";
  }
  
  // Driver code
  int main() {
    int arr[] = {1, 12, 9, 5, 6, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
  
    cout << "Sorted array is \n";
    printArray(arr, n);
  }

Code 4

#include <iostream>
using namespace std;
  
// function to heapify the tree
void heapify(int arr[], int n, int root)
{
   int largest = root; // root is the largest element
   int l = 2*root + 1; // left = 2*root + 1
   int r = 2*root + 2; // right = 2*root + 2
  
   // If left child is larger than root
   if (l < n && arr[l] > arr[largest])
   largest = l;
  
   // If right child is larger than largest so far
   if (r < n && arr[r] > arr[largest])
   largest = r;
  
   // If largest is not root
   if (largest != root)
      {
      //swap root and largest
      swap(arr[root], arr[largest]);
  
      // Recursively heapify the sub-tree
      heapify(arr, n, largest);
      }
}
  
// implementing heap sort
void heapSort(int arr[], int n)
{
   // build heap
   for (int i = n / 2 - 1; i >= 0; i--)
   heapify(arr, n, i);
  
   // extracting elements from heap one by one
   for (int i=n-1; i>=0; i--)
   {
      // Move current root to end
      swap(arr[0], arr[i]);
  
      // again call max heapify on the reduced heap
      heapify(arr, i, 0);
   }
}
  
/* print contents of array - utility function */
void displayArray(int arr[], int n)
{
   for (int i=0; i<n; ++i)
   cout << arr[i] << " ";
   cout << "\n";
}
  
// main program
int main()
{
   int heap_arr[] = {4,17,3,12,9,6};
   int n = sizeof(heap_arr)/sizeof(heap_arr[0]);
   cout<<"Input array"<<endl;
   displayArray(heap_arr,n);
  
   heapSort(heap_arr, n);
  
   cout << "Sorted array"<<endl;
   displayArray(heap_arr, n);
}

Let me know if you have any doubts or if you need anything to change. 

If you are satisfied with the solution, please leave a +ve feedback : ) Let me know for any help with any other questions.

Thank You!
===========================================================================