挿入ソート - 空のリストを扱う

Question

私はstlとベクトルを使用して挿入ソートを実装しようとしています。私はこれまでのところ、この解決策を考え出した：

void insertionSort(vector<int> &v, int splitIndex); 

int main() { 

    //vector<int> x = {55,33,99,11,22,44}; 
    //vector<int> x = {55}; 
    //vector<int> x = {55,11}; 
    vector<int> x; 

    insertionSort(x, 0); 

    printVector(x); 

    return 0; } 

void insertionSort(vector<int> &v, int splitIndex) { 

    vector<int>::iterator right = v.begin() + splitIndex + 1; 

    if(right == v.end()) 
     return; 

    vector<int>::iterator left = v.begin() + splitIndex; 

    while(*right < *left && right != v.begin()) { 
     iter_swap(right, left); 
     right--; 
     left--; 
    } 

    insertionSort(v, splitIndex+1); } 

「右」ポインタがベクトルの範囲外を向いされますので、それは空のベクターの場合を除き、すべてのケースに取り組んでいます。

if(v.size() < 2) return; 

しかし、私はそのTIS条件は、すべての再帰呼び出しのために実行されます好きではない：私はそれが最初に条件を追加することによって固定することができます知っています。

アドバイスをしてください。ありがとう。

Answer 1

vector<int>::iterator right = v.begin() + splitIndex + 1; 

は特にVEC未定義の動作が発生することができ、この文トルは空です。 *right < *left間接参照のイテレータを比較する前に、あなたが最初にright != v.begin()ことを確認する必要があるため

このループ

while(*right < *left && right != v.begin()) { 
    iter_swap(right, left); 
    right--; 
    left--; 
} 

も未定義の動作を持つことができます。そうでなければ、イテレータ leftはベクトルのイテレータの有効範囲外になります。

私は次の関数の定義を示唆しています

#include <iostream> 
#include <vector> 
#include <iterator> 
#include <algorithm> 

void insertionSort(std::vector<int> &v, std::vector<int>::size_type i = 0) 
{ 
    if (i < v.size()) 
    { 
     auto right = std::next(v.begin(), i); 
     auto left = right; 

     for (; right != v.begin() && *right < *--left; --right) 
     { 
      std::iter_swap(right, left); 
     } 

     insertionSort(v, i + 1); 
    } 
} 


int main() 
{ 
    std::vector<int> v0; 
    std::vector<int> v1 = { 55 }; 
    std::vector<int> v2 = { 55, 11 }; 
    std::vector<int> v3 = { 55, 33, 99, 11, 22, 44 }; 

    insertionSort(v0); 

    std::cout << "v0:"; 
    for (int x : v0) std::cout << ' ' << x; 
    std::cout << std::endl; 

    insertionSort(v1); 

    std::cout << "v1:"; 
    for (int x : v1) std::cout << ' ' << x; 
    std::cout << std::endl; 

    insertionSort(v2); 

    std::cout << "v2:"; 
    for (int x : v2) std::cout << ' ' << x; 
    std::cout << std::endl; 

    insertionSort(v3); 

    std::cout << "v3:"; 
    for (int x : v3) std::cout << ' ' << x; 
    std::cout << std::endl; 

    return 0; 
} 

プログラムの出力は、 `splitIndex場合、私はあなたが簡単に確認することができますね

v0: 
v1: 55 
v2: 11 55 
v3: 11 22 33 44 55 99 

Answer 2

あなたは、元のメソッドを、配列のサイズを確認し、唯一の2より大きい場合、呼び出します起動方法を、作成しますならば何：

：

insertionSort(x); 

として実装されます一般的に

void insertionSort(vector &v){ 
    if(v.size() < 2) return; 
    insertionSort(v, 0); 
}