algorytm.org

Sortowanie przez scalanie (mergesort)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sortowanie przez scalanie (mergesort)
Ocena użytkowników:***** / 96
SłabyŚwietny 
Wpisany przez Marcin Krajewski, 20 listopada 2006 21:08

Sortowanie przez scalanie (podobnie jak algorytm QuickSort, jest algorytmem typu "dziel i zwyciężaj". Jednak w odróżnieniu od QuickSort, algorytm ten w każdym przypadku osiąga złozoność T(n) = n*log(n). Niestety algorytm MergeSort posiada większą złożoność pamięciową, potrzebuje do swojego działania dodatkowej, pomocniczej struktury danych.
Ideą działania algorytmu jest dzielenie zbioru danych na mniejsze zbiory, aż do uzyskania n zbiorów jednoelementowych, które same z siebie są posortowane :), następnie zbiory te są łączone w coraz większe zbiory posortowane, aż do uzyskania jednego, posortowanego zbioru n-elementowego. Etap dzielenia nie jest skomplikowany, dzielenie następuje bez sprawdzania jakichkolwiek warunków. Dzięki temu, w przeciwieństwie do algorytmu QuickSort, następuje pełne rozwinięcie wszystkich gałęzi drzewa. Z kolei łączenie zbiorów posortowanych wymaga odpowiedniego wybierania poszczególnych elementów z łączonych zbiorów z uwzględnieniem faktu, że wielkość zbioru nie musi być równa (parzysta i nieparzysta ilość elementów), oraz tego, iż wybieranie elementów z poszczególnych zbiorów nie musi następować naprzemiennie, przez co jeden zbiór może osiągąć swój koniec wcześniej niż drugi. Robi sie to w następujący sposób. Kopiujemy zawartość zbioru głównego do struktury pomocniczej. Następnie, operując wyłącznie na kopii, ustawiamy wskaźniki na początki kolejnych zbiorów i porównujemy wskazywane wartości. Mniejszą wartość wpisujemy do zbioru głównego i przesuwamy odpowiedni wskaźnik o 1 i czynności powtarzamy, aż do momentu, gdy jeden ze wskaźników osiągnie koniec zbioru. Wówczam mamy do rozpatrzenia dwa przypadki, gdy zbiór 1 osiągnął koniec i gdy zbiór 2 osiągnął koniec. W przypadku pierwszym nie będzie problemu, elementy w zbiorze głównym są już posortowane i ułożone na właściwych miejscach. W przypadku drugim trzeba skopiować pozostałe elementy zbioru pierwszego pokolei na koniec. Po zakończeniu wszystkich operacji otrzmujemy posortowany zbiór główny.
Przykładowy przebieg algorytmu ukazany jest na schemacie poniżej:
Sortowanie przez scalanie (mergesort)



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Krzysztof SobolC#
.cs
.cs
***** / 1
Marcin KrajewskiC/C++
.cpp
.cpp
***** / 53
MarianC/C++C++
.cpp
.cpp
***** / 30
Michał WC/C++Przy scalaniu do pamięci roboczej kopiowana jest tylko jedna z łączonych tablic.
.cpp
.cpp
***** / 6
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 11
Tomasz LubińskiJava
.java
.java
***** / 15
gchlebusJava
.java
.java
***** / 9
S3gaMathcad
-
.mcd
***** / 0
Rafał GawlikPythonPython2, Python3
.py
.py
***** / 6
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 maja 2011 08:46
Komentarze
photo
+1 # AdamMTT 2012-02-02 18:37
a c#?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-16 # Adam222222 2012-05-22 08:44
A co javy się nie lubi? :->
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-7 # Kostek 2012-08-11 19:50
a w PHP łopatologicznie ?
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz