Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Для новичков > Алгоритм быстрой сортировки списка

Автор: Randomazer 24.12.2012, 17:08

Подскажите пожалуйста, если у кого есть, алгоритм или пример быстрой сортировки списка. В списке содержатся символы. Спасибо

Автор: Illusion Dolphin 24.12.2012, 17:13

Сейчас можно так:

Код


uses
   Generics.Collections;

var
  PersonsList : TList<TPerson>;

  PersonsList.Sort(TComparer<TPerson>.Construct(
      function(const Item1,Item2:TPerson): Integer
      begin
         Result := 
          CompareText(Item1.LastName, Item2.LastName);
      end));

Автор: Randomazer 24.12.2012, 17:21

Извините, мне для Free Pascal Compiler
Дан массив из 20 символов, перевести их в список и отсортировать быстрой сортировкой
Нашел вот это, но не могу найти как применить к своему случаю http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D0%B8%D1%81%D0%BA%D0%B0

Автор: Illusion Dolphin 24.12.2012, 22:06

Ну тогда читаем про двусвязные и односвязные списки:
http://delphisite.ru/faq/realizatsiya-odnosvyaznogo-i-dvusvyaznogo-spiskov
и затем под них преобразуем алгоритм быстрой сортировки:

Код


 procedure QuickSort(var A: array of Integer);
  var
    Lo, Hi, Mid, T: Integer;
  begin
    Lo := Low(A);
    Hi := High(A);
    Mid := A[(Lo + Hi) div 2];
    repeat
      while A[Lo] < Mid do Inc(Lo);
      while A[Hi] > Mid do Dec(Hi);
      if Lo <= Hi then
      begin
        T := A[Lo];
        A[Lo] := A[Hi];
        A[Hi] := T;
        Inc(Lo);
        Dec(Hi);
      end;
    until Lo > Hi;
    if Hi > Low(A) then QuickSort(A);
    if Lo < High(A) then QuickSort(A);
  end;

Автор: Randomazer 24.12.2012, 23:20

Спасибо большое за пример, вот только как раз и загвоздка, что я с ними разобраться не могу. Пример постараюсь переделать, спасибо

Автор: yalex 25.12.2012, 19:55

http://www.programmersforum.ru/showthread.php?t=106030

Код


procedure QuickSort(l:integer;r:integer);
var
  i,j:integer;
  X:Plist;
begin
   writeln;
   i:=l;
   j:=r;
   x:=GetByid((l+r) div 2);
   repeat
      while (GetById(i)^.sym<x^.sym) do inc(i);
      while (GetById(j)^.sym>x^.sym) do dec(j);
      if (i<=j) then
      begin
        Swap(i,j);
        inc(i);
        dec(j);
      end;
   until (i>j);
   if j>l then QuickSort(l,j);
   if r>i then QuickSort(i,r);
end;