Question

Sort 101, 55, 64, 23, 12, 09, 45, 32, 19, 65, 89 using Quick sort. Write the algorithm.

Please show steps.

Answer 1

Solutions:-

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[] = {101, 55, 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);
}

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