Academic Integrity: tutoring, explanations, and feedback — we don’t complete graded work or submit on a student’s behalf.

#include <stdio.h> #include <stdlib.h> int quickselect( int *A, int k, int n); i

ID: 3585128 • Letter: #

Question

#include <stdio.h>
#include <stdlib.h>

int quickselect( int *A, int k, int n);

int main(void)
{  
long i;
int *space; int tmp;
space = (int *) malloc( 1000000*sizeof(int));
for( i=0; i< 500000; i++ )
{ *(space + i) = ((139*i)%500000);
*(space + i + 500000) = 1000000 + ((141*i)%500000);
}
if( (tmp = quickselect( space, 500001, 1000000)) != 1000000 )
{ printf(" Failed test 1. Returned %d instead of 1000000 ", tmp);
fflush(stdout); exit(-1);
}
else printf("passed test1 ");
for( i=0; i< 500000; i++ )
{ *(space + i) = ((139*i)%500000);
*(space + i + 500000) = 1000000 + ((141*i)%500000);
}
if( (tmp = quickselect( space, 1, 1000000)) != 0 )
{ printf(" Failed test 2. Returned %d instead of 0 ", tmp);
fflush(stdout); exit(-1);
}
else printf("passed test2 ");
for( i=0; i< 500000; i++ )
{ *(space + i) = ((139*i)%500000);
*(space + i + 500000) = 1000000 + ((141*i)%500000);
}
if( (tmp = quickselect( space, 124, 1000000)) != 123 )
{ printf(" Failed test 3. Returned %d instead of 123 ", tmp);
fflush(stdout); exit(-1);
}
else printf("passed test3 ");

printf("Quickselect successful ");
exit(0);
}

Implement the quickselect algorithm on arrays. You write one function int quickselect (int *A, int k, int n); which returns the k-th smallest entry of an array A of length n. The programming language is C or C++; test your code before submission using the gcc or g++ compiler. Please remove all dead code; try to program as clearly as possible, since I try to read it. Your function for this should be less than fifty lines of code long. You can use the quicksort code that I distributed, but do not copy code from another student or from the web; this is an easy project.

Explanation / Answer

Here is the quickSelect code for you:

int quick(int array[],int low,int high)
{
int pivot,rb;
pivot = low;
rb = high;
while(low <=high)
{
while(array[pivot] >= array[low] && low <=rb)
{ low++; }
while(array[pivot] < array[high])
{ high--; }
if(pivot != high)
{
array[pivot] = array[pivot] + array[high];
array[high ] = array[pivot] - array[high];
array[pivot] = array[pivot] - array[high];
}
}
  

return high;
}

int quicksort(int array[],int k, int low,int high)
{
int pivot;
if(low <= high)
{
pivot = quick(array,low,high);
if(pivot == k)
   return array[pivot];
else if(pivot > k)  
   return quicksort(array,k,low,pivot-1);
else
   return quicksort(array,k,pivot+1,high);
}
}
int quickselect(int *A, int k, int n)
{
    return quicksort(A, k, 0, n-1);
}

Related Questions

#include <stdio.h> #include <math.h> #define MAX 4.0 #define MIN 2.0 int main(vo
Question #3727785
#include <stdio.h> #include <math.h> int main() { double a = 1000, t = 360, one
Question #3631319
#include <stdio.h> #include <math.h> int main() { float salary; float results; p
Question #3759928
#include <stdio.h> #include <math.h> int main(void){ int n, d; printf(\"Enter an
Question #3642970
#include <stdio.h> #include <stdib.h> int main (int argo, char* argv[]) { printf
Question #3628176
#include <stdio.h> #include <stdint.h> #include <assert.h> typedef uint8_t byte;
Question #3872887
#include <stdio.h> #include <stdlib.h> #define PRECISION 3 double absD (double n
Question #3557728
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <sys/time.h>
Question #3689671

Navigate

Previous
#include <stdio.h> #include <stdlib.h> int play_game(int *); // Returns 0 if pla
Next
#include <stdio.h> #include <stdlib.h> main() { char string 1 [4], string 2 [10]

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.