Przeglądając sporo metod sortowania integerów nie znalazłem żadnej operującej na tablicach dynamicznych, czy w ogóle jest taka?
0
0
Jak uda ci się posortować zwykłą tablicę to dynamiczną chyba też no nie?
0
Może masz problem w tym, że w zwykłej tablicy znasz ilość elementów a w dynamicznej nie? Jak tak to jeśli Tablica to ta tablica to
[code]
for n:=0 to Count(Tablica)-1 do...
[/code]
Dynamiczne tabelki są indeksowane od 0 więc będzie działać, ale można też tak
[code]
for n:=Low(Tablica) to High(Tablica) do...
[/code]
działa na zwykłych nie indeksowanych od zera też jak i na dynamicznych :)
0
Przykład sortowania tablicy open array (tablice dynamiczne też możesz tak przekazać) prosto z przykładu w Delphi:
{ TQuickSort }
procedure TQuickSort.Sort(var A: array of Integer);
procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var
Lo, Hi, Mid, T: Integer;
begin
Lo := iLo;
Hi := iHi;
Mid := A[(Lo + Hi) div 2];
repeat
while A[Lo] < Mid do Inc(Lo);
while A[Hi] > Mid do Dec(Hi);
if Lo <= Hi then
begin
VisualSwap(A[Lo], A[Hi], Lo, Hi);
T := A[Lo];
A[Lo] := A[Hi];
A[Hi] := T;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then QuickSort(A, iLo, Hi);
if Lo < iHi then QuickSort(A, Lo, iHi);
if Terminated then Exit;
end;
begin
QuickSort(A, Low(A), High(A));
end;
0
Sorry, koło 23.00 mam problemy z kojarzeniem. Chodziło mi o wyszukiwanie w tablicach dynamicznych zmiennych typu integer.
0
Sorry, koło 23.00 mam problemy z kojarzeniem. Chodziło mi o wyszukiwanie w tablicach dynamicznych zmiennych typu integer.
Teraz to ja już nie rozumiem.
Przecież jak deklarujesz tablicę to ona przechowuje zmienne określonego typu. Jeżeli zadeklarujesz:
array of Integer
to wszystkie elementy będą zmiennymi typu integer.
0
[niewinnosc]
Teraz chyba chodzi o wyszukiwanie elementu w tablicy dynamicznej.
Czy "dynamiczność" tej tablicy to ma jakiekolwiek znaczenie? Według mnie nie ma.
Oczywiście jestem na grząskim gruncie Delphi, ale podejrzewam że tablica dynamiczna jest normalną tablicą rozszerzoną o zmyślną metodę "add" tworzącą nową, większą o jeden element tablicę, następnie przekopiowującą dotychczasową zawartość do nowej tablicy, dopisującą nowy element na końcu i ostatecznie podmieniającą referencje.
Każda zmienna musi mieć określony rozmiar i nawet tablice dynamiczne są w danej chwili ograniczone i skończone.
Dlatego pytanie o to "jak sortować tabilicę dynamiczną", albo "jak wyszukiwać element w tablicy dynamicznej" jest chyba źle postawione.
Ostatecznie to są zwykłe tablice i w takich sytuacjach sięgamy do zwykłych algorytmów.
Żeby odrobinę zamieszać na koniec, wspomnę, że jedna cecha czyni tablice dynamiczne specyficznymi. Otóż możemy tak określić metodę add, aby nie wstawiała elementów w kolejności odpowiadającej ich napływaniu, tylko żeby wstawiała elementy zachowując pewną relację porządku. I okazuje się, że w takich sytuacjach najszybszym algorytmem sortowania nie jest quicksort, tylko insertsort. (wynika to z faktu, że cała kiedy dodajemy nowy element, to cała tablica jest już posortowana poza nowym elementem). Jest to dość rzadka sytuacja.
pozdrawiam
[niewinnosc]
karpia zjem.
0
for i:=0 to Length(Tablica)-1 do
if tab[i]=5 then close
0
Znów se poużywam [diabel]
Teraz chyba chodzi o wyszukiwanie elementu w tablicy dynamicznej.
Czy "dynamiczność" tej tablicy to ma jakiekolwiek znaczenie? Według mnie nie ma.
I tak i nie. To zależy jak pojmujemy tablice dynamiczne. Ci którzy korzystają z Delphi pojmują tablicę dynamiczną najczęściej jak zwykłą tablicę tylko z możliwością zmiany rozmiaru. Mam wygodny dostęp do każdego elemetnu A[i].
Ci, którzy piszą w czystym Pascalu zwykle przez tablicę dynamiczną rozumieją listę lub inny twór tego typu, w którym nie mamy wcale dostępu do każdego elementu w tak wygodny sposób jak w zwykłych tablicach.
I chociaż algorytm sortowania nie zmieni się dla jedej i drugiej tablicy to zmienia się wygoda implementacji algorytmu i jego wydajność.
Przy tablicach dynamicznych takich jak się rozumie w Pascalu dosyć niewygodnie jest stosować QuickSort (zwłaszcza, gdy tablicę reprezentuje lista jednokierunkowa). W tego typu tablicach zwiększa swoją efektywność zwykły algorytm wyszukiwania największego elementu i wstawiania go na początek (w tradycyjnych tablicach trzebaby przesuwać wszystkie elementy leżące poza na koniec).
Dlatego pytanie o to "jak sortować tabilicę dynamiczną", albo "jak wyszukiwać element w tablicy dynamicznej" jest chyba źle postawione.
Te pytania są w ogóle jakieś mgliste ;-)
Żeby odrobinę zamieszać na koniec, wspomnę, że jedna cecha czyni tablice dynamiczne specyficznymi. Otóż możemy tak określić metodę add, aby nie wstawiała elementów w kolejności odpowiadającej ich napływaniu, tylko żeby wstawiała elementy zachowując pewną relację porządku. I okazuje się, że w takich sytuacjach najszybszym algorytmem sortowania nie jest quicksort, tylko insertsort. (wynika to z faktu, że cała kiedy dodajemy nowy element, to cała tablica jest już posortowana poza nowym elementem). Jest to dość rzadka sytuacja.
Jeżeli chodzi o zachowywanie porządku to zwykle algorytmy zachowujące porządek należą do tych wolniejszych :)
0
nie pozostanę dłużny [diabel]
Naturalnie jest ogromna różnica pomiędzy listami a tablicami. Kiedy mówię tablice mam na myśli tablice a nie listy. Jestem pewien że nawet w Pascalu można zaimplementować dynamiczną tablicę (definując funkcję add dokładnie tak, jak opisałem wcześniej).
Oczywiście nie zgadzam sie ze stwierdzeniem:
Jeżeli chodzi o zachowywanie porządku to zwykle algorytmy zachowujące porządek należą do tych wolniejszych
Wolniejszych od czego mój drogi przedmówco?
Zaproponuję wam trzy rozwiązania, sami powiedzcie które byście wybrali ...
[b]Typowa sytuacja: [/b] Mamy bazę, przykładowo bazę danych biblioteki. Jest to oczywiście złożony system, ale nas interesuje tylko jeden aspekt: wyświetlanie alfabetycznej listy wszystkich książek należących do biblioteki. Nie wnikając nadmiernie w szczegóły, powiedzmy że książki przechowujemy w dynamicznie rozszerzającej się tablicy "booksArray[]".
[b]Pytanie: [/b] jak rozwiązać problem dodawania nowych pozycji i wyświetlania alfabetycznej listy książek, załóżmy że biblioteka jest stosunkowo duża i książki napływają do niej (to już jest czysta fikcja) kilka razy dziennie.
[b]1) [/b]nowe pozycje wpisujemy do booksArray[], przy czym tablica ta jest uporządkowana według chwili napływania danych, to znaczy, książka dodana najpóżniej ma najdalszy index. Jeżeli użytkownik zażąda wyświetlenie alfabetycznej listy, wstrzymujemy pracę systemu, tworzymy kopię tablicy booksArray[] (powiedzmy tempArray[]) sortujemy tablicę tempArray[] i ją wyświelamy.
[b]2)[/b] tablica booksArray[] jest prawie cała uporządkowana alfabetycznie, oprócz tych książek, które napłyneły jako ostatnie, one mają najdalsze indexy. Jeśli użytkownik zażąda wyświetlenie alfabetycznej listy, sortujemy listę booksArray[] i ją wyświetlamy.
[b]3)[/b] Tablica booksArray[] jest w każdej chwili całkowicie uporządkowana alfabetycznie. Kiedy wpisujemy do bazy nowy element, jest on od razu wstawiany w takie miejsce, aby cała tablica była posortowana. Kiedy użytkownik zażąda wyświetlenie alfabetycznej listy, wyświetlamy booksArray[].
Oczywiście to są ledwo szkice. Po pierwsze, celowo unikam szczegółów (to znaczy np. nie wspominam w jaki sposób wstawiamy elementy w projekcie 3) a po drugie, można wprowadzić wiele usprawnień (szczególnie projekt 2 jest pokrzywdzony). Niemniej uważni forumowicze dostrzegą pewną zaszytą zależność. Każdy następny projekt przeprowadza sortowanie na niższym poziomie, a wybór pomiędzy nimi sprowadza się do odpowiedzi na pytanie: "W którym momencie mam przeprowadzać sortowanie?"
Ostatecznie odpowiadając na przytoczony cytat, posłużę się odwołaniem do książki: "Perełki oprogramowania" Jon Bentley'a, gdzie bodajże w rozdziale 11.Sortowanie, jest wspomniane że w pewnych sytuacjach (dla pewnych specyficznych ułożeń elementów w tablicy wejściowej) sortowanie szybkie jest o wiele wolniejsze od sortowania przez wstawianie.
Pozdrawiam (w szczególności zadziornego przedmówcę)
[niewinnosc]
karpia zjem
0
A może użyć stog?
0
Oczywiście nie zgadzam sie ze stwierdzeniem:
Jeżeli chodzi o zachowywanie porządku to zwykle algorytmy zachowujące porządek należą do tych wolniejszych
Wolniejszych od czego mój drogi przedmówco?
Aj. Ugryzłem się w język.
Po pierwsze: miałem napisać "prostsze". Np. bąbelkowe, selection sort lub wspomniane insertion.
Po drugie: trochę się nie zrozumieliśmy (może to i moja wina). Nie chodziło mi o sortowanie przy wstawianiu, ale sortowanie już gotowej listy i zachowanie porządku. Przykład:
Lista nazwisk i imion posortowana według rosnąco wg Imion:
Nowak Adam
Kowalski Bartłomiej
Nowak Jan
Kowalski Zdzisław
Chcemy ją posortować wg Nazwisk, ale zachowując kolejność alfabetyczną Imion. Przy sortowaniu bąbelkowym otrzymamy taki wynik:
Kowalski Bartłomiej
Kowalski Zdzisław
Nowak Adam
Nowak Jan
Przy sortowaniu szybkim mniej więcej coś takiego:
Kowalski Zdzisław
Kowalski Bartłomiej
Nowak Jan
Nowak Adam
Jak widać nie zachowuje kolejności. Zdanie które wyraziłem odnosiło się do takiego zachowania porządku. Okazuje się, że algorytm sortowania szybkiego, jak też wiele innych algorytmów zaliczanych do tych dosyć szybkich, lecz bardziej skomplikowanych nie potrafi zachować kolejności. Algorytmy prostsze i zazwyczaj wolniejsze w większości przypadków zachowują kolejność.
Pozdrawiam (w szczególności zadziornego przedmówcę)
[niewinnosc]
Jak ja to kocham :