Finding n-th Smallest Element Using Partition List Of Quick Sort

Good day !

Need helps here.

I was told that I can search for a n-th smallest element in an array using the partition list function of quick sort, without having to sort it completely before getting the value.

For example, I got an array of 10 items. I would like to know the 3rd smallest element in the array.

I wonder how can I accomplish this ?

Thanks a lot.

SonicWave :p

p/s: Below is the funciton of the partition list i am using. THanks again.

void parti(int left, int right)
{
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = A[left];

while (left < right)
{
while ((A[right] >= pivot) && (left < right))
right--;
if (left != right)
{
A[left] = A[right];
left++;
}
while ((A[left] <= pivot) && (left < right))
left++;
if (left != right)
{
A[right] = A[left];
right--;
}
}
A[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;

displayArray();

if (left < pivot)
parti(left, pivot-1);
if (right > pivot)
parti(pivot+1, right);
}

Good day again.

I have did some modification and it works. I not sure it corrects or not but anyhow, I post it up here lar

:D

Thanks

SonicWave

void parti(int left, int right) { // This is a new function of partition list
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = A[left];

while (left < right) {
while ((A[right] >= pivot) && (left < right))
right--;
if (left != right) {
A[left] = A[right];
left++;
}

while ((A[left] <= pivot) && (left < right))
left++;
if (left != right) {
A[right] = A[left];
right--;
}
}

A[left] = pivot; // The pivot value is assigned to the fixed location since it is sorted

if (AnswerLocation == left) { // Compare the pivot location with the desired nth smallest element
printf("the %dth smallest number is %d\n",N,A[AnswerLocation]); // If equals, return the value of the array
} else {
pivot = left;
left = l_hold;
right = r_hold;

if (left < pivot)
parti(left, pivot-1);
if (right > pivot)
parti(pivot+1, right);
}
}

heaps are also useful for this sort of problems. Even selection sort can be used for small n/arrays :eek: