Как оптимизировать случайный алгоритм сортировки?

Вот некоторая случайная программа сортировки, которую я написал на C++. Он работает очень хорошо для 10 элементов или около того. Но для 15 элементов он работает так медленно, что я не могу даже ждать достаточно, чтобы получить результат. Есть ли способ оптимизировать алгоритм случайной сортировки?Как оптимизировать случайный алгоритм сортировки?

Вот мой код:

// randomsort.h 

#ifndef RANDOMSORT_H 
#define RANDOMSORT_H 

#include <stdlib.h> 
#include <time.h> 

class RandomSort 
{ 
private: 
    template <class T> 
    static bool isOrdered(T*, int); 

public: 
    template <class T> 
    static int sort(T*, int); 

}; 

template <class T> 
bool RandomSort::isOrdered(T* arr, int size) 
{ 
    for(int i = 1; i < size; i++) 
    { 
     if(arr[i-1] > arr[i]) 
     { 
      return false; 
     } 
    } 

    return true; 
} 

template <class T> 
int RandomSort::sort(T* arr, int size) 
{ 
    int stepAmount = 0; 

    srand(time(NULL)); 

    while(!isOrdered(arr, size)) 
    { 
     int i = rand() % size; 
     int j = rand() % size; 

     std::swap(arr[i], arr[j]); 

     stepAmount++; 
    } 

    return stepAmount; 
} 

#endif // RANDOMSORT_H

И main.cpp файл

// main.cpp 

#include <iostream> 
#include "randomsort.h" 

int main() 
{ 
    int size; 

    std::cout << "Enter amount of elements to sort: "; 
    std::cin >> size; 
    std::cout << std::endl; 

    int arr[size]; 

    for(int i = 0; i < size; i++) 
    { 
     arr[i] = (rand() % (size * 10)); 
    } 

    std::cout << "Input array: " << std::endl; 

    for(int i = 0; i < size; i++) 
     std::cout << arr[i] << ' '; 

    std::cout << std::endl << std::endl; 

    int stepAmount = RandomSort::sort(arr, size); 

    std::cout << "Output array: " << std::endl; 

    for(int i = 0; i < size; i++) 
     std::cout << arr[i] << ' '; 

    std::cout << std::endl << std::endl; 

    std::cout << "Number of steps: " << stepAmount; 

    return 0; 
}

Есть предложения?

источник

2015-11-15 P. Ink

Внедрите решение, используя стандартные библиотечные алгоритмы и сравните скорость. Затем вы можете увидеть, есть ли проблема в вашем алгоритме или какой-либо другой части кода. –

Я думаю, что вся точка рандомизированного сортирования состоит в том, что требуется время O (n!). Неудивительно, что вы можете сортировать 10 элементов таким образом (10! = ~ 3,6 миллиона), но сортировка 15 элементов потребует часов на современном компьютере (15! = ~ 1,3 трлн.), А сортировка 20 элементов займет вашу жизнь (20 ! = ~ 2,4 квинтиллиона). –

Существует только один способ оптимизации случайного сортировки: ИСПОЛЬЗУЙТЕ РАЗЛИЧНЫЙ СОРТ! –

Ваш код абсолютно случайный. Поэтому он может меняться, если этого не делать. Легкое исправление было бы заменой только тогда, когда оно вам понадобится.

int i = rand() % size; 
int j = rand() % size; 

// to know which should be first 
if (i > j) 
    std::swap(i, j); 

if (arr[i] > arr[j]) 
    std::swap(arr[i], arr[j]);

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

Но я считаю, что самое главное - вы не должны ожидать хороших результатов от такого алгоритма.

источник

2015-11-15 23:13:26 peroket

Как оптимизировать случайный алгоритм сортировки?

ответ

Смежные вопросы