[delphi] tagi z plików MP3 zakodowanych w formacie ID3v2
[delphi] problem ze zmianą ikony programu
[delphi] Rysowanie na Canvasie z pliku *bmp
[delphi] procedury przy pokazaniu formy
Samsung GT-B3410 Delphi
[delphi] sprawdzanie poprawności adresu
[delphi] efekt przewijania label'a
[delphi] przylepianie formy
[delphi] konstrukcja wyjątku
[Delphi] Program w zasobniku....
chomiki
Witam,Mam problem z implementacją algorytmu sortowania bąbelkowego w Delphi7. Oto kod programu:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TBubble = class(TForm)
Memo: TMemo;
bSortuj: TButton;
Rrosnaco: TRadioButton;
Rmalejaco: TRadioButton;
bLosuj: TButton;
procedure bLosujClick(Sender: TObject);
procedure bSortujClick(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Bubble: TBubble;
tab : array[1..100] of integer; // tablica globalna
implementation
{$R *.dfm}
procedure TBubble.bLosujClick(Sender: TObject);
var
i : integer;
begin
Memo.Clear;
for i:= 1 to 100 do
begin
Randomize;
tab[i]:=Random(100);
Memo.Lines.Add(IntToStr(tab[i]));
end;
end;
procedure TBubble.bSortujClick(Sender: TObject);
var
i, temp : integer;
begin
for i:=1 to Length(tab) do
begin
if tab[i] > tab[i+1] then
begin
temp := tab[i];
tab[i] := tab[i+1];
tab[i+1] := temp; // zamiana miejscami jesli an > an+1
end;
end;
for i:=1 to Length(tab) do
Memo.Lines.Add(IntToStr(tab[i])); // wypelnianie Memo danymi
end;
end.
Chodzi o to, że program po naciśnięciu przycisku sortuje mi tylko raz (przenosi jedną liczbę na koniec). Domyślam się, że brakuje mi jeszcze jakiegoś warunku. Prosiłbym o sugestie odnośnie brakujących danych oraz większej optymalizacji (jeśli możliwe)
Wiem, że jest to jeden z podstawowych algorytmów i można to znaleźć na internecie, ale chciałem sam wykombinować, bo tak człowiek najlepiej się uczy.
Musisz dorobić drugą pętelkę, w której ta aktualnie przesuwająca największą liczbę na koniec będzie chodzić. A optymalizacja - pętelka przesuwająca na koniec nie musi być na koniec a jedynie do indeksu gdzie ostatnio ustawiłeś liczbę, czyli - za pierwszym przebiegiem - do końca, drugi przebieg - do końca - 1 (bo na końcu jest już na pewno największa liczba), trzeci - do końca - 2 itd ...
Mam nadzieję, że dobrze wytłumaczyłem
BTW - Popatrz na pętlę - gdy i będzie równe Length(tab) to [i + 1] będzie ...
Czyli kolejna - nadrzędna pętla ma sprawdzać, czy wykonało się pojedyncze sortowanie wewnątrz tej podrzędnej, i jeśli nie, to ma się zakańczać, tak?
Z tym Length(tab) już poprawiłem
Pętla nic nie ma sprawdzać
Chyba jednak źle wytłumaczyłem ...
Pętla wewnętrzna przesuwa największą liczbę ze zbioru na koniec, pętla zewnętrzna określa ile liczb ma być przesuniętych. Optymalizacja polega na ograniczaniu rozmiaru zbioru, w którym dokonujemy przesunięcia.
Rozpatrując na przykładzie:
Mamy trzy liczby i mamy je uporządkować.
Pierwszy obrót pętli zewnetrznej - przesunięcie największej z liczb na koniec zbioru trzech liczb (wykonanie pętli wewnętrznej), drugi obrót pętli zewnętrznej - przesunięcie największej liczby na koniec (znowu wykonanie pętli wewnętrznej), ale już ze zbioru dwóch liczb (bo trzecia liczba już siedzi na swoim miejscu).
Jak teraz nie rozumiesz to już chyba kodem rzucę
Poełniłem coś takiego:
procedure TBubble.bSortujClick(Sender: TObject);
var
i, x, temp : integer;
begin
Memo.Clear;
for x:=(Length(tab)-1) downto 1 do begin
for i:=1 to x do
begin
if tab[i] > tab[i+1] then
begin
temp := tab[i];
tab[i] := tab[i+1];
tab[i+1] := temp; //przesuniecie na koniec najw. liczby
end;
end;
end;
for x:=1 to length(tab) do
Memo.Lines.Add(IntToStr(tab[x])); // wypelnianie Memo danymi
end;
z tego, co rozumiem, teraz liczba sortowań zmniejsza się z każdą iteracją pętli nadrzędnej i jest optymalnie. Dobrze myślę?
Zrobiłeś dokładnie tak jak ja bym to zrobil
Czy da się ten konkretnie algorytm bardziej zoptymalizować - nie wiem. Wydaje mi się, że nie.
Lux
Zamieszało mi się w głowie, bo zacząłem przeglądać definicję w Wikipedii, a tam były jakieś implementacje w C (którego kompletnie nie znam) i zachciało mi się kombinować. Ważne, że jednak się udało
Dzięki.
Pętla nic nie ma sprawdzać
Chyba jednak źle wytłumaczyłem ...
Pętla wewnętrzna przesuwa największą liczbę ze zbioru na koniec, pętla zewnętrzna określa ile liczb ma być przesuniętych. Optymalizacja polega na ograniczaniu rozmiaru zbioru, w którym dokonujemy przesunięcia.
a przypadkiem Ty nie mówisz o sortowaniu poprzez wstawianie??
bąbelkowe działa na zamianie dwóch liczb sąsiadujących obok siebie, a nie wyszukiwaniu największej i wstawianie ją na koniec - tak działa sortowanie poprzez wstawianie
Chodzi o bąbelkowe, bo przy pierwszym przetworzeniu wszystkich elementów tablicy na końcu "ustawia się" właśnie największa liczba Później przedostatnia itd...
Chodzi o bąbelkowe, bo przy pierwszym przetworzeniu wszystkich elementów tablicy na końcu "ustawia się" właśnie największa liczba Później przedostatnia itd...
No to właśnie tak się dzieje poprzez zamianę miejscami dwóch sąsiadujących liczb
Mam nadzieję, że ten link pomoże
http://algorytm.org/index...d=108&Itemid=28
//A jak nie, to sorry za robienie syfu
Ze swojej strony jeszcze dopowiem tylko, że najlepiej byłoby zrobić to w pętli while
(nam nauczyciel tłumaczył to tak: masz chorągiewkę (zmienna boolean), w każdym obiegu gdy zamieniasz - jeśli trzeba - pozycjami dwie liczby, wtedy "podnosisz" chorągiewkę. Jak będzie opuszczona, while może uznać, że nie ma co do robienia i koniec )
