C ++ Вставка сортировки путаница - PullRequest
Новая
       28

C ++ Вставка сортировки путаница

0 голосов
/ 15 июня 2019

Я пытаюсь реализовать сортировку вставками самостоятельно в C ++.Я знаю, что существует множество примеров, и я сравнил свое решение с уже существующим и не понимаю, почему мое не работает.Я знаю, что для этого есть библиотеки, но я хочу реализовать это самостоятельно.У меня есть 2 различные реализации, как показано ниже ( A - одна, которая работает, B - одна, которая не работает).

Вот A - Тот, который работает.Здесь нет ничего нового. 

    int myArr[5] = {5,4,3,2,1};

    for (int i = 1; i < 5; i++){

        int j = i - 1;
        int key = myArr[i];

        while(myArr[j] > key && j >= 0){
            myArr[j + 1] = myArr[j];
            j = j - 1;
        }        
        myArr[j + 1] = key;

        //Printing array to see what changed:
        for (size_t k = 0; k < 5; ++k){
            cout << myArr[k] << " ";
        }
        cout << endl;
   }

Пример вывода из A : 

    4 5 3 2 1 
    3 4 5 2 1 
    2 3 4 5 1 
    1 2 3 4 5

Вот B , что я придумал. B очень похож на A , за исключением строк, которые я указал, где я решил использовать индекс myArr вместо ключа: 

    int myArr[5] = {5,4,3,2,1};

    for (int i = 1; i < 5; i++){

        int j = i - 1;
        //int key = myArr[i]; //DIFFERENT FROM **A**


        //************** DIFFERENT FROM A **************
        //I didn't use "key", instead I chose to use myArr[i]
        while(myArr[j] > myArr[i] && j >= 0){
            myArr[j + 1] = myArr[j];
            j = j - 1;
        }

        //************** DIFFERENT FROM A **************
        //Same here: I use myArr[i] instead of key        
        myArr[j + 1] = myArr[i];

        //Printing array to see what changed:
        for (size_t k = 0; k < 5; ++k){
            cout << myArr[k] << " ";
        }
        cout << endl;
   }

Пример выводас B : 

    5 5 3 2 1 
    5 5 5 2 1 
    5 5 5 5 1 
    5 5 5 5 5

Не понимаю, единственное, что я изменил, - это не сохранение текущего значения в переменной.Я знаю, что могу легко это сделать, и все будет хорошо, но меня беспокоит то, что я не знаю, почему B неверно.Любое руководство будет оценено.

Ответы [ 2 ]

1 голос
/ 15 июня 2019

Это хорошее упражнение для прохождения кода вручную. Что изменилось? key - это временное хранилище для значения в myArr[i]. Проблема с, казалось бы, безобидным рефакторингом состоит в том, что myArr[j + 1] равно myArr[i] на первой итерации внутреннего цикла. Примечание: 

int j = i - 1;
...
myArr[j + 1] = myArr[j]; // j + 1 === i

что по сути: 

myArr[i] = myArr[j]; // whoops!

Здесь мы переназначили myArr[i] на что-то другое вместо копирования и сохранения значения в key. Мы теряем один элемент на каждой итерации внешнего цикла всякий раз, когда элемент myArr[i] еще не отсортирован.

Сохранить переменную key!

0 голосов
/ 15 июня 2019

Я буду использовать i = 1, чтобы показать, почему он работает не так, как вы ожидаете. 

int j = i - 1;

j становится 0. 

myArr[j + 1] = myArr[j];

Здесь myArr [1] назначено значение myArr [0]. Вот в чем проблема, как 

myArr[j + 1] = myArr[i];

присваивает myArr [1] значение myArr [0] (изменено в ранее упомянутой строке).

Короче говоря, сдвиг стирает значение для вставки. Вот почему вам нужно скопировать его в другую переменную (введите код A).

...