PerlGtk.pl - Artykuły - Perl a Sortowanie

Perl a Sortowanie - Część Trzecia
przez wrares (451 odsłon)
Algorytmy sortowania działają dobrze lub źle. Techniki wykorzystywane w sortowaniu danych losowych są dość uciążliwe dla systemu. Możemy wykorzystać trzy takie techniki które Nas w tym wspomogą: Cytat: (1) SelectionSort (2) BubbleSort (3) InsertionSort Algorytm SelectionSort to algorytm sortowania poprzez wymianę/wybór. Służy\do odnajdowania najmniejszego elementu i umieszczania go w określonym miejscu. Działa on w ten sposób że odnajduje wartość minimalną lub maksymalną i umieszcza ją we właściwym miejscu po czym powtarza tą operację. Teraz podam przykłady odnajdujące minima lub maksima które dostępne są w internecie MINIMUM `#Liczby sub lmin { my $min = shift; foreach (@_) { $min = $_ if $_ < $min } return $min; } #Łańcuch sub smin { my $smin = shift; foreach (@_) { $smin = $_ if $_ lt $smin } return $smin; } #Uniwersalny sub u_min { my $umin = shift; my $ucmp = shift; foreach (@_) { $umin = $_ if $ucmp->($_, $umin) < 0; } return $umin; }` MAKSIMUM `#Liczby sub lmax { my $min = shift; foreach (@_) { $min = $_ if $_ > $min } return $min; } #Łańcuch sub smax { my $smin = shift; foreach (@_) { $smin = $_ if $_ gt $smin; } return $smin; } #Uniwersalny sub u_max { my $umax = shift; my $ucmp = shift; foreach (@_) { $umax = $_ if $ucmp->($_, $umax) < 0; } return $umax; }` Nie należy algorytmu SelectionSort stosować jako uniwersalnego algorytmu sortującego. Ma on dużą złożoność czasową chociaż jest stabilny. Algorytm sortowania bąbelkowego BubbleSort skanuje tablicę wielokrotnie zmieniając miejscami sąsiadujące elementy. Te tak zwane bąbelki to elementy poruszające się w tablicy czasie sortowania. Algorytm ten ma jedną cechę która go wyróżnia spośród innych. Jest najszybszym spośród dostępnych algorytmów pracujących na posortowanych danych. Dlatego bardzo dobrze nadaje się do śledzenia rankingu drużyn. Wyobraźmy sobie że śledzimy rozgrywki drużyn na zawodach. Raz już posortowaliśmy, więc teraz zmiany są minimalne. Drużyna awansuje lub odpada. A tutaj przykład... Algorytm InsertionSort przeszukuje wszystkie elementy, odnajduje najmniejszy i wstawia go we właściwe miejsce. Gdy element zostanie wstawiony, wszystkie nieposortowane elementy przesuwane są do przodu aby zrobić miejsce dla wstawianego. Przykładem może być posortowanie kart w rękach gracza. Przytoczę pewien przykład. Uzyskujemy dostęp do informacji w bazie. Ściągamy do tablicy dużą ich ilość. Następnie w drugiej tablicy mamy małą ilość informacji którą chcemy dodać do tej dużej. Proponuję posortować małą tablicę a następnie dodać do tej dużej. A tutaj podaję przykład zaczerpnięty z internetu `sub insertionSort { my @unsorted = @{$_[0]}; my @sorted = @{$_[1]}; INSERTION: for my $current ( @unsorted ) { for my $pos ( 0 .. $#sorted ) { if ( $sorted[$pos] >= $current ) { splice @sorted, $pos, 0, $current; # Insert $current next INSERTION; } } push @sorted, $current; # No larger value has been found in @sorted } return @sorted; } my @unsorted = qw(1 82 73 745839 928 7346 8 6 4 8 0 6 34 102); my @sorted = qw(1 5); @sorted = insertionSort(\@unsorted, \@sorted);` Jak zauważamy dobór algorytmu do rozwiązania aktualnego problemu nie jest sprawą trywialną.

Powrót