Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [C++Builder]Разновидность сортировки QuickSort


Автор: lansel 5.9.2008, 13:42
Помогите правильно переписать данный код в с++. Вообщем то я почти сделала это, но у меня возникли проблемы с памятью, не сортирует большие элементы (такие как  в рандоме) и особенно если их много напимер больше 10000.
Как правильно будет в с++: 
1)  Const M=30; s: 0..M; ??
2)  stek: Array [1..M] of Record L,R:integer

Вот сам код:
Код

Const n=101; // чем больше тем лучше!
 Type tipkey=integer; tip=Record key:tipkey; end;
 Var X:Array[0..n-1]of tip;
         z,zz:integer; // счетчики 

 Procedure QuickSt1 (Var X:Array of tip);
  Const M=30;
  Var i,j,L,R: integer; w: tip; s: 0..M; xx:tipkey;
      stek: Array [1..M] of Record L,R:integer end;
  begin s:= 1; stek[1].L:= 0; stek[1].R:= High(X);
   Repeat L:= stek[s].L; R:= stek[s].R; s:= s-1;
    Repeat i:= L; j:= R; xx:= X[(L+R) div 2].key;
     Repeat {Inc(z);} While X[i].key < xx do begin {Inc(z);} Inc(i)end;
            {Inc(z);} While xx < X[j].key do begin  {Inc(z);} Dec(j) end;
      If i < j then begin w:= X[i]; X[i]:= X[j]; X[j]:= w; Inc(i); Dec(j) end
      Else If i = j then begin Inc(i); Dec(j) end
     Until i > j;
     If i < R then begin s:= s+1; stek[s].L:= i; stek[s].R:=R end;
     R:= j
    Until L >= R
   Until s = 0
  end;

procedure TForm1.Button10Click(Sender: TObject);
 VAr i,j:integer; t:cardinal;
begin
Randomize; zz:=0; z:=0; t:=GetTickCount;
 For i:= 1 to m do
 begin For j:=0 to n-1 do X[j].key:= Random(100000000);
 QuickSt1(X)
 end;
 Memo1.text:=IntToStr(zz)+'  '+ FloatToStr(GetTickCount-t)
+'  '+ FloatToStr(n*(ln(n)/Ln(2))+n/2)
end;


                          

Автор: Mazzi 5.9.2008, 14:49
правильно будет в с++: 
1)  Const M=30; s: 0..M; ??
Код

#define M    30
int s;
typedef struct rec{int L; int R;};
rec stack[M];


2)  stek: Array [1..M] of Record L,R:integer

Добавлено через 1 минуту и 26 секунд
Все массивы в С++ начинаются с нуля!

Удачи!

Автор: lansel 5.9.2008, 14:50
Mazzi, спасибо!

Автор: lansel 9.9.2008, 13:29
а что делать с сортировкой большого размера ключей??? не сортирует же :(

Автор: Mazzi 9.9.2008, 13:49
А с малым размером сортирует?

Ты добейся на небольших размерах, затем увеличивай, найди предел после которого перестаёт сортировать и поищи причину.

Автор: lansel 9.9.2008, 14:12
сортирует не больше 10000 ключей размером не больше 1000000 :(

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)