Частично сортировка массива C

Question

У меня есть массив, который выглядит следующим образом:

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

Я просто интересно, что метод, который я могу использовать, чтобы частично сортировать этот массив, чтобы принести в тройку крупнейших двойников на фронт. Я ищу наиболее эффективный метод для получения трех верхних чисел в этом массиве.

До сих пор я использовал qsort, но я просто ищу другой способ сделать это, что может быть еще быстрее. Я знаю, что qsort является O(nlogn) для лучших случаев и O(n^2) для худших случаев, но есть ли еще более эффективный метод для решения этой проблемы? То, что я подразумеваю под эффективностью, - это просто более быстрый способ сделать это, лучше, чем O(nlogn).

Любая помощь будет большим

Answer 1

Просто сохраните первый, второй, третий.

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

Я бы не стал масштабировать до k = четыре. Я думаю, что три - это ограничение для жесткого кодирования. Поскольку k получить большой, вам нужно перейти к формальному методу.

Это не отвечает на вопрос, который вы на самом деле просили, а именно, как частично сортировать, но, похоже, это то, что вы хотите.

Если вы хотите частично отсортировать, вы можете использовать quicksort и просто вернуться раньше, когда ось будет выше границы, которую вас интересует. Итак, наш первый стержень делится на пять, два. Игнорируйте последние два и на самом деле выполняйте подтипы последних пяти. Но пока это будет быстрее, чем quicksort, это не будет смена игры.Если вы можете получить консервативную верхнюю границу для k-го элемента (например, она будет составлять не более 25% между минимумом и средним значением), вы можете быстро устранить большую часть данных. Если вы ошибаетесь, это всего лишь один проход или два.

Используя метод QuickSort

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

    } 

(UNTESTED и там могут быть ошибки в немного хитрой логики сортировки).

Однако мы наивно использовали первый элемент в качестве стержня. Если мы сортируем большой набор данных, и у нас есть нормальный дистрибутив, и мы хотим получить верхнюю 1%, то z-счет равен 2.326. Возьмите немного больше, чтобы дать нам некоторую ошибку выборки, и мы сделаем первый проход с поворотным набором, скажем, 2.3 стандартными отклонениями выше среднего. Затем мы разделяем распределение на два набора: верхние 1% плюс немного, а остальные. Нам не нужно дальше обрабатывать остальные, а просто сортировать верхнюю группу.

Answer 2

Если мы должны выяснить три наибольшее число, то мы можем запустить findMax методу три раза и один раз максимум найден заменить соответствующий индекс (1, 2 or 3) с максимумом в массиве. Таким образом, мы оставим вас с массивом 3 самых больших элементов при запуске массива в c * O(n) временной сложности.

Примечание: Я использовал тот факт, что вы должны найти первые три максимальных двойников

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 3

Я хотел бы предложить базисное то это наиболее эффективный метод сортировки для таких случаев и имеет сложность O (N). Вы можете даже немного изменить его, чтобы остановиться, когда найдете три максимальных числа. Вы можете найти понимания радикс коротко: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

Answer 4

Для конкретной задачи самый быстрый способ сделать что-то подобное ниже, так как вы хотите, только три элемента: (Это может быть быстрее использовать очереди приоритета или другие данные структура, но скорость не будет очень заметно)

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

Однако потенциально быстрее, если к становится значительно больше, либо реализовать Quickselect или использовать метод partial_sort который я считаю, реализующий быстрый выбор. Однако алгоритм quickselect для данного случая имеет среднюю константу приблизительно 3,4-4,4, которая немного больше константы выше (3). Также обратите внимание, что quickselect имеет среднее время работы O (n). Это время выполнения может быть гарантировано с использованием медианы 3, но это не рекомендуется, так как оно значительно увеличивает среднюю константу. Intro-select правильно обрабатывает это, чтобы предотвратить наихудший случай quickselect, сохраняя при этом свой средний случай.