Вставка Сортировка сортирует массив на полпути - PullRequest
Новая
       14

Вставка Сортировка сортирует массив на полпути

0 голосов
/ 21 февраля 2019

Я читаю книгу DS и Algortihms.Я увидел алгоритм с именем вставки сортировки, а затем попытался применить его в C ++.Когда я сортирую массив, первый элемент массива остается в том месте, где он был ранее, в то время как другие элементы перемещаются на свое место!Я не могу понять, что происходит.Мой код: 

#include<iostream>
#include<vector>

using namespace std;

void vec_in(vector<unsigned>& vec, unsigned size);
void vec_out(vector<unsigned> vec);

int main(){
    vector<unsigned> vec;
    unsigned size;
    cout<<"SIZE : ";
    cin>>size;
    cout<<"ARRAY : ";
    vec_in(vec,size);
    cout<<endl;
    for(unsigned j=1; j<size; j++){
        unsigned key = vec[j];
        unsigned i=j-1;
        cout<<key<<endl;
        while(i>0&&vec[i]>key){
            vec[i+1]=vec[i];
            i--;
        }
        vec[i+1]=key;
    }
    cout<<"SORTED ARRAY : ";
    vec_out(vec);

} 

void vec_in(vector<unsigned>& vec, unsigned size){
    for(unsigned i=0; i<size; i++){
        unsigned in;
        cin>>in;
        vec.push_back(in);
    }
    cout<<endl;
}
void vec_out(vector<unsigned> vec){
    for(unsigned i=0; i<vec.size(); i++){ 
        cout<<vec[i]<<" ";
    } 
    cout<<endl;
}

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

Ответы [ 2 ]

0 голосов
/ 21 февраля 2019

Предположим, у нас есть только два элемента: 4 и 3.

Теперь, что происходит, когда вводится цикл for. 

    for(unsigned j=1; j<size; j++){
        unsigned key = vec[j];         /* key := 3      */
        unsigned i=j;                  /* i := 1        */
        cout<<key<<endl;               /* print(3)      */
        while(i>0&&vec[i-1]>key){      /* i > 0 (false) */
            vec[i]=vec[i-1];
            i--;
        }
        vec[i]=key;
    }

whileЦикл, который выполняет сортировку, не вводится.Это всегда происходит, когда вы пытаетесь сравнить vec[0] с vec[1].

Как правило, сначала выполните следующие тесты: 

1) empty vector
2) vector with one element
3) vector with two elements a) sorted acending b) sorted descending
...

Они позволят вамбыстро найти незначительные ошибки.

0 голосов
/ 21 февраля 2019

Вы должны заменить while(i>0&&vec[i]>key){ на while(i>=0&&vec[i]>key){.В этом случае i может стать отрицательным.Таким образом, его нужно опалить, т. Е. этот код работает.

Если вы хотите остаться со своими типами, вы можете заменить все вхождения i на i-1 и получить

#include<iostream>
#include<vector>

using namespace std;

void vec_in(vector<unsigned>& vec, unsigned size);
void vec_out(vector<unsigned> vec);

int main(){
    vector<unsigned> vec;
    unsigned size;
    cout<<"SIZE : ";
    cin>>size;
    cout<<"ARRAY : ";
    vec_in(vec,size);
    cout<<endl;
    for(unsigned j=1; j<size; j++){
        unsigned key = vec[j];
        unsigned i=j;
        cout<<key<<endl;
        while(i>0&&vec[i-1]>key){
            vec[i]=vec[i-1];
            i--;
        }
        vec[i]=key;
    }
    cout<<"SORTED ARRAY : ";
    vec_out(vec);

} 

void vec_in(vector<unsigned>& vec, unsigned size){
    for(unsigned i=0; i<size; i++){
        unsigned in;
        cin>>in;
        vec.push_back(in);
    }
    cout<<endl;
}
void vec_out(vector<unsigned> vec){
    for(unsigned i=0; i<vec.size(); i++){ 
        cout<<vec[i]<<" ";
    } 
    cout<<endl;
}

, который также работает .

Обратите внимание, что ваш подход требует N ^ 2 шагов (где N это размер вектора).Есть гораздо лучшие подходы, которые делают это всего за log (N) N шагов, как быстрая сортировка.Стандартная библиотека реализует такой алгоритм.Таким образом, вы должны всегда использовать std::sort для сортировки.

...