[РЕШЕНО][VB] quicksort qbasic быстрая сортировка половиной

[p51x]

kvitaliy, знаете люди особого склада ума зачастую очень уверены, что все, что они делают, очень важно и все за этим или наблюдают, или кидаются заниматься...
Вот и тут, мало того человек сам пришел пиарить свою гиниальную идею, так не дал ни внятного описания, ни алгоритма, ... более того после того, как дал свою реализацию "единомышленнику", а после нашел ошибку - не сообщил, не исправил "что бы тот не повторил ее".

[NetSpace]

p51x, да я вроде бы въехал. надо только взяться и попробовать.

[p51x]

Раз у вас много свободного времени, сгоняете мне за обедом?..

[kvitaliy]

p51x, может и так.

[сфинкс]

вроде бы въехавший понял правильно
и рекомендую самому скопировать на эту страницу
понятые пункты

насчёт ошибки единомышленника правильнее:
я не сообщил об ошибке на сей час

зато когда переделаю на другой язык сам
наверняка сообщу
и вообще единомышленник может опубликоваться в интернете
тогда и посмотрим что скажет народ

неправильно: "нашел ошибку - не сообщил,
не исправил "что бы тот не повторил ее"

правильно: не сообщаю про ошибку никому
чтобы именно все повторили бы ту же ошибку

вообще хорошая олимпийская задача по информатике

в свете вышесказанного новая идея:
? смогут ли школьники понять только из визуализации ?
вдруг школьники придумают нечто своё

https://www.youtube.com/watch?v=TcwY8Ue0DKw

преимущество моего алгоритма:
понятная даже школьникам человеческая сортировка быстрее в 4 раза

формула была: = N*(N-1)/2
формула стала: = 4*(N/4*(N/4-1)/2+2*N/4)
причём длинная формула в общем виде включает логарифм
и массив 1'000'000 элементов сортируется в 40 раз быстрее

и в excel каждый может проверить для любого N
особенно построив без анимации визуализацию из пирамид
и то речь только об одной из возможностей самой простейшей

чтобы тема стала ещё полезнее дарю ссылку
на многие алгоритмы сортировки на многих языках
rosettacode.org/wiki/Category:Sorting_Algorithms
и там легко выйти на алгоритмы для искомых языков

напоминаю: понявший пусть повторит что понял на данной странице

[NetSpace]

так, массив в 10.000 неповторяющихся элементов, разбросанных случайным образом, сформировал. счас буду думать над сортировкой и подсчётом времени.

[kvitaliy]

Сообщение от NetSpace

а если разделю массив на 4 части, то получу времена Т1, Т2, Т3 и Т4 такие, что
Т1+Т2+Т3+Т4 будут даже меньше Т1+Т2

Допустим так, если каждый массив сортировать параллельно, а не последовательно.
Ну а дальше? Как 4 разных быстро отсортированных массива мы мгновенно превратим в один правильно отсортированный?

[NetSpace]

вот код на Delphi.

var i,j,tmp,M:Integer;
    s:array[1..N]of Integer;
    Fr,t1,t2:Int64;
    Dt:Extended;
begin
   QueryPerformanceFrequency(Fr);
   M:=10000;
   for i:=1 to M do s[i]:=a[i];
   QueryPerformanceCounter(t1);
   for i:=1 to M do
   begin
      for j:=1 to M do
      begin
         if(s[i]<s[j])then
         begin
            tmp:=s[i];
            s[i]:=s[j];
            s[j]:=tmp;
         end;
      end;
   end;
   //for i:=1 to M do Memo1.Lines.Add(IntToStr(s[i]));
   QueryPerformanceCounter(t2);
   Dt:=(t2-t1)/Fr;
   Memo1.Lines.Add(FloatToStr(Dt)+'сек.');

выдаёт 0,078 секунды.
а если раскомментировать строку //for i:=1 to M do Memo1.Lines.Add(IntToStr(s[i])); и поглядеть результат - отсортированный массив, то 15 секунд будет. вывод в окно memo долгий....
а вот если 100.000 или даже 1.000.000 элементов сколько будет сортировать - не знаю даже...

[Аватар]

   for i:=1 to M-1 do
   begin
      for j:=i+1 to M do ...

самая простая )

[NetSpace]

500.000 чисел. массив формирует за 0,0087сек.
а вот сортирует за 413сек.