Sortowanie przez wstawianie - problem

Odpowiedz Nowy wątek
2003-12-01 07:00

Rejestracja: 17 lat temu

Ostatnio: 3 lata temu

Lokalizacja: Kielce

0

wykonując taki kod:

procedure Sort(const ASize: Integer; AIn: array of Integer; var AOut: Array of Integer);
var
  I, J, K, Found: Integer;
begin
  for I:=0 to ASize do
    AOut[I]:=-1;
  AOut[0]:=AIn[0];
  for I:=1 to ASize do
    begin
      Found:=AIn[I];
      for J:=0 to ASize do
        begin
          if AOut[J]>Found then
            begin
              for K:=ASize downto J-1 do
                begin
                  if K-1>=0 then
                    AOut[K]:=AOut[K-1]
                end;
              AOut[J]:=Found;
              Break;
            end
          else
            if AOut[J]=-1 then
              AOut[J]:=Found;
        end;
    end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Size, I: Integer;
  Unsorted, Sorted: array of Integer;
  Contains: string;
begin
  Randomize;
  Size:=StrToInt(Edit1.Text);
  SetLength(Unsorted, Size);
  SetLength(Sorted, Size);
  Memo1.Lines.Add('Log: Begin');
  for I:=0 to Size do
    begin
      Unsorted[I]:=Random(255);
      Contains:=Contains+IntToStr(Unsorted[I])+', ';
    end;
  Memo1.Lines.Add(Contains);
  Memo1.Lines.Add('Log: Begin sort');
  Contains:='';
  Sort(Size, Unsorted, Sorted);
  Memo1.Lines.Add('Log: End sort');
  for I:=0 to Size do
    begin
      Contains:=Contains+IntToStr(Sorted[I])+', ';
    end;
  Memo1.Lines.Add(Contains);
  Memo1.Lines.Add('Log: End');
end;

Dostaje informacje o "Invalid pointer operation". Kod już sprawdzam trzeci dzień i nic nie mogę wykombinować, aby to poprawić.

ps. to jest algorytm na sortowanie przez wstawianie...


HAKGER - 50% Complete

Pozostało 580 znaków

2003-12-01 09:28

Rejestracja: 16 lat temu

Ostatnio: 7 lat temu

0

A nie pomyślałeś o tym, że tablica, której przydzielisz pamięc przez setlength(tab,len) ma indeksy od 0 do len-1? Zamień w sortowaniu asize na asize-1. To tyle, ile rzuca się od razu w oczy, może jest jeszcze coś. :>


Linuksa, czy innego Uniksa, można opisać za pomocą logiki boolowskiej a nie za pomocą prawdopodobieństwa.

'System szesnastkowy jest wspaniały! W skali od 1 do 10 daję mu E'

extreme safety for Ubuntu:
sudo echo -e 'Defaults targetpw\nDefaults timestamp_timeout=0' >> /etc/sudoers

Pozostało 580 znaków

2003-12-01 10:17

Rejestracja: 16 lat temu

Ostatnio: 16 lat temu

0

A nie pomyślałeś o tym, że tablica, której przydzielisz pamięc przez setlength(tab,len) ma indeksy od 0 do len-1? Zamień w sortowaniu asize na asize-1. To tyle, ile rzuca się od razu w oczy, może jest jeszcze coś. :>

Ot co - przecież liczysz elementy od zera, a więc rozmiar musi być o jeden mniejszy.

A propos. Po kiego GRZYBA używasz tak kosmicznego sortowania. Looknij na [Delphi]/Demos/Threads/SortThds.pas i zobaczysz jak się sortuje. Porównasz sobie szybkość i dokładność sortowania.

A propos 2. Czy wiesz, że gdybyś użył listy to mógłbyś uzyć wewnętrznego sortowania stringów w liście (jako parametr odwołałbyś się do porównania dwóch elementów listy). Funkcja Sort sama "przeleci" po wszystkich parach listy i ustawi ją wg twojego porównania
np.
function SortujLista(El1, El2: Pointer): Integer;
begin
Result:=CompareStr( IntToStr(El1)), IntToStr(El2));
end;
MojaList.Sort(@SortujLista);

Pozostało 580 znaków

2003-12-01 22:58

Rejestracja: 17 lat temu

Ostatnio: 1 rok temu

0

A propos. Po kiego GRZYBA używasz tak kosmicznego sortowania. Looknij na [Delphi]/Demos/Threads/SortThds.pas i zobaczysz jak się sortuje. Porównasz sobie szybkość i dokładność sortowania.

Bo może ma za zadanie użyć takiego algorytmu? A może potrzebuje stabilnego algorytmu sortowania i np. przedstawiony w SortThds.pas najszybszy z tamtych QuickSort nie spełnia już jego założeń.

A co do sortowania przez wstawianie, to można ten kod znacznie prościej napisać (nie tracąc na efektywności). Jakoś tak:

for i := 0 to n-1 do
begin
  j := i;
  while t[j] > t[j+1] do
  begin
    pom := t[j];
    t[j] := t[j+1];
    t[j+1] := pom;
    Dec(j);
  end;
end;

Oczywiście tutaj zmieniana jest tablica wejściowa.


Jest jeszcze jeden błąd :)
Unix is user friendly. It's just very particular about who it's friends are.

Pozostało 580 znaków

2003-12-02 07:06

Rejestracja: 17 lat temu

Ostatnio: 3 lata temu

Lokalizacja: Kielce

0

Dryo dzięki ci! masz u mnie [browar] flabra też...

ps. Dry, skąd wiedziałeś że ten algorytm mam do zrobienia do szkoły? Przewidywanie bardzo dobrze Ci idzie...

//sory doktorku, dryo, jak tak sobie pomyślałem, to się okazało mnie że to co przedstawiłeś to sortowanie bąbelkowe...


HAKGER - 50% Complete

Pozostało 580 znaków

2003-12-02 21:41

Rejestracja: 17 lat temu

Ostatnio: 3 lata temu

Lokalizacja: Kielce

0

kombinując tak po trochu wykombinowałem takie coś:

procedure Sort(const AIn: array of Integer; var AOut: Array of Integer);
var
  I, J, K, Found: Integer;
begin
  for I:=0 to High(AIn) do
    AOut[I]:=-1;
  AOut[0]:=AIn[0];
  for I:=1 to High(AIn) do
    begin
      Found:=AIn[I];
      for J:=0 to High(AIn) do
        begin
          if AOut[J]>Found then
            begin
              for K:=High(AIn) downto J-1 do
                begin
                  if K-1>=0 then
                    AOut[K]:=AOut[K-1]
                end;
              AOut[J]:=Found;
              Break;
            end
          else
            if AOut[J]=-1 then
              AOut[J]:=Found;
        end;
    end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Size, I: Integer;
  Unsorted, Sorted: array of Integer;
  Contains: string;
begin
  Randomize;
  Size:=StrToInt(Edit1.Text);
  SetLength(Unsorted, Size);
  SetLength(Sorted, Size);
  Memo1.Lines.Add('Log: Begin');
  for I:=0 to High(Unsorted) do
    begin
      Unsorted[I]:=Random(255);
      Contains:=Contains+IntToStr(Unsorted[I])+', ';
    end;
  Memo1.Lines.Add(Contains);
  Memo1.Lines.Add('Log: Begin sort');
  Contains:='';
  Sort(Unsorted, Sorted);
  Memo1.Lines.Add('Log: End sort');
  for I:=0 to High(Sorted) do
    begin
      Contains:=Contains+IntToStr(Sorted[I])+', ';
    end;
  Memo1.Lines.Add(Contains);
  Memo1.Lines.Add('Log: End');
end;

nie ma już Invalid Pointer operation, ale jast skopane, bo logi działania pokazują błędy, oto one:

Log: Begin
102, 232, 55, 130, 63, 193, 69, 208, 139, 24,
Log: Begin sort
Log: End sort
24, 55, 55, 63, 63, 69, 69, 139, 208, 232,
Log: End

Log: Begin
112, 1, 235, 84, 90, 97, 21, 173, 26, 54,
Log: Begin sort
Log: End sort
1, 1, 1, 1, 1, 54, 97, 97, 173, 235,
Log: End

Log: Begin
215, 94, 157, 221, 33, 20, 12, 2, 86, 121,
Log: Begin sort
Log: End sort
2, 12, 20, 20, 86, 86, 121, 157, 215, 221,
Log: End

Log: Begin
79, 216, 15, 75, 241, 92, 183, 5, 248, 12,
Log: Begin sort
Log: End sort
5, 12, 15, 75, 75, 75, 183, 216, 216, 216,
Log: End

Log: Begin
95, 22, 254, 14, 86, 239, 104, 9, 158, 23,
Log: Begin sort
Log: End sort
9, 14, 14, 23, 86, 86, 86, 158, 239, 254,
Log: End

Log: Begin
189, 23, 148, 244, 223, 146, 143, 88, 3, 14,
Log: Begin sort
Log: End sort
3, 14, 23, 88, 143, 146, 148, 148, 223, 244,
Log: End

Log: Begin
9, 61, 195, 182, 147, 22, 28, 76, 116, 178,
Log: Begin sort
Log: End sort
9, 9, 28, 61, 61, 61, 61, 61, 61, 61,
Log: End
--------------------------------------

Wszystkie były robione dla Size = 10

Bardzo pomocne by były rady dadatkowe, bo na zabawę w wyświetlanie zmiennych i ich analizacje nie mam czasu


HAKGER - 50% Complete

Pozostało 580 znaków

2003-12-02 23:59

Rejestracja: 17 lat temu

Ostatnio: 1 rok temu

0

//sory doktorku, dryo, jak tak sobie pomyślałem, to się okazało mnie że to co przedstawiłeś to sortowanie bąbelkowe...

Otóż nie. To jest sortowanie przez proste wstawianie. Jest podobne do bąbelkowego, ale nie jest bąbelkowym. Po prostu tutaj przestawianie elementów jest połączone z wyszukiwaniem miejsca na jego wstawienie. W sortowaniu bąbelkowym zamieniamy po dwa elmenty ze sobą. Tutaj bierzemy drugi element i cofając się przestawiamy go, aż znajdzie się na odpowiednim miejscu. Tamten kod może nie oddawał tego tak dokładnie, więc podam tutaj dwa kody. Sortowanie przez proste wstawianie (takie jak tamto, ale zoptymalizowane i z asercjami) oraz przez połówkowe wstawianie (różnią się tylko sposobem wyszukiwania elementu, ale zasada jest ta sama. Mając posortowaną część tablicy, bierzemy pierwszy element nie posortowany. Wstawiamy go w odpowiednie miejsce i przesuwamy resztę. Na listach robi się to znacznie fajniej).

var
  t: array [1..n] of Integer;
  pom, i, j: Integer;
begin
  for i := 2 to n do
  begin
    j := i;
    while (j>1) and (t[j] < t[j-1]) do
    begin
      pom := t[j];
      t[j] := t[j-1];
      t[j-1] := pom;
      Dec(j);
      (* <1, j) - posortowane, <j, i> - posortowane *)
    end;
    (* <1, i> - posortowane *)
  end;
end;

Liczba porówniań (pesymistycznie) n(n-1)/2
Liczba przestawień (pesymistycznie) n
(n-1)/2

Przez wstawianie połówkowe:

for i := 2 to n do
begin
  x := A[i];
  l := 1;
  p := i - 1;
  while l <= p do
  begin
    m := (l+p) div 2;
    if x < A[m] then
      p := m-1
    else
      l := m+1;
   end;
   for j := i-1 downto l do
     A[j+1] := A[j];
   A[l] := x;
end;

Liczba porówniań (pesymistycznie) log n
Liczba przestawień (pesymistycznie) n*(n-1)/2


Jest jeszcze jeden błąd :)
Unix is user friendly. It's just very particular about who it's friends are.

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0