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

[kvitaliy]

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

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

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

M:=10000; for i:=1 to M do s[i]:=a[i];

Разве тут случайные элементы в массиве?

Когда я тестировал сортировщик eduard-fe
Проц 3.30 GHz. Сортировался файл с 10 000 000 значений типа Int время = 0.819000 сек. Это скорость сортировщика в Винде stable_sort.
Прошу заметить, что это были числа во всём диапазоне: 4 байта и диапазон [-2 147 483 648, +2 147 483 647]

Вот когда ТС сфинкс сможет отсортировать своим алгоритмом файл в 10 000 000 элементов чисел из диапазона -2 147 483 648 до +2 147 483 647 за время 0,8 секунды, вот тогда и вернёмся к этому вопросу.
А картинки любой рисовать может.

[сфинкс]

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

и не обсуждая ничьи разработки просто повторяю:

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

быстрее в 4 раза ускоряемых сортировок
и то лишь простейшая возможность

и ничуть не мешаю разбирающемуся самостоятельно

ссылка на многие алгоритмы сортировки на многих языках
rosettacode.org/wiki/Category:Sorting_Algorithms
и там легко выйти на алгоритмы для искомых языков

вообще хорошая олимпийская задача по информатике
? смогут ли школьники понять только из визуализации ?
вдруг школьники придумают нечто своё

главное не мешать умнеть

[NetSpace]

хорошо-хорошо. я вчера только начал. на сортировке в миллион элементов программа перестала отвечать. сегодня возьмусь, при возможности, за неё снова.
а вообще, почему бы и в самом деле не расширить диапазон - [-2 147 483 648, +2 147 483 647]? надо будет для чистоты эксперимента такой взять. пущай мой ноут погудит....

[Аватар]

NetSpace

И чего на самой медленном алгоритме эксперименты ставить? Вот кусочек кода для быстрой сортировки без рекурсии, короткие интервалы <26 сортируются вставкой. На AMD 2.7 Ghz 10000000 - 1.3 сек, 100000000 - 15 сек. Экспериментируй и улучшай ) Можно в несколько потоков сделать ) Заодно и с 255-ым днем ))

type PItem = ^TItem;
     TItem = record
       IndBeg: Integer;
       IndEnd: Integer;
       Next: PItem;
     end;
var m: array of Integer;
    Stack: PItem;

procedure Push(IndBeg,IndEnd: Integer);
var p: PItem;
begin
  New(p);
  p^.IndBeg:=IndBeg;
  p^.IndEnd:=IndEnd;
  p^.Next:=Stack;
  Stack:=p;
end;

procedure Pop(var IndBeg,IndEnd: Integer);
var p: PItem;
begin
  IndBeg:=Stack^.IndBeg;
  IndEnd:=Stack^.IndEnd;
  p:=Stack.Next;
  Dispose(Stack);
  Stack:=p;
end;

procedure Init1(Count: Integer);
var i: Integer;
begin
  SetLength(m,Count);
  for i:=0 to Count-1 do m[i]:=Random(2147483647)-1073741823;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  Randomize;
end;

procedure TForm1.Button1Click(Sender: TObject);
var xIndBeg,xIndEnd,i,j,v,z: Integer;
    c: Cardinal;
begin
  Init1(10000000);

  c:=GetTickCount;

  Stack:=nil;
  Push(Low(m),High(m));
  repeat
    Pop(xIndBeg,xIndEnd);
    if xIndEnd-xIndBeg>24 then begin
      //медиана, тут можно улучшать 
      i:=(xIndEnd-xIndBeg) div 2;
      if m[xIndBeg]>m[xIndEnd] then begin
        if m[i]<m[xIndEnd] then i:=xIndEnd
        else if m[i]>m[xIndBeg] then i:=xIndBeg;
      end
      else begin
        if m[i]<m[xIndBeg] then i:=xIndBeg
        else if m[i]>m[xIndEnd] then i:=xIndEnd;
      end;
      v:=m[xIndEnd];
      m[xIndEnd]:=m[i];
      m[i]:=v;
      //быстрая сортировка
      i:=xIndBeg-1;
      j:=xIndEnd;
      z:=m[xIndEnd];
      repeat
        repeat
          dec(j);
        until (m[j]<=z) or (j=i+1);
        repeat
          inc(i);
        until (m[i]>=z) or (i=j-1);
        v:=m[i];
        m[i]:=m[j];
        m[j]:=v;
      until i>=j;
      m[j]:=m[i];
      m[i]:=m[xIndEnd];
      m[xIndEnd]:=v;
      if i>xIndBeg+1 then Push(xIndBeg,i-1);
      if i<xIndEnd-1 then Push(i+1,xIndEnd);
    end
    else begin
      //сортировка вставками
      for j:=xIndBeg+1 to xIndEnd do begin
        z:=m[j];
        i:=j-1;
        while (i>=xIndBeg) and (m[i]>z) do begin
          m[i+1]:=m[i];
          Dec(i);
        end;
        m[i+1]:=z;
      end;
    end;
  until Stack=nil;

  Memo1.Lines.Add(IntToStr(GetTickCount-c));
end;

[сфинкс]

пока все вспоминают главную идею:

Русская Сортировка Половинами =
= Человеческая Быстрая Сортировка



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



и каждый может дополнить программу новейшими алгоритмами

[NetSpace]

ну, вчера добился, что у меня программа 1.000.000 элементов сортирует за 93 секунды, но не делением пополам, а другим образом. это мало или много?
сверху два товарища дали пищу для раздумий - буду пробовать.

[Аватар]

пока все вспоминают главную идею:

Русская Сортировка Половинами =
= Человеческая Быстрая Сортировка

А кому на компьютере нужна человеческая сортировка? Нужна только быстрая.

МЫ

Это кто?

ЗЫ

Арифметические операции в столбик =
= Человеческие Быстрые Арифметические Операции

[сфинкс]

НЕправильно заданный вопрос:
"А кому на компьютере нужна человеческая сортировка?"

случайно ну конечно же случайно стёрта главная идея
посему повторяю:

Русская Сортировка Половинами =
= Человеческая Быстрая Сортировка

значит вопрос должен звучать:
"А кому на компьютере нужна сортировка человеческая БЫСТРАЯ ?"

и сейчас все видим: вопрос содержит ответ

и удалив реально лишние слова получаем:
"кому ... нужна сортировка человеческая БЫСТРАЯ ?"

ответ очевиден
и ещё см. выше исходники многих алгоритмов

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

бывших медленных алгоритмов сортировки
кои ускорила Русская Сортировка Половинами
в своей простейшей реализации без рекурсии

[p51x]

Так выше уже разместили...

[Аватар]

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

А что в этом интересного? Ну добавлю в код счетчики, скорость упадет, может в несколько раз. Главное скорость. Другое дело тест на разных данных, особенно на вырожденных случаях или приближающихся к ним. Еще интересно - адаптация к архитектуре

100ооо шт. за 70 секунд

100, допустим с тремя нулями, за 70 сек? Это и даром никому не нужно, хоть Человеческая, хоть Быстрая)