Question

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.

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.

Answer 1

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