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

Мое задание — создать рекурсивную функцию сортировки выбора в C ++. Он выполняется так, как и предполагалось при первом вызове в main, но выбор Selection Sort в главном меню цикла 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);
}

2

Решение

Ваш код довольно громоздкий, поэтому я не буду пытаться его реорганизовать. Вместо этого рассмотрите возможность использования этой универсальной и рекурсивной реализации сортировки выбора (использует параметры шаблона функции по умолчанию в 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 итератор (размер в вашей программе).

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

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]