Не стыдитесь пузырьковых сортов, у них есть свое место.Если ваш набор данных имеет небольшой размер, его легко кодировать и он стабилен, если вы все делаете правильно (никогда не меняйте местами одинаковые элементы).
Это также может быть ослепительно быстрым, если ваши данные в основномотсортированы, чередуя направления на каждом проходе.Я знаю, что вы сказали, что изначально он не был почти отсортирован, я говорю о том, что это может произойти, если вы сортируете, то сохраните.В любом случае, если размер набора данных небольшой, на самом деле не имеет значения, является ли он полностью несортированным.
Это , особенно , если, как вы упомянули в комментарии к другомуответ, размер вашего набора данных составляет около 11. Если не считать алгоритма сортировки, явно разработанного , чтобы быть преднамеренно ужасным, любой алгоритм легко справится с таким размером достаточно быстро.
Если ваша среда не 'Чтобы предложить стабильную сортировку, я бы просто пошел с пузырьковой сортировкой, учитывая ваши ограничения и свойства.
Фактически, используя следующую программу вместе с утилитой time, я обнаружил, чтоПроцессорное время, используемое для qsort и сортировки пузырьков, начинает меняться только после того, как количество элементов достигло 10 000.
И даже тогда сортировка пузырьков заняла менее половины секунды.Если вы не будете выполнять много операций сортировки в секунду, это не будет иметь значения.
#include <stdio.h>
#include <stdlib.h>
static int data[10000];
#define SZDATA (sizeof (*data))
#define NMDATA (sizeof (data) / sizeof (*data))
int compfn (const void *a, const void *b) {
if (*((int*)a) > *((int*)b))
return 1;
if (*((int*)a) < *((int*)b))
return -1;
return 0;
}
int main (void) {
int i, tmp, swapped, count;
for (i = 0; i < NMDATA; i++)
data[i] = (i * 3) % 11;
if (0) {
qsort (data, NMDATA, SZDATA, compfn);
} else {
swapped = 1;
count = NMDATA;
while (swapped) {
swapped = 0;
for (i = 1; i < count; i++) {
if (data[i] < data[i-1]) {
tmp = data[i];
data[i] = data[i-1];
data[i-1] = tmp;
swapped = 1;
}
}
count --;
}
}
//for (i = 0; i < NMDATA; i++)
//printf ("%10d\n", data[i]);
return 0;
}
Изменяя размер массива data и оператора if (0), я получил следующие результаты (в миллисекундах) по пять прогонов для каждого случая:
Data size | qsort | bubble
----------+-------+-------
100 | 61 | 76
| 76 | 76
| 77 | 61
| 61 | 60
| 61 | 61 avg qsort = 67, bubble = 67
1000 | 77 | 93
| 61 | 45
| 76 | 77
| 77 | 76
| 76 | 77 avg qsort = 73, bubble = 74
| |
10000 | 92 | 414
| 77 | 413
| 61 | 413
| 76 | 405
| 61 | 421 avg qsort = 73, bubble = 413
Я подозреваю, что более быстрые пузырьковые сортировки с небольшим набором данных таковы из-за отсутствия вызовов функций.
Что нужно предпринятьот этого заключается в том, что для небольших наборов данных эффективность алгоритма часто не важна, поскольку такие вещи, как big-O, обычно актуальны по мере того, как наборы данных становятся больше.
Однако этот тест был выполнен в моя среда и ваша среда могут значительно отличаться.Я бы предложил выполнить те же измерения в вашей среде - реализовать сортировку по пузырькам и рассмотреть возможность перехода к более сложному алгоритму только в том случае, когда это станет необходимым.
По предложению комментатора я повторяюзапустил тесты, используя srand(42), а затем rand() для заполнения элементов массива.В этом случае результаты были только немного хуже для пузырьковой сортировки: 642 против 413 миллисекунд для 10000 элементов и 82 против 74 миллисекунд для 1000.
Учитывая ограничения в вопросе (небольшое количество элементов, нечастая сортировка,требование стабильности, низкая сложность пространства), я все еще предпочитаю простоту пузырьковой сортировки любому из более сложных алгоритмов.
Тем не менее, помните мой предыдущий совет: вам нужно рассчитать время в вашем собственном среда.Результаты могут быть совершенно разными.Вы можете использовать код, который я предоставил в качестве основы для этого.Серьезно, если какой-либо метод, который вы выберете, займет меньше секунды, он, вероятно, более чем подходит для ваших целей.