##### Question

In: Computer Science

# Provide all steps b) Sort the keys 20, 31, 29, 45, 09, 98, 12, 23, 99,...

Provide all steps

b) Sort the keys 20, 31, 29, 45, 09, 98, 12, 23, 99, 66 in descending order using the Heap sort. Also write the algorithm.

1. a) Sort 99, 54, 64, 23, 12, 09, 45, 32, 19, 65, 89 using Quick sort. Write the algorithm.

b) Sort 69, 74, 64, 23, 12, 09, 45, 32, 19, 65, 88, 33, 60, 38 using Shell sort. Write the algorithm.

## Solutions

##### Expert Solution

b)

solutions:-

Heap sort using descending order

code:

def Heap(arr, n, i):
s=i
l=(2*i+1)
r=(2*i+2)
if l < n and arr[l] < arr[s]:
s=l
if r < n and arr[r] < arr[s]:
s=r
if s!= i:
(arr[i],
arr[s])=(arr[s], arr[i])
Heap(arr,n,s)

def Heap_Sort(arr,n):

for i in range(int(n/2)-1,-1,-1):
Heap(arr,n,i)
for i in range(n-1,-1,-1):

arr[0],arr[i]=arr[i],arr[0]

Heap(arr,i,0)

def printing(arr,n):
for i in range(n):
print(arr[i],end = " ")
print()

if __name__ == '__main__':
arr=[20, 31, 29, 45, 9, 98, 12, 23, 99, 66]
n=len(arr)
Heap_Sort(arr, n)
print("After the sorted array ")
printing(arr, n)

code in spyder:-

output:-

Algorithm:-

i) At first getting input data

ii) Than build up the min heap

iii) At that time smallest number is stored at the heap root.

iv) Than replace the last number from the heap and reducing the heap size

v) After reducing the heap size = 1

vi) Heap is the root

vii) Replace above step while heap>1.

--------------------------------------------------------------------------------------------------------------------------------

a)

solutions:-

Quick sort:-

code:-

#include <stdio.h>
#include<conio.h>
void swap(int *a, int *b)
{
int t=*a;
*a=*b;
*b=t;
}

int partition(int arr[],int l,int h)
{
int p=arr[h];
int i=(l-1);
for(int j=l;j<h;j++)
{
if(arr[j]<=p)
{
i++;
swap(&arr[i],&arr[j]);
}
}
swap(&arr[i+1],&arr[h]);
return (i+1);
}

void Quick_Sort(int arr[],int l,int h)
{
if(l<h)
{
int pi=partition(arr,l,h);
Quick_Sort(arr,l,pi-1);
Quick_Sort(arr,pi+1,h);
}
}

void printing(int arr[],int s)
{
for(int i=0;i<s;i++)
{
printf("%d\n",arr[i]);
}
}

int main()
{
int data[] = {99, 54, 64, 23, 12, 9, 45, 32, 19, 65, 89};
int n=(sizeof(data)/sizeof(data[0]));
Quick_Sort(data,0,n-1);
printf("Sorted array:\n");
printing(data,n);
}

code in dev c:-

output:-

Algorithm:-

Quick_Sort(arr, LMI, RMI)

if (LMI <RMI)

PI <- partition(arr, LMI, RMI)

Quick_Sort(arr, LMI, PI)

Quick_Sort(arr, PI + 1, RMI)

partition(arr,LMI, RMI)

set RMI as PI

store_Index<-LMI - 1

for (i <- LMI + 1 to RMI)

if (element[i] < P_Element)

swap element[i] and element[store_Index]

store_Index++

swap P_Element and element[store_Index+1]

return store_Index + 1

Note:-

LMI=Left Most Index

RMI=Right Most Index

P_Element=Pivot element

PI=pivot index

arr=Array

--------------------------------------------------------------------------------------------------------------

b)

solution:-

shell sort:-

code:-

#include <stdio.h>
#include<conio.h>
void Shell_Sort(int arr[],int n)
{
for(int in=n/2;in>0;in=in/2)
{
for(int i=in;i<n;i=i+1)
{
int t=arr[i],j;
for(j=i;j>=in && arr[j-in]>t;j=j-in)
{
arr[j]=arr[j-in];
}
arr[j]=t;
}
}
}
void printing(int arr[],int s)
{
for(int i=0;i<s;i++)
{
printf("%d \n",arr[i]);
}
}
int main()
{
int d[]={69, 74, 64, 23, 12, 9, 45, 32, 19, 65, 88, 33, 60, 38};
int s=sizeof(d)/sizeof(d[0]);
Shell_Sort(d,s);
printf(" After Sorted array: \n");
printing(d,s);
}

code in dev c:-

output:-

Algorithm:-

I. At first Initialize the value.

II. Rearrange the elements at n/2 times.

III. Rearrange all the elements at n/2 interval.

IV. Sort these sub-lists using insertion sort.

V. Repeat until complete list is sorted

## Related Solutions

##### Sort 101, 55, 64, 23, 12, 09, 45, 32, 19, 65, 89 using Quick sort. Write...
Sort 101, 55, 64, 23, 12, 09, 45, 32, 19, 65, 89 using Quick sort. Write the algorithm. Please show steps.
##### Steps and formula (if applied) are mandatory for all the questions. 1.   a) Sort the keys 66,...
Steps and formula (if applied) are mandatory for all the questions. 1.   a) Sort the keys 66, 99, 23, 12, 98, 09, 45, 29, 31, 20 in ascending order using the Heap sort. Also write the algorithm.                                                                                                                                                           b) Sort the keys 20, 31, 29, 45, 09, 98, 12, 23, 99, 66 in descending order using the Heap sort. Also write the algorithm. 2.   Construct a Huffman coding tree using the given Letters and frequencies below. Also write the algorithm. F:...
##### Steps and formula (if applied) are mandatory for all the questions. 3.   a) Sort 99, 54, 64,...
Steps and formula (if applied) are mandatory for all the questions. 3.   a) Sort 99, 54, 64, 23, 12, 09, 45, 32, 19, 65, 89 using Quick sort. Write the algorithm.                                                                   b) Sort 69, 74, 64, 23, 12, 09, 45, 32, 19, 65, 88, 33, 60, 38 using Shell sort. Write the algorithm.
##### old by years Interval Frequency 35-37 two 32-34 three 29-31 five 26-28 Six 23-25 four 20-22...
old by years Interval Frequency 35-37 two 32-34 three 29-31 five 26-28 Six 23-25 four 20-22 five 17-19 nine 14-16 Sixteen Calculate the above when Passport first used 1- what is the shape of the old distribution? 2- Which accurate statements can describe the relationship between the mean and median old? he mean and median are the same The mean is bigger than the median The mean is less than the median 3- Calculate percentile rank corresponding to the old...
##### For the stress data given below with the nearest error of 1: 27-17-11-24-36-13-29-22-18 23-30-12-46-17-32-48-11-18 18-32-26-24-38-24-15-13-13 18-21-27-20-16-15-37-19-19...
For the stress data given below with the nearest error of 1: 27-17-11-24-36-13-29-22-18 23-30-12-46-17-32-48-11-18 18-32-26-24-38-24-15-13-13 18-21-27-20-16-15-37-19-19 a) Construct a frequency distribution table. b) Construct the three types of statistical graphs. c) Determine the (1) Mean, (2) Median, (3) Mode, (4) Range, Variance, and (6) Standard Deviation.