algorytmy_i_struktury_danych:sortowanie

Co prawda nie jest to mój temat, ale widzę, że osoba odpowiedzialna za sortowanie, nie ma zamiaru zrobić tego jak należy.

dobry człowieku (kimkolwiek jesteś) - dzięki za pomoc i uzupełnienie odp. na to pytanie, choć na mój gust to sortowanie drzewiaste czy sortowanie plików sekwencyjnych to nie jest to, co zawiera sie w kategorii “podstawowe metody sortowania” - wydaje mi sie ze 3 lub 4, ktore tu wymienilem to wszystko - odzwierciedla to ilość opracowań w internecie, w końcu też na stronach akademickich (czy popularnej książce pana Wróblewskiego) i nie wydaje mi się by u nas wymagali więcej niż na innych...ale widze że jesteś ambitny (a może nadgorliwy?) i chcesz się nauczyć więcej, i słusznie! przeciez wiedzy nigdy za mało;) wiadomo, że każde pytanie można rozpisywać w nieskończoność, a chyba nie o to chodzi choć nie wiem jak egzamin będzie wyglądał - czy to będzię pytanie-odpowiedź tylko czy może jeszcze dodatkowo jakies pytania uzupełniające. Co do oceny wydajności z która miałem problem to niestety sortowanie bąbelkowe nie było ZAWSZE najgorsze, wątek oceny wydajności dalej jest dla mnie niejasny bo podzielić te algorytmy na lepsze i gorsze nie jest tak trudno jak przyznać im konkretne miejsca na podium. Nie mam też zamiaru tak jak to chyba również Ty zasugerowałeś(aś) w uwagach, że trzeba przeczytać książke o sortowaniu by udzielić odp. w kwestii wydajności - sory, ale ja sam nie mam zamiaru pisać doktoratu z sortowania.. i wydaje mi się, że dokładne analizy wydajności są poza zakresem tego egzaminu, ale mogę się mylić. Rasumując zgadzam się ze stwierdzeniem, że odp na to pytanie można było lepiej opracować, ale na pewno nie lepiej niż to jest zrobione tutaj: http://www.i-lo.tarnow.pl/edu/inf/alg/algsort/ - moim zdaniem najlepsza strona o algorytmach i wszystko co trzeba każdy tam znajdzie, zakres powtórki też każdy indywidualnie sobie określi bo jest z czego wybierać. W sumie to zamiast tego opracowania mogłem podać ten link i by było chyba najlepiej.

## Sortowanie

Sortowania można podzielić na: sortowania tablica oraz sortowania plików sekwencyjnych

### Algorytmy sortowanie tablic

- select sort (proste wybieranie, znajdujemy po kolei elementy zaczynając od najmniejszego), złożoność: n^2
- insert sort (proste wstawianie, opisane w rozdziale), złożoność: n^2
- bubble sort (bąbelkowe, opisane w rozdziale), złożoność: n^2
- quick sort (szybkie, nie wiem czy autor sam rozumiał co pisze. Idea działania jest taka: wybierz losowy element z tablicy, zapamiętaj jego wartość (mediana), idź od lewego “krańca” tablicy, aż znajdziesz element większy od wylosowanego, idź od prawej aż znajdziesz mniejszy, zamień je miejscami, rób tak aż wskaźniki (indeksy) się spotkają. Otrzymujesz dwa podciągi, dla których powtarzasz procedurę. W efekcie otrzyujesz posortowaną tablicę), złożoność: n*lon(n)
- tree sort (sortowanie drzewiaste, budujemy “drzewo”, “najniższa” warstwa to elemnty tablicy (n - elementów), kolejna warstwa, (n/2 elementów) składa się z mniejszego elementu z pary sąsiednich elementów itd. np:

ciąg: 44 45 12 42 94 18 06 67

- Najniższy poziom drzewa 44 45 12 42 94 18 06 67
- Wyższy (min. (44, 45)) 44, (min. (12, 42)) 12, (min. (94, 18)) 18, (min (06, 67))
- Wyższy 12, 06
- Najwyższy 06

Wyszukiwanie najmniejszego elementu trwa log2(n), usuwamy go i budujemy od nowa

- 44 45 12 42 94 18 67
- 42 12 18 67
- 12 18
- 12

aż do “opróżnienia” drzewa (do tego jest bardzo sprytny algorytm )), złożoność n*log (n)

Najlepsze rezultaty “doświadczalne mają”: quick sort, tree sort, pozostałe (bąbelkowe zawsze najgorsze)

### Algorytmy sortowanie plików sekwencyjnych

łączenie proste (pozostałe algorytmy to jego modyfikacje), składa się z dwóch etapów:

Podział: otwieramy plik do odczytu (p1), a dwa do zapisu (p2,p3), zapisujemy pierwszą liczbę (element) a pliku p1 do p2, bierzemy kolejną liczbę, jeśli większa bądź równa zapisujemy do p2, jesli mniejsza do p3 i zamieniamy “rolę” pliku p2 z p3 (od tej pory piszemy do p3, chyba, że trafimy na kolejną mniejszą, wtedy znowu p2 itd.)

Łączenie: otwieramy do odczytu p2 i p3, do zapisu p1, zapisujemy mniejszy z elementów z plików p2 i p3 do p1, bierzemy kolejny element z pliku, z którego element był mniejszy, aż do przepisania wszytskich elementów z p2 i p3. Ponawiamy algorytm podziału

Postępujemy tak długo, aż przy podziale p2 lub p3 będzie pusty.

Złożoność n*log(n)

Dzięki za uwagę

### Sortowanie bąbelkowe

Jest to jeden z prostszych algorytmów sortowania. Sprawdzamy całą tablicę od końca, jeżeli trafimy na parę elementów, w której większy poprzedza mniejszy to zamieniamy je miejscami i znów zaczynamy przeszukiwać tą tablicę od końca(?)(a nie powinno być - i idąc do początku tablicy postępujemy analogicznie z kolejnymi elementami? taką sytuację przedstawia drugi rysunek (buble2)). Czynność powtarzamy tak długo aż podczas sprawdzania całej tablicy, nie zajdzie ani jedna zamiana elementów. Realizuje sięto najczęściej za pomocą zmiennej logicznej. Złożoność O(n^2) Algorytm nosi nazwę bąbelkowego, gdyż najmniejsze liczby “wypływają” z dołu tablicy na jej szczyt. Oto przykład zastosowania dla nieuporządkowanego ciągu liczb «2, 4, 1, 3».

bubble1: bubble2:

Przy następnym przebiegu nie zajdzie ani jedna zmiana, to znak, że ciąg jest już posortowany. Z powyższego zdania można wyciągnąć wniosek, że gdy ciąg wejściowy będzie posortowany, to algorytm wykona tylko jeden przebieg. Jest to duża zaleta tego sposobu sortowania, niektóre metody będą sortowały ciąg nawet jeśli będzie on posortowany. Z kolei najgorszym zestawem danych dla tego algorytmu jest ciąg posortowany nierosnąco.

uwaga: opisana tutaj wersja jak i wersje w linkach poniżej są lekko zmodyfikowane w stosunku do bazowej postaći tego algorytmu, który opisuje pan Piotr Wróblewski (o ile ta wersja jest rzeczywiście najbardziej podstawowa), gdzie zaczynamy porównywać elementy od końca przesuwając się do przodu po każdym porównaniu (nie wracamy po każdej zamianie elementów jak to jest opisane w tej wersji na stronie!) - wracamy się dopiero jak dojdziemy do początku tablicy, a w drugim przebiegu dochodzimy nie do konca, a do drugiego elementu (licząc od początku tablicy) gdyż pierwszy to jest ten, który jako najmniejszy wypłynął pierwszy na samą górę. Myślę, że która wersje się będzie opisywało to nie ma aż takiego znaczenia o ile wiemy jak dokładnie ona działa.

Inny opis z dobrym przykładzie na stronie www

Inne źródło informacji

Przykład sortowania na stronie www

### Sortowanie szybkie (Quicksort)

Algorytm sorotwania szybkiego jest uważany za najszybszy algorytm dla danych losowych. Zasada jego działania opiera się o metodę dziel i zwyciężaj (Jeżeli problem można podzielić na kilka mniejszych, niezależnych podproblemów i rozwiązać je rekurencyjnie a na końcu połączyć je w rozwiązanie całego problemu, możemy zastosować metodę “dziel i zwyciężaj”). Zbiór danych zostaje podzielony na dwa podzbiory i każdy z nich jest sortowany niezależnie od drugiego. Dla zadanej tablicy a[l..p] wybieramy element v=a[l] i przeszukujemy resztę tablicy (tzn. a[l+1..p]) tak długo, aż nie znajdziemy elementu nie większego(niemniejszego?) niż a[l]. Następnie przeszukujemy tą tablicę od strony prawej póki nie znajdziemy elementu nie większego niż a[l]. Gdy to osiągniemy, zamieniamy miejscami te dwa elementy i zaczynamy cały proces od początku. Algorytm działa tak długo, aż wskaźnik poruszający się w lewo i wskaźnik poruszający się w prawo spotkają się. Należy wówczas zamienić element v=a[l] z ostatnim elementem lewej części tablicy. Mimo, że w najgorszym przypadku algorytm ma złożoność kwadratową, jest on bardzo często stosowany. Powodem tego jest niska- liniowologarytmiczna, złożoność w średnim przypadku.

Inny opis z ciekawym przykładem działania

Inne źródło informacji

Przykład sortowania na stronie www

### Sortowanie przez wstawianie (insertionsort)

Zasada działania tego algorytmu jest często porównywana do porządkowania kart w wachlarz podczas gry. Każdą kartę wstawiamy w odpowiednie miejsce, tzn. po młodszej, ale przed starszą. Podobnie jest z liczbami. Pierwszy element pozostaje na swoim miejscu. Następnie bierzemy drugi i sprawdzamy, w jakiej relacji jest on z pierwszym. Jeśli jest niemniejszy, to zostaje na drugim miejscu, w przeciwnym wypadku wędruje na pierwsze miejsce. Dalej sprawdzamy trzeci element (porównujemy go do dwóch pierwszych i wstawiamy w odpowiednie miejsce), czwarty (porównujemy z trzema pierwszymi), piąty itd. Idea działania algorytmu opiera sięna podziale ciągu na dwie części: pierwsza jest posortowana, druga jeszcze nie. Wybieramy kolejną liczbę z drugiej części i wstawiamy ją do pierwszej. Ponieważ jest ona posortowana, to szukamy dla naszej liczby takiego miejsca, aby liczba na lewo była niewiększa a liczba na prawo niemniejsza. Wstawienie liczby do posortowanej tablicy wymaga więc czasu O(n). Wynika z tego złożoność algorytmy: O(n2) Oto przykłąd dla nieposortowanego ciągu <2, 4, 1, 3>

Inny opis z ciekawym przykładem

Inne źródło informacji

Przykład sortowania na stronie www

### Sortowanie przez scalanie (MergeSort)

Opis z przykładem

## Porównanie algorytmów sortowania

Na stronie http://ww.umk.pl/~abak/wdimat/s/Compare.html możecie sami porównywać między sobą 2 wybrane algorytmy. Postaram sie jeszcze ten punkt rozwinąć.

Porównanie algorytmów sortowania

Analiza wybranych algorytmów sortowania i wyszukiwania (PDF)

Porównanie klas czasowej złożoności obliczeniowej

Analiza i ocena algorytmów sortowania

Opis kilku algorytmów i program do porównania ich wydajności

## Pozostałe linki

Inne algorytmy sortowania oraz pozostałe informacje związane z algorytmami i strukturami danych są opisane na poniższych stronach:

Bardzo fajny przegląd algorytmów wraz z ich szczegółową analizą i przykładami (polecam)

http://oen.dydaktyka.agh.edu.pl/dydaktyka/informatyka/c_algorytmy_i_str_danych/index.php

http://ww.umk.pl/~abak/wdimat/s/Index.html

http://www.algorytm.org

http://mpuszek.republika.pl/sortowanie.html