Question

Subject: Algorithm

2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A 17, 3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps.

need this urgent please.

Answer 1

2.1

1.

code

solution

1. # include<iostream> //standard input and output using namespace std; void swap (int array1[],int il,int j1) array1 [11] +=array1 [j1] ; arrayl[j1] Farrayl[i1]-arrayl[11]; array1 [11]-=array1 [j1] ; void max_heap (int data[],int heap_Size,int index_val) max=index val ; int int left-2 index val+1; int right-2*index_val+2; if (left <heap_Size &&data[left] > data [max] ) max-left; if (right < heap_Size &&data [right] >data [max]) max-right; if (max! =index-val) swap (data [max], data[index_val]); max_heap (data,heap_Size,max) void heap_sort (int data], int num) for (int i1 = num / 2-1; il >= 0; il--) max_heap (data, num, il); for (int il-num-1; i1>-0; i1--) swap (data [0],data[i1]); max_heap (data, i1,0);

int main() int arrayll7,3,9,3,2,5,6,1,8 int array_size-g; int index_val-0; heap-sort (array!, array-size) ;ו do t cout<carrayl[index_vall: index val++ while (index_valcarray_size && cout<<", ");

//output

1,2,3,3,5,6,7,8,9

//copyable code

1.

#include<iostream>

//standard input and output

using namespace std;

void swap(int array1[],int i1,int j1)

{

array1[i1]+=array1[j1];

array1[j1]=array1[i1]-array1[j1];

array1[i1]-=array1[j1];

}

void max_heap(int data[],int heap_Size,int index_val)

{

   int max=index_val;

   int left=2*index_val+1;

   int right=2*index_val+2;

   if(left < heap_Size && data[left] > data[max])

   {

       max=left;

   }

   if(right < heap_Size && data[right] > data[max])

   {

       max=right;

   }

   if(max!=index_val)

   {

       swap(data[max],data[index_val]);

       max_heap(data,heap_Size,max);

   }

}

void heap_sort(int data[], int num)

{

for (int i1 = num / 2 - 1; i1 >= 0; i1--)

max_heap(data, num, i1);

for (int i1=num-1; i1>=0; i1--)

{

swap(data[0],data[i1]);

     

max_heap(data, i1,0);

}

}

int main()

{

   int array1[]={7,3,9,3,2,5,6,1,8};

   int array_size=9;

   int index_val=0;

   heap_sort(array1,array_size);

   do{

       cout<<array1[index_val];

       index_val++;

   }while(index_val<array_size && cout<<",");

}

2 <bits/stdc++.h> #include using namespace std; //merge function void merge (int arrvalue[], int startvalue, int midvalue, int endvalue) int startvalue2 = midvalue + 1; sorted if (arrvalue [midvalue] arrvalue [ startvalue2] <= returni if (arrvalue [startvalue] <- arrvalue [startvalue2]) [ startvalue++ else int value = arrvalue [startvalue2]; int index = startvalue2; while (index != 3tartvalue) arrvalue [index] = arrvalue [index - 1]; index-- arrvalue [startvalue] = value ; startvalue++ midvalue+t; startvalue2+t

void merge Sort (int arrvalue [], int l, int r) if (l < r) int m1 (r - 1) / 2; merge_Sort (arrvalue, l, m); merge_Sort (arrvalue, m + l, r); merge (arrvalue, l, m, r); void display (int A[], int size) int i; printf("%d printf("In") ", A[1]); int main() int arrvalue [7,3,9,3,2,5,6,1,8; int arrvalue_sizesizeof (arrvalue)/ sizeof (arrvalue [0]) merge Sort (arrvalue, 0, arrvalue size -1) display (arrvalue, arrvalue_size); return 0

//output

1 2 33 56789

//copyable code

#include <bits/stdc++.h>

using namespace std;

//merge function

void merge(int arrvalue[], int startvalue, int midvalue, int endvalue)

{

    int startvalue2 = midvalue + 1;

    // sorted

    if (arrvalue[midvalue] <= arrvalue[startvalue2]) {

        return;

    }

    while (startvalue <= midvalue && startvalue2 <= endvalue) {

  

        if (arrvalue[startvalue] <= arrvalue[startvalue2]) {

            startvalue++;

        }

        else {

            int value = arrvalue[startvalue2];

            int index = startvalue2;

         

            while (index != startvalue) {

                arrvalue[index] = arrvalue[index - 1];

                index--;

            }

            arrvalue[startvalue] = value;

            startvalue++;

            midvalue++;

            startvalue2++;

        }

    }

}

void merge_Sort(int arrvalue[], int l, int r)

{

    if (l < r) {

        int m = l + (r - l) / 2;

          merge_Sort(arrvalue, l, m);

        merge_Sort(arrvalue, m + 1, r);

        merge(arrvalue, l, m, r);

    }

}

void display(int A[], int size)

{

    int i;

    for (i = 0; i < size; i++)

        printf("%d ", A[i]);

    printf("\n");

}

  

int main()

{

    int arrvalue[] = {7,3,9,3,2,5,6,1,8};

    int arrvalue_size = sizeof(arrvalue) / sizeof(arrvalue[0]);

    merge_Sort(arrvalue, 0, arrvalue_size - 1);

    display(arrvalue, arrvalue_size);

    return 0;

}

3. Worst case for quick sort . Quick sort has unbalanced partition so call cn time for some constant c The recursive call as n-1 elements taksc(n-1).another elements c(n-2) and so on worst-case running time is e(n2) Worst case Time complexity It occurs the partttion process then it will picks greatest or smallest element as pivot Last element is always picked as pivot element Worst case occur when the array can be sorted in increasing or decreasing order T(n) = T(0)-T(n-1) + Equivalent to T(n) T(n-1)+ (n) а») (n)