quicksort списка

[SpineDuzt]

Всем доброго времени суток.
Не подскажите, как отсортировать список с помощью quicksort?
Пузырьком и перебором смог сделать, а вот быстрая сортировка не получается.
Или где можно посмотреть пример такой процедуры на паскале?
Кому интересно, вот что смог сделать:

type elem_list=string;
     pelem=^elem;
     elem=record info: elem_list;
                 next: pelem
     end;

     list3=object
     procedure sort(var b:pelem; l,r:integer);
     procedure trav(var b:pelem);
     procedure sk;
     end;

...............................

procedure list3.trav(var b:pelem); {обход списка, чтобы посмотреть кол-во элементов в нем}
var cur:pelem;
    k:integer;
begin cur:= b;
      k:=0;
      while (cur<>nil) do
      begin
        k:=k+1;
        cur:=cur^.next
      end
end;

procedure list3.sk; {процедура, чтобы поставить указатель в середину и конец списка}
var u,k,z:integer;
    cur:pelem;
    cur0,cur1:pelem;
begin
 z:=k div 2;
 for u:=1 to z do
  begin
   cur:=cur^.next;
  end;
   for u:=1 to k do
  begin
   cur1:=cur1^.next;
  end;
end;

procedure list3.sort(var b:pelem; l,r:integer); {qs}
var i,j,u,k:integer;
    cur:pelem;
    cur0,cur1,cur3:pelem;
    s:elem_list;

begin
  i:=1;
  j:=k;
  cur0:=b;
  repeat
    while cur0^.info<cur^.info do inc(i);
    while cur1^.info>cur^.info do dec(j);
    if i<=j then
    begin
      s:=cur3^.info;
      cur0^.info:=cur1^.info;
      cur1^.info:=s;
      inc(i);
      dec(j);
    end;
  until i>j;
  if l<j then list3.sort(b,l,j);
  if i<r then list3.sort(b,i,r);
end;

[RUSt88]

за исходниками и подробной теорией идем в википедию

[SpineDuzt]

Спасибо за помощь.
Сам я до этого ну никак не мог додуматься.
И вообще исходников быстрой сортировки списка на паскале в википедии нет.

[RUSt88]

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

[SpineDuzt]

В этом и вся проблема.
Я же написал, не получается у меня.
Я сделал быструю сортировку для записей-так же с помощью википедии и гугла.
Но про списки там немного инфы (в частности в пример приводится всего одна сортировка перебором) и я просто не понимаю синтаксис списка во многих местах.
Например бывало такое (звучит глупо, да), что запускаю иной раз программу все работает, а после выхода и !абсюлютно ничего не меняя! и запуска ее снова, она вылетает с экситкод=216.
И еще есть много вопросов, поэтому и попросил указать хотя бы более менее полный шаблон быстрой сортировки списка на паскале, чтобы сделать на подобии самому.
Если интересно, нам задали написать три сортировки(пузырьком, перебором и быстрая) в разных модулях и присоединить их в одну программу. Первые две я сделал еще 2 недели назад, а быстрая ну никак не получается.
Читать алгоритм и пытаться написать самому уже сил нет.

[Serge_Bliznykov]

SpineDuzt
1) где Ваши наработки?! (выкладывайте Ваш код)
2) фактически Вам нужно сделать процедуру, которая обменивает два элемента списка местами! (как она будет это делать - это Ваш выбор - либо данные переписывать из одного элемента в другой, либо изменять ссылки так, чтобы элементы в списке поменялись местами..
3) QuickSort реализация бывает рекурсивной и нерекурсивной. Вы какую пытаетесь сделать?

А вот, к слову, пример реализации сортировки через рекурсию:

// взято из JclBase.pas

procedure StringListCustomSort(StringList: TStringList; SortFunc: TStringListCustomSortCompare);

  procedure QuickSort(L, R: Integer);
  var
    I, J, P: Integer;
  begin
    repeat
      I := L;
      J := R;
      P := (L + R) shr 1;
      repeat
        while SortFunc(StringList, I, P) < 0 do
          Inc(I);
        while SortFunc(StringList, J, P) > 0 do
          Dec(J);
        if I <= J then
        begin
          StringList.Exchange(I, J);
          if P = I then
            P := J
          else
          if P = J then
            P := I;
          Inc(I);
          Dec(J);
        end;
      until I > J;
      if L < J then
        QuickSort(L, J);
      L := I;
    until I >= R;
  end;

begin
  QuickSort(0, StringList.Count - 1);
end;