Уважаемые коллеги, какие алгоритмы сортировки массива большой длины (до 10000 элементов) посоветуете?
Есть алгоритм быстрой сортировки, но он не всегда работает правильно.

Здравствуйте, RussianFellow, Вы писали:

RF>Уважаемые коллеги, какие алгоритмы сортировки массива большой длины (до 10000 элементов) посоветуете?
А тебе что надо получить в итоге? Данные тоже разные бывают.
RF>Есть алгоритм быстрой сортировки, но он не всегда работает правильно.
Что значит "не всегда работает правильно"? Алгоритм либо сортирует, либо не сортирует на каких-то данных, а значит это неправильный алгоритм или неправильное его конфигурирование.

Здравствуйте, RussianFellow, Вы писали:

RF>Уважаемые коллеги, какие алгоритмы сортировки массива большой длины (до 10000 элементов) посоветуете?

Любой, который с поддержкой многоядерных возможностей процессора, в GNU STL это __gnu_parallel::sort, например.
То есть, тут важен не столько сам алгоритм, сколько его реализация с задействованием всех возможностей железа.
То есть, самое главное в софте-это железо, на котором он исполняется.

Здравствуйте, Kernan, Вы писали:

K>Здравствуйте, RussianFellow, Вы писали:

RF>>Уважаемые коллеги, какие алгоритмы сортировки массива большой длины (до 10000 элементов) посоветуете?
K>А тебе что надо получить в итоге? Данные тоже разные бывают.

Отсортированный по возрастанию или убыванию массив из вещественных чисел.

Здравствуйте, RussianFellow, Вы писали:

Я так и не осилил самостоятельно написать алгоритм быстрой сортировки, пользуюсь простым алгоритмом перебора: два вложенных цикла, первый I от 1 до N-1, второй J от I+1 до N, во втором цикле находится наименьшее число и оно меняется с числом, находящимся под индексом I. Такой алгоритм не самый быстрый, но у меня никогда не возникало задач, для который скорость была бы критичной. Если у вас массив из 10 тысяч чисел, сортировка этим алгоритмом займёт миллисекунду времени, можно не переживать.

Здравствуйте, RussianFellow, Вы писали:

RF>Уважаемые коллеги, какие алгоритмы сортировки массива большой длины (до 10000 элементов) посоветуете?
RF>Есть алгоритм быстрой сортировки, но он не всегда работает правильно.
Он всегда работает если реализован правильно.

для больших merge-sort но 10000 это не большая длинна.
https://en.wikipedia.org/wiki/External_sorting

Здравствуйте, Khimik, Вы писали:


K>Я так и не осилил самостоятельно написать алгоритм быстрой сортировки, пользуюсь простым алгоритмом перебора.

Чем это лучше алгоритма qsort с рекурсией?

Здравствуйте, RussianFellow, Вы писали:

RF>Уважаемые коллеги, какие алгоритмы сортировки массива большой длины (до 10000 элементов) посоветуете?
RF>Есть алгоритм быстрой сортировки, но он не всегда работает правильно.

Если бы был массив длины, которая не входит в память, тогда имело бы смысл сортировать по частям, затем сливать.
А так — используй любую стандартную для твоей среды программирования. Отработает так, что и не заметишь.

Здравствуйте, smeeld, Вы писали:

S>Здравствуйте, Khimik, Вы писали:


K>>Я так и не осилил самостоятельно написать алгоритм быстрой сортировки, пользуюсь простым алгоритмом перебора.

S>Чем это лучше алгоритма qsort с рекурсией?

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

Здравствуйте, Khimik, Вы писали:


K>Может быть, ничем, разве что тем, что не приходится использовать сторонний код, который вдруг как-то не так заработает на специфической задаче.

Какой стороний? Имелось ввиду своя реализация qsort в рекурсивной форме, а не методом разбиения на два цикла, о чём там у Вас выше говорилось.

Здравствуйте, smeeld, Вы писали:


S>Какой стороний? Имелось ввиду своя реализация qsort в рекурсивной форме, а не методом разбиения на два цикла, о чём там у Вас выше говорилось.

Я и говорю — свою реализацию qsort я не осилил. Мне надо, чтобы кто-то понятно объяснил на пальцах, как работает эта сортировка. А по книгам часто трудно понять что-то сложное.

Здравствуйте, Khimik, Вы писали:

K>Здравствуйте, RussianFellow, Вы писали:

K>Я так и не осилил самостоятельно написать алгоритм быстрой сортировки, пользуюсь простым алгоритмом перебора: два вложенных цикла, первый I от 1 до N-1, второй J от I+1 до N, во втором цикле находится наименьшее число и оно меняется с числом, находящимся под индексом I. Такой алгоритм не самый быстрый, но у меня никогда не возникало задач, для который скорость была бы критичной. Если у вас массив из 10 тысяч чисел, сортировка этим алгоритмом займёт миллисекунду времени, можно не переживать.

Спасибо, у меня сортировка работает нормально!

Здравствуйте, Khimik, Вы писали:

K>Может быть, ничем, разве что тем, что не приходится использовать сторонний код, который вдруг как-то не так заработает на специфической задаче.

Совершенно верно.

Здравствуйте, Khimik, Вы писали:

K>Я и говорю — свою реализацию qsort я не осилил. Мне надо, чтобы кто-то понятно объяснил на пальцах, как работает эта сортировка. А по книгам часто трудно понять что-то сложное.

А, понятно, но там просто всё, ниже самый простой вариант, работает чуть медленнее чем std::sort (в последнем не совсем qsort, a HeapSort, в котором на малых интервалах, если размер частичного отрезка меньше некоторого лимита, quick sort заменяется на heap_sort), но зато быстрее чем qsort их glibc.

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

#define likely(X) __builtin_expect( !!(X), 1)

template<typename Pos, typename  Cmp> 
  
  void srt(Pos pt, Pos pm, Cmp cmp){
  
   Pos tmp=pt, md=pt, sp;
   
   do{
       if(likely(md==pm))  return;
         sp=pm;
          while(sp!=tmp){
          if(cmp(*tmp, *md)){ ++tmp; continue; }; 
              
          while(--sp!=tmp){   
          if(cmp(*md, *sp)) continue;
          std::swap(*tmp, *sp);
         ++tmp; break;
         }
       }
     ++md;
    }while(tmp==pt);
      srt(pt, tmp, cmp);
      srt(tmp, pm, cmp);
 }

template<typename Pos> 
  
  void srt(Pos pt, Pos pm){
  
   Pos tmp=pt, md=pt, sp;
   
   do{
       if(likely(md==pm))  return;
         sp=pm;       
         while(sp!=tmp){
          if(cmp(*tmp, *md)){ ++tmp; continue; }; 
              
          while(--sp!=tmp){   
          
          if(cmp(*md, *sp)) continue;
          std::swap(*tmp, *sp);
         ++tmp; break;
         }
       }
     ++md;
    }while(tmp==pt);
 srt(pt, tmp);
 srt(tmp, pm);
}


int main(int a , char** s){

 std::vector<int> v;
 v.reserve(std::stoi(s[1]));
 std::generate_n(std::back_inserter<std::vector<int> >(v), std::stoi(s[1]), [](){ return random(); });

srt(v.begin(), v.end(), [](int a, int b){ return a< b; });
 std::copy(v.begin(), v.begin()+std::stoi(s[2]), std::ostream_iterator<int>(std::cout, "\n"));
}

Здравствуйте, Khimik, Вы писали:

K>Я так и не осилил самостоятельно написать алгоритм быстрой сортировки,
Да ладно?

K> пользуюсь простым алгоритмом перебора: два вложенных цикла, первый I от 1 до N-1, второй J от I+1 до N, во втором цикле находится наименьшее число и оно меняется с числом, находящимся под индексом I.
Не метод пузырька ли? Как-то ты его странно описал.

Здравствуйте, RussianFellow, Вы писали:

RF>Уважаемые коллеги, какие алгоритмы сортировки массива большой длины (до 10000 элементов) посоветуете?
RF>Есть алгоритм быстрой сортировки, но он не всегда работает правильно.

Ты че, к собеседованиям не готовился ни когда? Офигеть.

Здравствуйте, Khimik, Вы писали:

K>Может быть, ничем, разве что тем, что не приходится использовать сторонний код, который вдруг как-то не так заработает на специфической задаче.

Я пока встречал ровно одну специфическую задачу: сортировать фамилии в алфавитном порядке на украинском языке. Некоторые буквы украинского языка занимали в таблице неправильные места. И то, это было довольно давно.

Здравствуйте, smeeld, Вы писали:

S>Здравствуйте, Khimik, Вы писали:

K>>Я и говорю — свою реализацию qsort я не осилил. Мне надо, чтобы кто-то понятно объяснил на пальцах, как работает эта сортировка. А по книгам часто трудно понять что-то сложное.

S>А, понятно, но там просто всё, ниже самый простой вариант, работает чуть медленнее чем std::sort (в последнем не совсем qsort, a HeapSort, в котором на малых интервалах, если размер частичного отрезка меньше некоторого лимита, quick sort заменяется на heap_sort), но зато быстрее чем qsort их glibc.

Я, как и ТС, не профи, знаю только Delphi, но мне хотелось бы понять принцип qsort. Из Вики я вроде понял следующее:
Процедура сортировки имеет на входе границы, в которых обрабатывается массив (изначально от 1 до N). Находим среднее число M в массиве (для этого запускается один цикл), далее делим массив на две части – меньшие и большие (либо равные) M. Если я правильно понимаю, для этого удобно держать временный массив Z такой же длины, как и сортируемый, и прогнать два цикла – сначала помещать в Z числа, меньшие M, а потом числа, большие либо равные M. Далее надо запустить четвёртый цикл – заменить исходный массив на Z. Запомнить границы двух подмассивов: от 1 до V от V+1 до N. И далее дважды вызвать рекурсивно эту же процедуру, первую с границами от 1 до V, вторую с границами от V+1 до N. Если рекурсивная функция видит, что ей предлагают отсортировать только одно число – сразу выйти.

Здравствуйте, RussianFellow, Вы писали:

RF>Здравствуйте, Khimik, Вы писали:

K>>Может быть, ничем, разве что тем, что не приходится использовать сторонний код, который вдруг как-то не так заработает на специфической задаче.

RF>Совершенно верно.
Это совершенно неверно!

Здравствуйте, RussianFellow, Вы писали:

RF>Отсортированный по возрастанию или убыванию массив из вещественных чисел.
Тогда просто бери quick sort и используй его. 10.000 элементов это ни о чём, но на этом массиве уже проявляются проблемы выч. сложности поэтому пузырьковая сортировка которую предложил Химик будет не оптимальна, хотя, если твои данные плохо перемешаны или частично уложены в массив в обратном порядке, то qsort будет не так эффективен. В любом случае, qsort лучше чем bubble sort.