Partial Sorting Array C

Question

I have an array that looks like this:

int array[] = {4.53, 3.65, 7.43, 9.54, 0.72, 0.0} 

I'm just wondering which method I can use to partially sort this array to bring the top three largest doubles to the front. I am looking for the most efficient method to get the top three numbers in this array.

So far I have used qsort , but I'm just looking for another way to do this, which could be even faster. I know that qsort O(nlogn) for better cases and O(n^2) for worst cases, but is there an even more efficient method to solve this problem? What I mean by efficiency is just a faster way to do this, better than O(nlogn) .

Any help would be great

Answer 1

Just save the first, second, third.

  first = array[0]; second = array[1]; third = array[2]; /* scratch sort for three elements */ if(first < second) swap(first, second); if(first < third) swap(first, third); if(second < third) swap(second, third); /* now go through, bubbling up if we have a hit */ for(i=3;i<N;i++) { if(third < array[i]) { third = array[i]; if(second < third) { swap(second, third); if(first < second) swap(first, second); } } } 

I would not increase to k = four. I think three is a limitation for hard coding. As k increases, you need to move on to the formal method.

This does not answer the question that you actually asked, namely how to partially sort, but it seems that this is what you want.

If you want to partially sort, you can use quicksort and just return earlier when the axis is above the border that interests you. So, our first core is divided into five, two. Ignore the last two and actually do subtypes of the last five. But while it will be faster than quicksort, it will not be a change of game. If you can get a conservative upper bound for the k-th element (for example, it will always be no more than 25% between the minimum and average), you can quickly eliminate most of the data. If you are mistaken, this is just one pass or two.

Using the quicksort Method

  int sortfirstk_r(int *array, int N, int k) { int pivot = 0; int j = n -1; int i = 1; while(i <= j) { if(array[pivot] < array[i]) swap(array[i], array[j--]) else i++; } sortfirstk_r(array, i, k < i ? k : i); if(i < k) sortfirstk_r(array +i, N -i, k - i); } 

(Unchecked and there may be errors in the slightly complicated sorting logic).

However, we naively used the first element as a support. If we sort a large data set, and we have a normal distribution, and we want to get the top 1%, then the z-score is 2.326. Take a little more to give us some sampling error, and we will make the first pass with a rotary set, say 2.3 standard deviations above average. Then we divide the distribution into two sets: the top 1% plus a bit, and the rest. We do not need to further process the rest and just sort the top group.

Answer 2

For your specific problem, the fastest way is to do something similar below, because you only need three elements: (It may be faster to use a priority queue or other data structure, but the speed will not be very noticeable)

 #include"stdio.h" void moveThreeMaxToFront(double * arr, int length); void moveMaxToFront(double*arr, int length); int main() { int i; double meh[]={ 5,3,1,7,2,9,11}; moveThreeMaxToFront(meh, 7); for(i=0; i<7; i++) printf("%f \n", meh[i]); } void moveThreeMaxToFront(double * arr, int length) { for(int i=0; i<3; i++) moveMaxToFront(arr++, length-i); } void moveMaxToFront(double* arr, int length) { int i; for(i=1; i<length; i++) { if(arr[i]>arr[0]) { double tmp=arr[i]; arr[i]=arr[0]; arr[0]=tmp; } } } 

However, it is potentially faster if k gets significantly larger than either Quickselect or using the partial_sort method, which I assume implements quickselect. However, the quickselect algorithm for this case has an average constant of approximately 3.4-4.4, which is slightly larger than the constant higher (3). Also note that quickselect has an average runtime of O (n). This runtime can be guaranteed using median 3, but this is not recommended as it significantly increases the average constant. Intro-select handles this correctly to prevent the worst case of quickselect, while preserving the average case.

Answer 3

If we need to find the three largest numbers, we can run the findMax method three times, and as soon as the maximum is found, replace the corresponding index (1, 2 or 3) maximum in the array. So we leave you with an array of the 3 largest elements when starting the array in c * O(n) time complexity.

Note: I used the fact that you need to find the first three maximum doublings.

 double findMax(double arr[i], double prevMax){ double maximum = -100000000000; for(int i = 0; i < arr.length; i++){ if(arr[i] < prevMax) maximum = max(arr[i], maximum); } return maximum; } 

Answer 4

I would suggest radix sorting - this is the most efficient sorting method for such cases and has O (n) complexity. You can even change it a bit to stop when you find the three maximum numbers. You can find and understand the short circuit: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html