Случайная (рандомная) сортировка элементов

Если требуется отсортировать какой либо список, массив или еще что в случайном порядке, можно применить один из нескольких незамысловатых алгоритма. Суть их проста - разбросать элементы в максимально случайном порядке и без повторений.

Рассмотрим реализацию в Qt/C++. Впрочем, ровно тоже самое работает и на чистом C++, только "qsrand()" и "qrand()" меняется на "srand()" и "rand()" соответственно.

Для того, что бы при каждом запуске получались псевдослучайные числа, существует метод: qsrand( unsigned int seed );

Но если передать ему одно и то же число, то при вызове генератора последовательность чисел будет одна и та же. Для создания эффекта псевдо-случайности достаточно при каждом вызове передавать некоторое случайное число. Как же его получить? Для не сильно требовательной случайности достаточно передать генератору текущее время (например в миллисекундах).

На примере с Qt выглядит это так: qsrand( QTime::currentTime().msec() );
Что бы получить собственно само случайное число используется метод qrand();
Он выведет любое число во всем диапазоне int. Ограничить до максимального числа можно путем деление с остатком (%).

Получение 12 случайных чисел выглядит так: qrand() % 12;

Перейдем к основной теме.

Имеем:
Целочисленный динамическй массив с размерностью нашего сортируемого списка:
int *array = new int[countAll];
А при каждом запуске метода сортировки создаем новую последовательность случайных чисел:
qsrand(QTime::currentTime().msec());

Способ №1

    for (int i = 0; i < countAll; i++) {
        array[i] = i;
    }

    for (int i = 0; i < countAll; i++) {
        int j = qrand() % (countAll); //Рандомим число
        int str = array[i]; //Запоминаем вопрос
        array[i] = array[j]; //Замена вопросов
        array[j] = str; //Замена вопросов
    }


    for (int i = 0; i < countAll; i++) {
        ui->list2->addItem(ui->list1->item(array[i])->text());
    }

Способ №2

  
    int j = 0;
    for (int i = 0; i < countAll; i++) {
        array[i] = i;
    }
    for (int i = 0; i < countAll; i++) {
        j = qrand() % (countAll - i);
        ui->list2->addItem(ui->list1->item(array[j])->text());
        array[j] = array[countAll - i - 1];
    }

И первый и второй способ одинаково подходят для обычной случайной сортировки списков или массивов.

Скачать: Демо проект на Qt/C++ случайной сортировки