int quicksearch(field A, int l, int r, int i) {
if (l < r) then {
q:= partition(A, l, r);
if (r-q >= i) then {
return quicksearch(A, q+1, r, i);
} else {
return quicksearch(A, l, q, i-r+q);
}
} else if (i = 1) then {
return l;
} else {
return -1;
}
}
int partition(field A, int l, int r) {
x:= A[(l+r) div 2];
i:= l-1;
j:= r+1;
partition1(A, x, i, j);
}
int partition1(field A, ele x, int i, int j) {
j--;
if (A[j] > x) then {
return partition1(A, x, i, j);
} else {
return partition2(A, x, i, j);
}
}
int partition2(field A, ele x, int i, int j) {
i++;
if (A[i] < x) then {
return partition2(A, x, i, j);
} else {
if (i < j) then {
exchange(A[i], A[j]);
partition1(A, x, i, j);
} else {
return j;
}
}
}
|