Seřazení struktury pomocí QuickSort – Delphi – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Seřazení struktury pomocí QuickSort – Delphi – Fórum – Programujte.comSeřazení struktury pomocí QuickSort – Delphi – Fórum – Programujte.com

 

Navara0
Newbie
29. 9. 2018   #1
-
0
-

Zdravím,

mám problém se seřazením struktury pomocí quicksort (podle abecedy). Je definována následující struktura:

type
  TZastavka = record
    IndexZast: SmallInt;
    IndexBodu: SmallInt;
    CisloOIS: SmallInt;
    Nazev10: String[10];
    NazevPanel: ShortString;
    //atd...
  end;

var
  ArrZastavky: Array of TZastavka;

a pomocí následující procedury se jí pokouším seřadit, mělo by se jednat o quicksort způsob:

procedure TStrukturyZast.ZamenitZastavky(const AIdx1, AIdx2: Integer);
var
  Tmp: TZastavka;
begin
  Tmp := ArrZastavky[AIdx1];
  ArrZastavky[AIdx1] := ArrZastavky[AIdx2];
  ArrZastavky[AIdx2] := Tmp;
end;

procedure TStrukturyZast.SeraditZastavkyQuickSort(const AStart, AEnd: Integer);
var
  Left: Integer;
  Pivot: string;
  Right: Integer;
begin
  if AStart >= AEnd then Exit;

  Pivot := ArrZastavky[AStart].NazevPanel;
  Left := AStart + 1;
  Right := AEnd;
  while Left < Right do
    begin
      if ArrZastavky[Left].NazevPanel < Pivot 
      (* nebo pro správné řazení českých znaků použito
       if AnsiCompareStr(ArrZastavky[Left].NazevPanel, Pivot) = -1 //
       výsledek je ale též chybný *)
      then
        Inc(Left)
      else
        begin
          ZamenitZastavky(Left, Right);
          Dec(Right);
        end;
    end;
  Dec(Left);
  ZamenitZastavky(Left, AStart);
  Dec(Left);
  SeraditZastavkyQuickSort(AStart, Left);
  SeraditZastavkyQuickSort(Right, AEnd);
end;

výsledek však vypadá podivně, na prvních cca 50ti položkách vypadá funkčně, některé položky původně na konci se dostanou na začátek - tam kam patří, ovšem na některých místech je ve výsledku větší "rozsypání" než bylo před seřazením (stejné názvy byly před seřazením u sebe), viz výsledek vypsaný v tabulce:

Připojen obrázek.

Netušíte prosím kde je chyba? Zdroják QuickSortu jsem vyšašil někde na netu, upravil jsem si ho pro použití na této struktuře. Porovnával jsem ho s různými nalezenými zápisy, nenacházím žádnou syntaktickou odlišnost...

Díky, N.

Nahlásit jako SPAM
IP: 37.48.7.–
Navara0
Newbie
30. 9. 2018   #2
-
0
-

Tak nakonec se povedlo vyřešit, zápis  

procedure TStrukturyZast.SeraditZastQuickSort_NazevPanel(iLo, iHi: Integer);
var
  Lo, Hi: Integer;
  T: TZastavka;
  Pivot: ShortString;
begin
  Lo := iLo;
  Hi := iHi;
  Pivot := ArrZastavky[(Lo + Hi) div 2].NazevPanel;
  repeat
    while AnsiCompareStr(ArrZastavky[Lo].NazevPanel, Pivot) = -1 do Inc(Lo);
    while AnsiCompareStr(ArrZastavky[Hi].NazevPanel, Pivot) = 1 do Dec(Hi);
    if Lo <= Hi then
    begin
      T := ArrZastavky[Lo];
      ArrZastavky[Lo] := ArrZastavky[Hi];
      ArrZastavky[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;
  if Hi > iLo then SeraditZastQuickSort_NazevPanel(iLo, Hi);
  if Lo < iHi then SeraditZastQuickSort_NazevPanel(Lo, iHi);
end;

funguje krásně. Problém ale nastane, pokud procedura dostane pole jako parametr

procedure TStrukturyZast.SeraditZastQuickSort_NazevPanel(ArrZ: array of TZastavka; iLo, iHi: Integer);

a má pracovat s různými poli podle dodaného parametu. Vynadá mi hláškou Stack Overflow. Netuší někdo proč?

Nahlásit jako SPAM
IP: 37.48.7.–
KIIV
~ Moderátor
+43
God of flame
30. 9. 2018   #3
-
0
-

#2 Navara
Nejspise predavas pole hodnotou, takze po par iteracich (a hromadach kopii toho pole), stack opravdu dojde. Je obvykle jen par MB velky. Krom toho, i kdyby bylo pole dost male, aby to nepreteklo, tak se porad meni vzdy konkretni kopie.

Proste doporucuju predavat pole jako referenci (snad uz si nekdy videl klicove slovo var u parametru)

Nahlásit jako SPAM
IP: 89.24.63.–
Program vždy dělá to co naprogramujete, ne to co chcete...
MilanL+1
Expert
1. 10. 2018   #4
-
0
-

#2 Navara
pokud chceš mít pole jako parametr a pracovat s ním přímo musíš argument funkce deklarovat jako var tzn:

 

procedure TStrukturyZast.SeraditZastQuickSort_NazevPanel(var ArrZ: array of TZastavka; iLo, iHi: Integer);

já teď řeším, něco podobného při řazení trošku složitější struktury , kde nejde přímo zaměňovat struktury, tak jsem to vyřešil pomocí takové kulišárny, udělal jsem si pomocné indexové pole přes, které přistupuji k vlastnímu poli záznamů.  

TZaznam = record
	...
end;

var
   Zaznamy : array od TZaznam;
   Indexy : array [] of integer;  // výchozí inicializace Indexy[x] = x 

// přístup k záznamům
   Zaznamy[Indexy[x]]

// při řazení pak případně prohodím pouze indexy

Výhodou je zachování původního řazení a možnost mít pomocí několika indexových polí na indexováno řazení podle více vlastností záznamu současně.

Nahlásit jako SPAM
IP: 91.139.9.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 8 hostů

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032020 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý