You should write a recursive method called quicksort that takes as an arguement
ID: 3546955 • Letter: Y
Question
You should write a recursive method called quicksort that takes as an arguement an array of integers. your method should choose a pivot somewhere in the middle of the input array(it need not be exactly in the middle, especially if the array is of even size).
As we've seen, the quicksort method should then create two new arrays, less and greater, and place elements depending on whether they are greater or less than the pivot element. Recursively call quicksort on your two new arrays, less and greater.
Finally, write a main method to call and test your quicksort method. Create an array of integers by using the java built in method Math.random(). Your integers should each be greater than or equal to zero and less than 100.
Explanation / Answer
#include<stdio.h>
#define max_size 6
int A[max_size];
void quick _sort ( int a , int b ) / * quick sort recursive method * /
{
int r=0,t=0,k=a,l=0,pivot;
int la[max_size],ra[max_size];
pivot = A[ a ];
if( a = = b)
return ;
while ( k < b )
{
k ++ ;
if ( A [ k ] < A [ a ] )
{
la [ t ] = A [ k ] ;
t ++ ;
}
else
{
ra [ r ] = A [ k ];
r ++ ;
}
k = a ;
for ( l=0 ; l < t ; l ++ )
A [ k++ ] =pivot ;
for ( l=0 ; l < r ; l ++ )
A [ k ++ ] = ra [ l ] ;
if ( t > 0 )
quick _sort ( a , a + t -1 ) ;
if ( r > 0 )
quick sort ( b - r + 1 , b )
}
}
void printarr ( int a ) / * printing function * /
{
int i ;
for ( i=0 ; i < a ; i ++ )
{
printf ( " %d " , A [ i ] ) ;
printf ( " " ) ;
}
}
int main () / * main function here quick sort finction is called * /
{
int i , s ;
scanf ( " % d " , & s ) ;
for ( i=0 ; i < s ; i ++ )
{
scanf ( " % d " , & A [ i ] ) ;
}
printarr ( s ) ;
quick _ sort ( 0 , s - 1 ) ;
printarr ( s ) ;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.