I am writing a routine to calculate median using the minimum of the numbers and then changing the value of the minimum to a large value outside the range of numbers (assuming you know the nature of the numbers).  I know I could use many other proven techniques, but have chosen to play around with this one.I don't see why the performance is poor. There are 3 loops, however, only two are nested at any one time.  There is no sorting involved, only finding the first occurrence of a minimum and making the new value outside the range.  If it finds the same number a second time, it ignores the number until the next iteration.  It iterates for half of the total series before the median is found.  It works dandy except for the speed.  How do I improve the efficiency of this code?float trashMin(float array[], unsigned int length, float median){    //what we want to do in this routine is find the lowest in the array    //we then make the lowest number, the same as the highest possible number and     //after iteratively going through the array 1/2 of the full length we will find the median    unsigned int halflength = (length / 2) + 1;    unsigned int i = 0;    unsigned int j = 0;    unsigned int k = 0;    float highNumber = 999.0;//this is an arbitrary number, well outside of range of the number series    float median = 0;    for (i = 0; i < halflength; ++i)    {        float lowestInArray = array[0];        bool firstTime = true;// is it the first time we see this number        for (j = 0; j < length; ++j)        {// find the lowest and highest number in the array            float comparitor = array[j];            lowestInArray = (lowestInArray < comparitor) ? lowestInArray : comparitor;        }//end j        // now that we know which is the smallest number, eliminate only 1st occurance of it                    for (k = 0; k < length; ++k)        {            float comparitor = array[k];                            if (comparitor == lowestInArray && firstTime == true)            {                array[k] = highNumber;                firstTime = false;            }        }//end k        median = lowestInArray;    }//end i    return median;}
Performance of Median routine using min performs abysmally
c++;performance;algorithm;c;sorting
The structure of your function isfor (i = 0; i < halflength; ++i)    // N/2 iterations{    ...    for (j = 0; j < length; ++j)    // N iterations    {        ...     }    for (k = 0; k < length; ++k)    // N iterations    {        ...    }}this makes \$ N/2 (N+N) = N^2\$ iterations, where \$ N \$ is the lengthof the array.There are small improvements possible: In the k-loop, if amatching element has been found, you can break-out early:    // now that we know which is the smallest number, eliminate only 1st occurance of it                for (k = 0; k < length; ++k)    {        float comparitor = array[k];                        if (comparitor == lowestInArray)        {            array[k] = highNumber;            break;        }    }But actually this loop is not needed at all: In the j-loop,remember the index where the lowest element has been found,and then set to a large number directly:    float lowestInArray = array[0];    unsigned int indexOfLowest = 0;    for (unsigned int j = 1; j < length; ++j) {        float comparitor = array[j];        if (comparitor < lowestInArray) {            lowestInArray = comparitor;            indexOfLowest = j;        }    }    array[indexOfLowest] = FLT_MAX;Also FLT_MAX is a better choice than 999.0 for a large number.This reduces the number of iterations by a factor of 2.If it finds the same number a second time, it ignores the number until  the next iteration.Yes, but the j-loop still traverses over the entire array. Instead ofreplacing the found minimal element by FLT_MAX, you could replace itby the last array element, and then reduce the upper boundfor the j-loop accordingly:for (unsigned int i = 0; i < halflength; ++i){    float lowestInArray = array[0];    unsigned int indexOfLowest = 0;    for (unsigned int j = 0; j < length - i; ++j) {        float comparitor = array[j];        if (comparitor < lowestInArray) {            indexOfLowest = comparitor;            indexOfLowest = j;        }    }    array[indexOfLowest] = array[length - i - 1];    median = lowestInArray;}This reduces the number of iterations again. But it is still\$  O(N^2) \$, and I doubt that much more is possible with thisalgorithm.As you already noticed, sorting the array first and then takingthe middle element is faster. This is no surprise since sorting cantypically be done in \$  O(N \log N) \$ operations.