Незаметная проблема стабильности быстрой сортировки

Question

Я пытаюсь создать реализацию быстрой сортировки для школьного проекта, которая сортирует файл CSV, и мне очень тяжело с ним работать. Согласно спецификации проекта, сортировка каждого столбца файла CSV по порядку приведет к тому, что нестабильная сортировка станет стабильной, а именно: «./sort --algorithm quicksort -k 1,2,3,4,5 input.csv» должен выдать те же результаты, что и "./sort --algorithm вставка -k 1,2,3,4,5 input.csv"

Чтобы сохранить предыдущие сортировки, сортировки выполняются в обратном порядке, например:

for (int current_key = config.sort_columns.size()-1; current_key >= 0; current_key--){
    sorting_algorithm(records, config, config.sort_columns[current_key]-1);
}

Где config.sort_columns - это вектор всех столбцов сортировки, указанных в аргументе -k.

Вот мой ввод:

name,breed,date of birth,date of death,avg eggs per week 
Marilyn,Isa Red,2011-04-24,N/A,6 
Brian,Derp,2010-01-15,2011-12-01,4 
Chrissy,Ent,2012-02-08,N/A,3 
Mildred,Araucana,2011-05-01,N/A,3 
Jimmy,Ent,2006-02-30,N/A,15 
Mabel,Isa Red,2011-04-26,N/A,5 
Myrtle,Araucana,2011-08-01,N/A,0 
Myrtle,Araucana,2011-05-01,2011-07-13,0 
Adam,Ent,2010-01-01,N/A,10 
Isabel,Ent,2009-04-01,N/A,2 
Jimmy,Ent,2006-02-30,2011-03-24,1 
Jimmy,Derp,2003-02-30,2010-03-24,8 
Myrtle,Herp,2011-08-01,N/A,0 

Вот вывод моей сортировки вставки (должно быть и кажется правильным):

name,breed,date of birth,date of death,avg eggs per week 
Adam,Ent,2010-01-01,N/A,10 
Brian,Derp,2010-01-15,2011-12-01,4 
Chrissy,Ent,2012-02-08,N/A,3 
Isabel,Ent,2009-04-01,N/A,2 
Jimmy,Derp,2003-02-30,2010-03-24,8 
Jimmy,Ent,2006-02-30,2011-03-24,1 
Jimmy,Ent,2006-02-30,N/A,15 
Mabel,Isa Red,2011-04-26,N/A,5 
Marilyn,Isa Red,2011-04-24,N/A,6 
Mildred,Araucana,2011-05-01,N/A,3 
Myrtle,Araucana,2011-05-01,2011-07-13,0 
Myrtle,Araucana,2011-08-01,N/A,0 
Myrtle,Herp,2011-08-01,N/A,0

А вот вывод моей быстрой сортировки:

name,breed,date of birth,date of death,avg eggs per week
Adam,Ent,2010-01-01,N/A,10
Brian,Derp,2010-01-15,2011-12-01,4
Chrissy,Ent,2012-02-08,N/A,3
Isabel,Ent,2009-04-01,N/A,2
Jimmy,Ent,2006-02-30,2011-03-24,1
Jimmy,Ent,2006-02-30,N/A,15
Jimmy,Derp,2003-02-30,2010-03-24,8
Mabel,Isa Red,2011-04-26,N/A,5
Marilyn,Isa Red,2011-04-24,N/A,6
Mildred,Araucana,2011-05-01,N/A,3
Myrtle,Herp,2011-08-01,N/A,0
Myrtle,Araucana,2011-08-01,N/A,0
Myrtle,Araucana,2011-05-01,2011-07-13,0

Как видите, это почти правильно, за исключением того, что второй столбец неверен, когда совпадает первый столбец (например, «сумасшедший» должен стоять перед обоими «энтами»).

И, наконец, вот моя реализация быстрой сортировки:

int sort_quick_partition(std::vector<Record> &records, bool (*comparison)(string, string), int sort_key, int left, int right){
    /*
    Partition the vector and return the address of the new pivot.

    @param less - Vector of elements less than pivot.
    @param greater - Vector of elements greater than pivot.
    */

    // Setup 
    int store_location;
    Record pivot = records[right];
    Record temp_record;

    // Loop through and partition the vector within the provided bounds
    store_location = left - 1;
    for (int j = left; j < right; j++){
        if (comparison(records[j].fields[sort_key],pivot.fields[sort_key])){
            store_location += 1;
            std::swap(records[store_location], records[j]);
        }
    }

    std::swap(records[store_location+1], records[right]);

    return store_location+1;
}

void sort_quick_helper(std::vector<Record> &records, bool (*comparison)(string, string), int sort_key, int left, int right){
    /*
    Actually performs the quick sort.

    @param sub_list - Vector to sort.
    @param *comparison - Comparison to perform.
    @param sort_key - Which column to sort by.
    @param left - Left side of active sort zone.
    @param right - Right side of active sort zone.
    */

    // Setup
    int new_pivot;

    // Make sure the list has 2 or more items
    if (left < right){
        // Partition the vector and get the new pivot value
        new_pivot = sort_quick_partition(records, comparison, sort_key, left, right);

        // Sort elements less than the pivot
        sort_quick_helper(records, comparison, sort_key, left, new_pivot-1);

        // Sort elements greater than the pivot
        sort_quick_helper(records, comparison, sort_key, new_pivot+1, right);
    }
}

void sort_quick(std::vector<Record> &records, Configuration &config, int sort_key){
    /*
    Perform a quick sort on the records.

    @param &records - Vector of Record structures representing the file.
    @param &config - Reference to a global configuration structure.
    @param sort_key - Which column to sort by.
    */

    // Decide if it needs to be reversed
    bool (*comparison)(string, string);
    if (config.reverse){
        comparison = &comparison_gte;
    } else {
        comparison = &comparison_lte;
    }

    // Call the sort
    sort_quick_helper(records, comparison, sort_key, 0, records.size()-1);
}

Обратите внимание, что sorting_algorithm - это указатель на функцию, которая указывает на активную сортировку, в данном случае - sort_quick.

Кто-нибудь видит, что может быть не так? Я пытался исправить это в течение нескольких дней, и в этот момент я убираю волосы. Спасибо всем!

Answer 1

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

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

Поэтому, когда вы сравниваете записи «Миртл, Араукана, 2011-08-01, N / A, 0» и «Миртл, Араукана, 2011-05-01,2011-07-13,0», вам необходимо сравнить поля в порядке, пока вы не найдете пару, которые не равны. (Это называется лексикографическим порядком.) Возможно, вам даже потребуется включить исходную позицию, если вам нужно сохранить порядок полностью равных записей.

Конечно, если бы это была не домашняя работа, вы бы, наверное, смотрели на std::stable_sort. (Последовательность стабильных сортировок в столбцах в обратном порядке будет в порядке.)

Answer 2

Что ж, ваша сортировка выглядит стабильно, поскольку вы выбрали стержень для элемента right most. Тем не менее, в конце строки.

std::swap(records[store_location+1], records[right]);

меняет местами две записи точно так же, даже когда они равны. Добавить чек для сортировки только тогда, когда они не равны:

// You'll probably use your comparison() function here.
if ( records[store_location+1].fields[sort_key] != records[right].fields[sort_key] ) {
    std::swap(records[store_location+1], records[right]);
}