//
// Assignment 1 : Program to find the ith minimum element from a n-set in worst case O(n) time.
//
// Author : Saket Soni, M.Tech. CS, Sem II, Session 2004-06
// Roll : mtc0420
// Subject : Design and Analysis of Algorithms
// Submitted to : Shri. Krishnendu Mukhopadhyay
// Date : February 10, 2005
///////////////////////////////////////////////////////////////////////////////////////////////
// Header Files ...
///////////////////////////////////////////////////////////////////////////////////////////////
//
#include
#include
///////////////////////////////////////////////////////////////////////////////////////////////
// Function Declarations ...
///////////////////////////////////////////////////////////////////////////////////////////////
//
int search(int *piArray, int i, int noOfElementsInTheArray);
// to find the ith minimum element in the piArray.
int findMedian(int *piArray, int noOfElementsInTheArray);
// findMedian function finds the location of the approximate median of the
// elements in the piArray.
int findMed(int *piArray, int noOfelementsInTheArray);
// this function is used by the findMedian function, this function assumes that two
// consecutive element in array form a single element, the even pos, stores the number,
// and the odd pos, stores the location in the original Array.
void mysort(int *piArray, int noOfElementsInTheArray);
// findMed function sorts the elements in the array using insertion sort and then returns
// the median element of the piArray, here piArray is same as the piArray used in the
// findMed function.
void quickSort(int *piArray, int noOfElementsInTheArray);
// quickSort sorting algorithm for debugging purpose.
///////////////////////////////////////////////////////////////////////////////////////////////
// Application Entry Point (the main function) ...
///////////////////////////////////////////////////////////////////////////////////////////////
//
int main()
{
int piArray[100000]; // the set of input numbers
int iNoOfElements; // the cardinality of the set
int iCounter; // the counter variable
int iOrder; // the i of the ith term to be found
int iResult; // the ith term, i.e. the result
int seed; // random number seed
printf("Enter the seed value for random number generation : ");
scanf("%d",&seed);
srand(seed);
printf("Enter the no of elements to generate : ");
scanf("%d",&iNoOfElements);
printf("Enter the order of the element to be found : ");
scanf("%d",&iOrder);
// iNoOfElements = 100000; // debug mode
// srand(1234); // debug mode
// iNoOfElements = 100; // debug mode
// srand(15); // debug
mode
// initialize the iAr array with random numbers ...
printf("The array generated is ...\n");
for(iCounter = 0; iCounter < iNoOfElements; iCounter++) {
piArray[iCounter] = ((float)rand())/RAND_MAX * 1000;
printf("%4d ", piArray[iCounter]);
if ( !((iCounter+1)%10) )
printf("\n");
}
// iOrder = 65650; // debug mode
// iOrder = 50; // debug mode
// find the iOrder'th min number in the piArray set ...
iResult = search(piArray, iOrder, iNoOfElements);
// print the output ...
printf("\nThe %d'th smallest no. (using our algo) : %d", iOrder, iResult);
// Checking the result by actual sorting ...
printf("\n\nNow checking the result by actual sorting ... ");
quickSort(piArray,iNoOfElements);
printf("\nArray after sorting is ...\n");
for(iCounter = 0; iCounter < iNoOfElements; iCounter++) {
printf("%4d ", piArray[iCounter]);
if ( !((iCounter+1)%10) )
printf("\n");
}
printf("\nThe %d'th smallest no. (using sorting) : %d\n", iOrder, piArray[iOrder-1]);
if ( piArray[iOrder-1] == iResult )
printf("Success!!!\n");
else
printf("F a i l u r e ! ! !\n");
}
///////////////////////////////////////////////////////////////////////////////////////////////
// search function to find the ith minimum element in the piArray ...
///////////////////////////////////////////////////////////////////////////////////////////////
//
int search(int *piArray, int iOrder, int iNoOfElements)
{
int iTemp; // temporary storage for swapping
int iPivot; // index to pivot element
int iEdge; // other index used for partitioning
iPivot = findMedian(piArray,iNoOfElements); // find a good pivot element
iTemp = piArray[0]; // bring the pivot element into the first
piArray[0] = piArray[iPivot]; // location of the piArray
piArray[iPivot] = iTemp;
iPivot = 0; iEdge = iNoOfElements-1; // initialize the indices for partitioning
while ( 1 ) // do the partitioning
{
while ( iEdge != iPivot && piArray[iEdge] > piArray[iPivot] ) iEdge--;
if ( iEdge == iPivot )
break;
else {
iTemp = piArray[iEdge]; piArray[iEdge] = piArray[iPivot];
piArray[iPivot] = iTemp;
iTemp = iEdge; iEdge = iPivot; iPivot = iTemp;
}
while ( iEdge != iPivot && piArray[iEdge] <= piArray[iPivot] ) iEdge++;
if ( iEdge == iPivot )
break;
else {
iTemp = piArray[iEdge]; piArray[iEdge] = piArray[iPivot];
piArray[iPivot] = iTemp;
iTemp = iEdge; iEdge = iPivot; iPivot = iTemp;
}
}
if ( iPivot+1 == iOrder ) // if pivot's order is the required order then
return
return piArray[iPivot]; // the value of the pivot
else if ( iPivot+1 > iOrder ) // else find the partitin containing the our order
return search(piArray,iOrder,iPivot);
else
return search(piArray+iPivot+1,iOrder-iPivot-1,iNoOfElements-iPivot-1);
}
///////////////////////////////////////////////////////////////////////////////////////////////
// findMedian function finds the location of the approximate median of the
// elements in the piArray ...
///////////////////////////////////////////////////////////////////////////////////////////////
//
int findMedian(int *piArray, int iNoOfElements)
{
int iCounter, *piArr;
// initialize the array for use with findMed function ...
piArr = (int*) malloc (iNoOfElements*2*sizeof(int));
if ( piArr == NULL ) {
printf("Out of Memory!");
exit(1);
}
for ( iCounter = 0 ; iCounter < iNoOfElements ; iCounter++ ) {
piArr[iCounter*2] = piArray[iCounter]; // even location stores the value
piArr[iCounter*2+1] = iCounter; // odd location stores the location of the value
}
return findMed(piArr,iNoOfElements); // call findMed function to actually find
the
// median
}
///////////////////////////////////////////////////////////////////////////////////////////////
// findMed function is used by the findMedian function, this function assumes that two
// consecutive element in array form a single element, the even pos, stores the number,
// and the odd pos, stores the location in the original Array ...
///////////////////////////////////////////////////////////////////////////////////////////////
//
int findMed(int *piArray, int iNoOfElements)
{
int iNoOfGroups; // for the number of 5 element groups
int iCounter; // for use in the loops
int *piArr; // for array to store the medians of the
groups
iNoOfGroups = ((float)iNoOfElements+4)/5; // calculate the no. of groups
if ( iNoOfGroups == 1 ) { //
if only one group
mysort(piArray,iNoOfElements); // then sort, and then
return piArray[((iNoOfElements-1)/2)*2+1]; // return the location of the median
}
// allocate memory to store the medians of the various groups ...
piArr = (int*) malloc (iNoOfGroups*2*sizeof(int));
if ( piArr == NULL ) {
printf("Out of Memory!");
exit(1);
}
// find the median of each group and store it in the piArr array ...
for ( iCounter = 0 ; iCounter < iNoOfGroups-1 ; iCounter++ ) {
mysort(piArray+iCounter*5*2,5);
piArr[iCounter*2] = piArray[(iCounter*5+2)*2];
piArr[iCounter*2+1] = piArray[(iCounter*5+2)*2+1];
}
// this is to handle the last group of possibly less than 5 elements ...
if ( iNoOfElements%5 ) {
mysort(piArray+iCounter*5*2,iNoOfElements%5);
piArr[iCounter*2] = piArray[(iCounter*5+(iNoOfElements%5)/2)*2];
piArr[iCounter*2+1] = piArray[(iCounter*5+(iNoOfElements%5)/2)*2+1];
}
else {
mysort(piArray+iCounter*5*2,5);
piArr[iCounter*2] = piArray[(iCounter*5+2)*2];
piArr[iCounter*2+1] = piArray[(iCounter*5+2)*2+1];
}
// recursive call on the array of medians to find the median of the medians
iCounter = findMed(piArr,iNoOfGroups); // temporarily storing the location of
// the median of the medians in iCounter
// so that we could free piArr before returning.
free(piArr);
return iCounter; // return the location of the median of the medians
}
///////////////////////////////////////////////////////////////////////////////////////////////
// findMed function sorts the elements in the array using insertion sort and then returns
// the median element of the piArray, here piArray is same as the piArray used in the
// findMed function ...
///////////////////////////////////////////////////////////////////////////////////////////////
//
void mysort(int *piArray, int iNoOfElements) // sorting using insertion sort algo
{
int iCounter1, iCounter2, iTemp1, iTemp2; // counters and temporary variables
for ( iCounter1 = 1 ; iCounter1 < iNoOfElements ; iCounter1++ )
{
iCounter2 = iCounter1;
iTemp1 = piArray[iCounter2*2]; // store the next value in temporay
location
iTemp2 = piArray[iCounter2*2+1];
// find the position where to insert in the already
sorted array ...
while ( iCounter2> 0 && piArray[(iCounter2-1)*2] > iTemp1 ) {
piArray[iCounter2*2] = piArray[(iCounter2-1)*2];
piArray[iCounter2*2+1] = piArray[(iCounter2-1)*2+1];
iCounter2--;
}
// finally insert at the found location ...
piArray[iCounter2*2] = iTemp1;
piArray[iCounter2*2+1] = iTemp2;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////
// quickSort sorting algorithm for debugging purpose ...
///////////////////////////////////////////////////////////////////////////////////////////////
//
void quickSort(int *piArray, int iNoOfElements) // used for debugging purpose
{
int iEdge, iPivot, iTemp; // variable declarations
// trivial case if array size is less than 2 ...
if ( iNoOfElements <= 1 )
return;
// do the partitioning ...
iPivot = 0; iEdge = iNoOfElements-1;
while ( 1 )
{
while ( iEdge != iPivot && piArray[iEdge] > piArray[iPivot] ) iEdge--;
if ( iEdge == iPivot )
break;
else {
iTemp = piArray[iEdge]; piArray[iEdge] = piArray[iPivot];
piArray[iPivot] = iTemp;
iTemp = iEdge; iEdge = iPivot; iPivot = iTemp;
}
while ( iEdge != iPivot && piArray[iEdge] <= piArray[iPivot] ) iEdge++;
if ( iEdge == iPivot )
break;
else {
iTemp = piArray[iEdge]; piArray[iEdge] = piArray[iPivot]; piArray[iPivot] = iTemp;
iTemp = iEdge; iEdge = iPivot; iPivot = iTemp;
}
}
// recursivly sort the partitioned arrays ...
quickSort(piArray,iPivot);
quickSort(piArray+iPivot+1,iNoOfElements-iPivot-1);
}