Запуск функции сортировки по ссылке в C++ более одного раза

Мое задание — создать функцию рекурсивной сортировки выбором на C++. Он запускается, как и предполагалось, при первом вызове в main, но выбор сортировки выбором в главном меню цикла while во второй раз приводит к некоторым странным результатам. Я не уверен, что это проблема с передачей по ссылке, статической переменной в selectionSort() или чем-то еще.

#include <iostream>
#include <array>
#include <algorithm>
#include <stdlib.h>
#include <time.h>

using namespace std;

//Function Prototypes
void selectionSort(array<int, 10> &arrayRef, size_t size); //Passes a size 10 int array by ref
void rollDice(unsigned int numRolls); //Parameter is number of times the two die should roll

int main()
{
    int usrIn;

    cout << "Welcome to Program Assignment 2!";

    while (true) //Main Menu Loop
    {
        srand(time(NULL));
        cout << "\n\n1) Selection Sort\n2)Roll Dice Simulation\n3)End The Program\nSelect an Option."
            << endl;

        cin >> usrIn;

        if (usrIn == 1)
        {
            cout << "Maximum value for array variables to be sorted: " << endl;
            cin >> usrIn; //Retrieves the user input max int value for the array's number generator
            array<int, 10> arrayToSort; //Initializes the test array of size 10

            for (int &val : arrayToSort) //Generates values for the array
                val = rand() % usrIn + 1;

            cout << "\nbefore sort:\n";
            for (int val : arrayToSort) //Displays numbers before the array is sorted
                cout << val << " ";

            selectionSort(arrayToSort, 10); //Sorts the array in numerical order

            cout << "\nafter sort:\n";
            for (int val : arrayToSort) //Displays numbers after the array is sorted
                cout << val << " ";

        }
    }


    return 0;
}

void selectionSort(array<int, 10> &arrayRef, size_t size)
{
    static int counter = 0;

    if (size <= 1)
        return;

    for (int i = counter; i < arrayRef.size(); i++)
    {
        if (arrayRef[i] < arrayRef[counter])
        {
            swap(arrayRef[i], arrayRef[counter]);
        }
    }

    counter++;
    selectionSort(arrayRef, size - 1);
}

c++ recursion static-variables pass-by-reference selection-sort
person Hunter Jones    schedule 16.09.2013    source источник
comment
Не связано, но вам нужно позвонить srand один раз.   -  person Some programmer dude    schedule 16.09.2013
comment
И это определенно может быть связано со статической переменной в функции selectionSort. Попробуйте сбросить его после сортировки.   -  person Some programmer dude    schedule 16.09.2013
comment
удалить статический и инициализировать counter с помощью этого counter = 10 - size;   -  person borisbn    schedule 16.09.2013

Ответы (1)


arrow_upward
1
arrow_downward

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

template<class ForwardIterator, class Compare = std::less<typename std::iterator_traits<ForwardIterator>::value_type>>
void selection_sort(ForwardIterator first, ForwardIterator last, Compare cmp = Compare{})
{
        if (first == last) return;
        auto const selection = std::min_element(first, last, cmp);
        std::iter_swap(selection, first);
        selection_sort(++first, last, cmp);
}

Ключевым моментом здесь является увеличение итератора first (указатель на первый элемент массива в вашей программе), а не уменьшение итератора last (размер в вашей программе).

Конечно, у этого есть хвостовая рекурсия, которую можно легко удалить с помощью внешнего цикла, возвращающего обычную итеративную реализацию.

person TemplateRex    schedule 16.09.2013