Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# Fast Selection

·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```Selectv returns the position of the nth smallest number in the list.

Selectv modifies the list.

```
#include

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;
}

``````
Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.