Fast Selection

• Tweet
• 

        Selectv returns the position of the nth smallest number in the list.

Selectv modifies the list.

#include <stdio.h>

typedef struct {
	int len;
	int e[102];
} List;

void printv(char *msg, List l) {
	printf("%s", msg);
	int i;
	for (i = 0; i < l.len; ++i)
		printf("%d ", l.e[i]);
	printf("\n");
}

int pivot(List *l, int p, int r) {
	int x = l->e[r];
	int i = p - 1;
	int j = r + 1;
	
	while (1) {
		do {
			++i;
		} while (l->e[i] < x);
		do {
			--j;
		} while (l->e[j] > x);
	
		//printf("%d %d\n", i, j);
		
		if (i < j) {
			int aux = l->e[i];
			l->e[i] = l->e[j];
			l->e[j] = aux;
		} else
			return i - 1;
	}
}


int selectv(List *l, int nrp, int p, int r) {
	//printf("p, r: %d, %d\n", p, r);
	//printf("nrp: %d\n", nrp);
	//printv("l: ", *l);
	
	if (p == r)
		return l->e[p];
	
	if (p < r) {
		int q = pivot(l, p, r);
		
		//getchar();
		
		if (q - p + 1< nrp)
			return selectv(l, nrp - (q - p) - 1, q + 1, r);
		return selectv(l, nrp, p, q);
	}
	return -1;
}

int main(int argc, char *argv[]) {
	List l;
	l.len = 100;
	int i;
	for (i = 0; i < l.len; ++i)
		l.e[i] = l.len - i;
	
	int nth = 56;
	printf("%d: %d\n", nth, selectv(&l, nth, 0, l.len - 1));
	
	//printv("L: ", l);
	
	return 0;
}

Tags:
• algorithm
• C
• Fast
• select