Какой самый быстрый способ проверки правильности функции сортировки?

Question

Используя генетический алгоритм, я нашел этот список сравнения:

compareAndSwap(x[0],x[2]);
compareAndSwap(x[3],x[4]);
compareAndSwap(x[2],x[4]);
compareAndSwap(x[0],x[3]);
compareAndSwap(x[2],x[3]);
compareAndSwap(x[1],x[3]);
compareAndSwap(x[1],x[2]);
compareAndSwap(x[0],x[1]);
compareAndSwap(x[3],x[4]);

, но мне нужно проверить его, работает ли он во всех случаях.Также количество элементов массива (в настоящее время 5) может возрасти до 100 в некоторых ситуациях.Это означало бы, что число проверяемых случаев быстро растет, например, более чем pow(2,100).

Если я приведу только отсортированный массив в худшем случае, это не проверяет наличие ошибок относительно среднего элементаx[2] сравнений.Например, 5,4,3,2,1 сортируется некоторой функцией в 1,2,3,4,5, только по

compareAndSwap(x[0],x[4]);
compareAndSwap(x[1],x[3]);

, и это, конечно, не сортирует много случаев 5-элементные массивы.

Пробовал генераторы случайных чисел для выборочных массивов, но не уверен, что это приемлемо:

      std::random_device rd;
      std::mt19937 rng(rd());
      std::uniform_real_distribution<double> dist(0,1);

      for(int k=0;k<500;k++)
      {
        std::vector<double> arraySorted;
        for(int i=0;i<5;i++)
            arraySorted.push_back(dist(rng));

      //sortNetwork(arraySorted.data());

      //if(!std::is_sorted(arraySorted.begin(),arraySorted.end())) 
            throw std::runtime_error("error");
      }

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

Что если бы это был массив из 1000 элементов?Проверяются ли они с использованием математики, ручки и бумаги в рамках некоторых теорем и известных алгоритмов или с использованием суперкомпьютеров?

Только несколько примеров для 4 элементов:

1 2 3 4   
1 2 4 3   
2 1 3 4    
2 1 4 3   
1 2 0 1                        
1 2 1 0                         
2 1 0 1
2 1 1 0
3 4 2 1                           
3 4 1 2
4 3 2 1
4 3 1 2
1 1 1 1

, кажется, имеет больше, чем pow (2, n) падежи.

Можно ли как-то трактовать сеть сортировки как проблему с графом при генерации тестовых данных?

Answer 1

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

Вот несколько примеров использования функции сортировки.

• Пустой список
• Список из одного элемента
• Список со всеми нулями
• Упорядоченный список
• Перевернутый список
• Список всехте же элементы
• Очень большой список
• Список со странными элементами (например, Unicode, отрицательные числа, перегруженные числа)

Тогда есть ошибочные данные, которые должнывернуть ошибку, а не мусор.Вывод мусора, ошибка.

• Пустой указатель
• Список пустых значений
• Список, который слишком велик (если ваша функция имеет ограничения по размеру)

И да, рандомизировать.Создайте случайные допустимые списки случайных допустимых размеров, а затем убедитесь, что результат сортировки находится в порядке.Это помогает охватить любые случаи, которые вы могли пропустить, и позволяет избежать любых неверных предположений, которые вы могли сделать.Это особенно важно при тестировании функции «черный ящик» , означающей, что тестер не знает своих внутренних функций.Каждый раз, когда вы запускаете больше случайных списков для функции, вы еще больше уменьшаете вероятность ошибки.

Обязательно выведите случайное начальное число, чтобы вы могли повторить тест в случае сбоя.

Наконец, используйте покрытие теста , чтобы убедиться, что ваши тесты затрагивают все строки и ветви кода.Код может быть сгенерирован ИИ, но вы все равно можете провести анализ покрытия, чтобы выявить пробелы в тестировании.Запуск кода beautifier над, вероятно, нечитаемым кодом, сгенерированным AI, поможет вам понять, где вам нужно больше тестов.