На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, JoeUser
  
> Правильный алгоритм быстрой сортировки
    Уважаемые участники форума, подскажите, пожалуйста, правильный алгоритм быстрой сортировки. Который бы работал во всех случаях, чтобы не было выходов за пределы массива.

    Ответ можете написать на любом языке, но желательно--на C++ .
      На С++? Легко :D
      ExpandedWrap disabled
        #include <algorithm>
        #include <iostream>
        #include <iterator>
        #include <vector>
        #include <forward_list>
         
        template <class ForwardIt>
         void quicksort(ForwardIt first, ForwardIt last)
         {
            if(first == last) return;
            auto pivot = *std::next(first, std::distance(first,last)/2);
            ForwardIt middle1 = std::partition(first, last,
                                 [pivot](const auto& em){ return em < pivot; });
            ForwardIt middle2 = std::partition(middle1, last,
                                 [pivot](const auto& em){ return !(pivot < em); });
            quicksort(first, middle1);
            quicksort(middle2, last);
         }
         
        int main()
        {
            std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
            std::cout << "Original vector:\n    ";
            for(int elem : v) std::cout << elem << ' ';
         
            auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});
         
            std::cout << "\nPartitioned vector:\n    ";
            std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
            std::cout << " * ";
            std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));
         
            std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
            std::cout << "\nUnsorted list:\n    ";
            for(int n : fl) std::cout << n << ' ';
            std::cout << '\n';  
         
            quicksort(std::begin(fl), std::end(fl));
            std::cout << "Sorted using quicksort:\n    ";
            for(int fi : fl) std::cout << fi << ' ';
            std::cout << '\n';
        }
      Подпись была включена в связи с окончанием срока наказания
      1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
      0 пользователей:


      Рейтинг@Mail.ru
      [ Script Execution time: 0,0618 ]   [ 14 queries used ]   [ Generated: 20.08.19, 23:40 GMT ]