1

Есть массив из пар элементов (Priority:Sec) введите сюда описание изображения

Я сортирую его, используя quicksort, по приоритетам: введите сюда описание изображения

Далее я прогоняю полученный сортированный массив снова в quicksort, но уже по SEC, планируя получить

(10:10)(100:10)(250:10)(200:11)(250:20)(100:21)(50:30)(50:31)

А получаю:

введите сюда описание изображения

Код:

// Быстрая сортика
    void quicksort(struct ProcessManager * PRMR, int first, int last, bool SEC){
        struct SimpleProcess count;
        int mid;
        int f=first, l=last;

        if (PRMR->RealCount < 2) return;

        if (SEC) mid=PRMR->Process[(f+l) / 2].SecurityLevel;
            else mid=PRMR->Process[(f+l) / 2].Priority; 

        do {
            if (SEC){
                while (PRMR->Process[f].SecurityLevel<mid) f++;
                while (PRMR->Process[l].SecurityLevel>mid) l--;
            } else {
                while (PRMR->Process[f].Priority<mid) f++;
                while (PRMR->Process[l].Priority>mid) l--;
            }
            if (f<=l) //перестановка элементов
            {
            count=PRMR->Process[f];
            PRMR->Process[f]=PRMR->Process[l];
            PRMR->Process[l]=count;
            f++;
            l--;
            }
        } while (f<l);

        if (first<l) quicksort(PRMR, first, l, SEC);
        if (f<last)  quicksort(PRMR, f, last, SEC);
    }

    // Сортировка диспетчера задач
    bool sort_procman(struct ProcessManager * PRMR){

        // Сортировка процесс менеджера
        if (PRMR->Sorted) return true;
        if (PRMR->RealCount <= 1) {PRMR->Sorted = true; return true;}

        // Сортировка по приоритету
        quicksort(PRMR, 0, PRMR->RealCount-1, false);

        // Сортировка по уровню безопасности
        quicksort(PRMR, 0, PRMR->RealCount-1, true);

        // Обновляем инфо
        PRMR->Sorted = true;
        return true;

    }   

Вопрос: Почему так получается и как получить желаемое?

P.S. Сорри, что картинками - программа выполняется под MS-DOS

6
  • Забавно, что порядок приоритетов получается обратным 7 июл 2019 в 10:51
  • 1
    Используйте другую сортировку, которая не меняет порядок элементов. Тот же mergeSort. По скорости то же самое, но порядок поступления остается неизменным 7 июл 2019 в 10:53
  • if (f<=l) //перестановка элементов а если убратьравно? Я хз как оно работает, но по логике не надо ничего менять, если они равны, так? 7 июл 2019 в 10:59
  • 2
    Почитайте разницу между устойчивыми и неустойчивыми методами сортировки. Квиксорт как раз является неустойчивым. ru.wikipedia.org/wiki/…
    – Xander
    7 июл 2019 в 11:36
  • 1
    При чём тут вообще устойчивая сортировка если у автора алгоритм просто игнорирует на втором проходе первое поле? Никакая устойчивость не полечит пару (100,20) vs (200,10)
    – Alexey Ten
    7 июл 2019 в 11:48

1 ответ 1

3

Нужна только одна сортировка с правильной функцией сравнения, в которой должно в первую очередь сравниваться главное поле, а при его равенстве - вторичное (и т.д., если полей много).

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

1
  • хз за что вас минусят, имхо - дело пишете, добавлю плюсик для баланса.
    – tym32167
    7 июл 2019 в 17:17

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.