Quickselect is like half of Quicksort, with only one

recursive call instead of two.

We select a random comparison element (pivot),

and divide the array into the smaller and larger part.

(exactly like quicksort). If the pivot is the L-th smallest

item, then the smaller part contains L - 1 items, and

the larger part n - L items. If we are looking for the k-th

smallest item

- if k

looking for the k-th smallest item among the L-1 items

in the smaller part

- if k == L: we return the pivot, which is the L-th smallest item.

- if k > L: we do a recursive call on the larger part, looking

for the (k - L)-th smallest item in the larger part.

So after the division phase we know whether the

k-th smallest item is in the smaller part or in the larger part,

and we need to continue the search only on that part.

This reduces the expected runtime from O(n log n)

to O(n). Quickselect is a linear time selection algorithm.

Especially it can find the median in linear time, where the

alternative would be to sort the array in n log n time,

and then pick the middle element.

Test Code

#include

#include

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

{ *(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

{ *(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

{ *(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);

}

//This is the main function, which calls the function you implemented. It is essential that you stick to the interface that is specified in the homework

Course CSC 220 Algorithms Spring Semester 2020 Homework Project 1 Given 02/10/2020, Due 02/26/2020 Write a function that implements quickselect to find the k-th smallest element in an array of n elements (1