Алгоритм сортировки списка целых чисел

Question

У меня есть список из примерно 200 целых чисел, значения которых находятся в диапазоне от 1 до 5.

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

Какой самый быстрый алгоритм сортировки для этой целочисленной сортировки?

РЕДАКТИРОВАТЬ: Оказывается, так как я знаю, что числа от 1 до 5, то я могу использовать алгоритм сортировки сегментов (?)что, если я не ошибаюсь - и я определенно мог быть - означает, что для каждого целого числа значения 1 я помещаю его в группу 1, значение 2 я помещаю в группу 2 и т. д., а затем объединяю группы в конце.Это кажется простым и эффективным способом сделать это.

Однако, поскольку для меня это (в настоящее время) учебное упражнение, я собираюсь снять ограничение 1 - 5 и попытаться реализовать сортировку по пузырькам и объединить их.Сортируйте и сравните два, чтобы увидеть, что быстрее.

Спасибо за вашу помощь!

Answer 1

... мне сказали, что это ужасный способ сделать что-то.

Прежде всего, не принимайте в качестве евангелия ничего, что вы слышите от случайных тел в Интернете(даже я).

Сортировка пузырьков штраф при определенных условиях, например, когда данные уже в основном отсортированы, или количество элементов относительно мало (например, 200) ^(a) , или у вас нет встроенной в язык функциональности сортировки, и вы находитесь в сжатые сроки, когда нехватка производительности будет раздражать клиента, а отсутствие функциональности приведет к увольнению: -)

Это смещение по отношению к пузырьковой сортировке аналогично правилам «только одна точка выхода из функции» и «нет перехода».Вы должны понять причину, стоящую за ними, чтобы вы знали, когда правила могут быть безопасно проигнорированы.

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

dim count[1..5] = {0, 0, 0, 0, 0};
for each item in list:
    count[item] = count[item] + 1
for val in 1..5:
    for quant in 1..count[val]:
        output val

Это решение O (n) времени и пространства O (1), и вы не найдетеболее эффективный big-O для обобщенной процедуры сортировки - в этом случае это возможно только из-за дополнительной информации о данных, имеющейся у вас (ограничена значениями от 1 до 5).

Если вы хотите проверить всеразличные алгоритмы сортировки, страница алгоритма сортировки в Википедии является полезной отправной точкой, включая основные алгоритмы и их свойства.

---

^(a) В сторонуследующий код (использующий данные наихудшего случая для пузырьковой сортировки) при запуске под CygWin на не очень мощном ноутбуке IBM T60 (2 ГГц двухъядерный) завершается в среднем за 0,157 секунды (5 выборок: 0,150, 0,125,0,192, 0,199, 0,115).

Я бы не использовал его для сортировки миллиона предметов (все знают, что сортировка пузырьков плохо масштабируется), но в большинстве случаев 200 должно быть в порядке:

#include <stdio.h>

#define COUNT 200
int main (void) {
    int i, swapped, tmp, item[COUNT];

    // Set up worst case (reverse order) data.

    for (i = 0; i < COUNT; i++)
        item[i] = 200 - i;

    // Slightly optimised bubble sort.

    swapped = 1;
    while (swapped) {
        swapped = 0;
        for (i = 1; i < COUNT; i++) {
            if (item[i-1] > item[i]) {
                tmp = item[i-1];
                item[i-1] = item[i];
                item[i] = tmp;
                swapped = 1;
            }
        }
    }

    // for (i = 0; i < COUNT; i++)
    //     printf ("%d ", item[i]);
    // putchar ('\n');

    return 0;
}

Answer 2

Здесь вам может не потребоваться сортировка, поскольку у вас есть только 5 возможных значений. Вы можете использовать 5 контейнеров (или блоков), и, просматривая список целых чисел, вы помещаете значения в правильное поле. В конце, сложите ведра по порядку.

Answer 3

Слияние сортировка - это O (n log n) Я думаю, что это лучше, чем QuickSort

Вы можете найти код C # здесь .