単一リンクリストでの選択ソートの実装

Question

Heya単体リンクリストで選択ソートアルゴリズムを実装しようとしていますが、コードに問題があると認識していますが、リンクリストには数字が含まれています6実行後の出力は7777です。どんな助けもありがとう。

template<class Type> 
void UnOrderedLinkedList<Type>::swap(nodeType<Type>* first, nodeType<Type>* second) 
{ 
    nodeType<Type>* temp; 
    temp->info = first->info; 
    first->info = second->info; 
    second->info = temp->info; 
} 

Answer 1

あなたswap関数から：

nodeType<Type>* temp; 
temp->info = first->info; 

未定義の動作のクリアケースです次に交換する

template<class Type> 
void UnOrderedLinkedList<Type>::selectionSort() 
{ 
nodeType<Type>* loc; 
nodeType<Type>* minIndex; 
nodeType<Type>* temp; 
temp = first; 
if(temp == NULL) 
    cerr<<"Cannot sort an empty list."<<endl; 
else 
    if(temp->link == NULL) 
    cerr<<"List has only one item so it is already sorted."<<endl; 
else 

while(temp != NULL) 
{ 
    minIndex = minLocation(temp, last); 
    swap(temp, minIndex); 
    temp = temp->link; 
} 
} 


template<class Type> 
nodeType<Type>* UnOrderedLinkedList<Type>::minLocation(nodeType<Type>* first, nodeType<Type>* last) 

nodeType<Type>* minIndex; 
nodeType<Type>* other; 

minIndex = first; 
other = minIndex->link; 

while(other != NULL) 
{ 
    if(minIndex->info > other->info) 
    { 
     minIndex = other; 
     other = other->link; 
    } 

    else 
    { 
     other = other->link; 
    } 

} 
    return minIndex; 
} 

！初期化を行わずに、ローカル変数、つまりポインタを宣言します。次に、UBにつながる初期化されていない変数を直接使用します。ポインタを使用しているので、プログラムがクラッシュしていないことを実際に喜んでいるはずです。

ここでは、ノードを実際にスワップしないので、ポインタやノードは必要ありません。必要なのは何であるかinfoのインスタンスであり、それを使用：

SomeType temp; 
temp = first->info; 
first->info = second->info; 
second->info = temp; 

Answer 2

@JoachimPileborgによって答えはもちろん動作しますが、あなたが単独でリンクされ、独自のメンバ関数sortを記述する必要はありませんのでご注意します選択ソートを行うためのリスト。

#include <algorithm> // min_element, iter_swap, is_sorted 
#include <cassert>  // assert 
#include <forward_list> // forward_list 
#include <functional> // less 
#include <iostream>  // cout 
#include <ios>   // boolalpha 
#include <iterator>  // distance, next 

template<class FwdIt, class Compare = std::less<>> 
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) 
{ 
    for (auto it = first; it != last; ++it) { 
     auto const selection = std::min_element(it, last, cmp); 
     std::iter_swap(selection, it); 
     assert(std::is_sorted(first, std::next(it), cmp)); 
    } 
} 

int main() 
{ 
    auto fl = std::forward_list<int> { 2, 4, 1, 0, -1, 8, 2 }; 
    std::cout << std::boolalpha << std::is_sorted(fl.begin(), fl.end()) << '\n'; 
    for (auto const& e : fl) std::cout << e << ", "; std::cout << '\n'; 
    selection_sort(fl.begin(), fl.end()); 
    std::cout << std::boolalpha << std::is_sorted(fl.begin(), fl.end()) << '\n'; 
    for (auto const& e : fl) std::cout << e << ", "; std::cout << '\n'; 
} 

Live Example：

理由はselection_sort（複雑O(N^2)有する）のgeneric versionは、標準ライブラリからの1つ、std::forward_listとして前方反復子を公開既に適合する任意単独でリンクされたリストであることです

std::forward_listも独自のメンバ関数sortを実装しています。 O(N log N)マージソートを行うこのバージョンは、公開インターフェイスだけに基づいて実装することはできません（実際には可能ですが、forward_listが保証するO(1)ストレージの代わりにO(N)余分なストレージを使用します）。