Логическая ошибка в алгоритме сортировки выбора C ++? - PullRequest
Новая
       7

Логическая ошибка в алгоритме сортировки выбора C ++?

0 голосов
/ 25 февраля 2020

Я новичок в C ++ и пытаюсь написать эту простую функцию сортировки выбора. Извиняюсь, если ответ прост более опытным программистам, но я новичок и долго смотрел на это безрезультатно. Вот мой код: 

#include <iostream>
#include <array>
using namespace std;
array<int, 10> unsorted {3, 4, 1, 5, 7, 2, 8, 9, 6, 0};

void printarray(array<int, 10> arr) {
    int count = 0;
    for (int i : arr) {
        if (count < arr.size()-1) {
            cout << i << ", ";
        } else {
            cout << i << endl;
        }
        count++;
    };
}

int selection_sort(array<int, 10> arr) {
    int test;
    array<int, 10> newarr;
    for(int j = 0; j < arr.size(); j++) {
        test = arr[j];
        for(int i = j; i < arr.size(); i++) {
            if(arr[i+1] < test) {
                test = arr[i];
            }
        }
        newarr[j] = test;
    }
    printarray(newarr);
    return 0;
}


int main() {
    selection_sort(unsorted);
    return 0;
}

Когда я запускаю эту функцию, она печатает массив int, содержащий 10 нулей. Есть ли ошибка при назначении значений для массива (в C ++) или, скорее, проблема в самом logi c?

Ответы [ 2 ]

1 голос
/ 11 марта 2020

Обе реализации неверны. Я только исправил ответ @ Adrisui3. Правильное решение: 

#include<iostream>
#include<vector>

using namespace std;

int main()
{   
    vector<int> array(5);
    int aux;

    array[0] = 10;
    array[1] = 2;
    array[2] = 45;
    array[3] = -5;
    array[4] = 0;

    for(int i = 0; i < array.size(); i++)
    {
        int min = i;
        for(int j = i+1; j < array.size(); j++)
        {
            if(array[j] < array[min])
            {
                min = j;

            }
        }

        if (i != min)
        {
            aux = array[i];
            array[i] = array[min] ;
            array[min] = aux;
        }
    }
    for(int k = 0; k < array.size(); k++)
    {
        std::cout << array[k] << std::endl;
    }

}

Ссылка: wikipidia

1 голос
/ 25 февраля 2020

Это довольно странный способ реализации Selection Sort. Насколько я понимаю, вы сделали там несколько ошибок. Во-первых, вы не можете использовать arr.size () в первом случае для l oop, так как это приведет к тому, что второй просто выйдет за пределы go, что приведет к неожиданному поведению. Если бы случайно это были обычные массивы, вы бы получили хорошую ошибку сегментации. Даже при том, что вы не получаете ошибку во время выполнения, это то, что вы должны знать. С другой стороны, основная проблема здесь связана с тем, как вы используете индексы, а также с тем, что вам действительно не нужен второй массив.

Здесь у вас есть пример этого алгоритм. 

#include<iostream>
#include<vector>

using namespace std;

int main()
{   
    vector<int> array(5);
    int aux;

    array[0]=10;
    array[1]=2;
    array[2]=45;
    array[3]=-5;
    array[4]=0;

    for(int i=0; i<array.size()-1; i++)
    {
        for(int j=i+1; j<array.size(); j++)
        {
            if(array[j]<array[i])
            {
                aux=array[j];
                array[j]=array[i];
                array[i]=aux;
            }
        }
    }
}

Кроме того, я бы рекомендовал вам использовать вектор вместо массива, оба являются контейнерами STL, но вектор намного более гибок и полезен, хотя и потребляет некоторую дополнительную память.

Надеюсь, мой ответ был достаточно ясен. Я здесь, если вам нужна дополнительная помощь. Удачи!

...