微妙的快速排序穩定性問題

Question

我正在嘗試爲排序CSV文件的學校項目創建一個快速排序實現，並且我很難與它一起工作。根據項目規範，按順序對CSV文件的每一列進行排序將強制不穩定排序變得穩定，即：「./sort --algorithm quicksort -k 1,2,3,4,5 input.csv」應該產生與「./sort - 算法插入-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 

正如您所看到的，這幾乎是正確的，只是當第一列墊子ches（例如「Derp」應該出現在「Ents」之前）。

最後，這裏是我的快速排序實現：

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

這是不正確的，你可以通過重複排序來穩定地排除不穩定因素。考慮最後的排序：當它看到相同的鍵時，不保證保留先前的排序（這就是不穩定的意思）。

相反，您需要做的是按照明確命令輸入的鍵排序 - 因此您需要進行一種排序，其中排序的鍵是所有列而不是單個列。

因此，當您比較記錄「Myrtle，Araucana，2011-08-01，N/A，0」和「Myrtle，Araucana，2011-05-01,2011-07-13,0」時，您需要按順序比較字段，直到找到不相等的對。 （這就是所謂的詞典排序。）如果您需要保留完全相同的記錄順序，您甚至可能需要合併原始位置。

當然，如果這不是家庭作業，你可能會看std::stable_sort。 （以相反順序在列上進行穩定排序的順序應該沒問題。）

Answer 2

那麼，您的排序看起來很穩定，因爲您已選擇樞軸爲right的大部分元素。但是，最後的線。

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