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