Thread: Finding a median in an array using quicksort

Hi, please help!
I have to do find a median of an array using modified quicksort or any recursive function and I'm having problems with it.
I have come up with this code so far, but I don't know what else to do.
Please help me!

Code:

#include <stdio.h>#include <stdlib.h>
#include <time.h>
 
#define SIZE 10
void write(const unsigned int *array, const char *text,
                 int start,  int End)
{
    int i;
    printf("%-10s", text);
    for (i = 0; i < SIZE; i++) {
        if (i < start || i > End) {
            printf("-- ");
        } else {
            printf("%2u ", array[i]);
        }
    }
    printf("\n");
}
 
void quicks(int *array, int i, int j, int k)
{
    int l, p;
    int pivot, pom, pp;
 
    l = i;
    p = j;
 
    pivot = array[(l + p) / 2];
    pp=(l + p) / 2;
    printf("pivot: array[%u] = %u\n", (l + p) / 2, pivot);
    write(array, "Before:", i, j);
 
    do {
        while (array[l] < pivot)
        {
            l++;
        }
        while (pivot < array[p])
        {
            p--;
	    }
 
        if (l <= p) {
            pom = array[l];
            array[l] = array[p];
            array[p] = pom;
            l++;
            p--;
        }
 
    } while (l <= p);
 
    write(array, "After:", i, j);


if(k<pp)
{
    if (i < p)
        quicks(array, i, p, k); 
    }
else if(k>pp)
{
    if (l < j)
        quicks(array, l, j, k); 
}
}
 
int main(void)
{
    int cycle;
    int k;
    unsigned int array[] = { 74, 43, 94, 24, 48, 76, 88, 33, 52, 59 };
 
    printf("%-10s", "Start:");
 
    for (cycle = 0; cycle < SIZE; cycle++) {
        printf("%2u ", array[cycle]);
    }
    printf("\n");
    k = SIZE/2;
    quicks(array, 0, SIZE - 1, k);
 
    printf("%-10s", "End:");
    for (cycle = 0; cycle < SIZE; cycle++) {
        printf("%2u ", array[cycle]);
    }
    printf("\n");
 
    return 0;
}

Also posted here.

Why don't you take a look at an algorithm called median of medians that is based on the quick select algorithm with a worst case of big-oh(N).

Wikipedia has a pseudocode section that you can look at Median of medians - Wikipedia, the free encyclopedia