Mu Sigma Interview Questions

#include // including library files 
int temp;
void heapify(int arr[], int size, int i)//declaring functions
{
int max = i;
int left = 2*i + 1;
int right = 2*i + 2;

if (left < size && arr[left] >arr[max])
max= left;

if (right < size && arr[right] > arr[max])
max= right;

if (max!= i)
{
// performing sorting logic by using temporary variable
temp = arr[i];
arr[i]= arr[max];
arr[max] = temp;
heapify(arr, size, max);
}
}

void heapSort(int arr[], int size)// providing definition to heap sort
{
int i;
for (i = size / 2 - 1; i >= 0; i--)
heapify(arr, size, i);
for (i=size-1; i>=0; i--)
{
// swaping logic
temp = arr[0];
arr[0]= arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}

void main() // defining main()
{
int arr[] = {58, 134, 3, 67, 32, 89, 15, 10,78, 9};
// array initializing with their elements.
int i;
int size = sizeof(arr)/sizeof(arr[0]);

heapSort(arr, size);

printf("printing sorted elements\n"); // printing the sorted array
for (i=0; i<size; ++i)
printf("%d ",arr[i]);
}

#include

using namespace std;

void heapify(int arr[], int n, int i)
{
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;
 
    //If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;
 
    //If right child largest 
    if (r < n && arr[r] > arr[largest])
        largest = r;
 
    //If root is nor largest
    if (largest != i)
    {
        swap(arr[i], arr[largest]);
 
        //Recursively heapifying the sub-tree
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n)
{
    
    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--)
    {
        //Moving current root to end
        swap(arr[0], arr[i]);
 
        //Calling max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}
 
//Function to print array
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << "\n";
}
 

int main()
{
    int arr[] = {1, 14, 3, 7, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Unsorted array  \n";
    display(arr, n);
    
    heapSort(arr, n);
 
    cout << "Sorted array  \n";
    display(arr, n);
}