Merge sort
Mergesort je stabilní řadicí algoritmus typu rozděl a panuj s asymptotickou složitostí . Merge sort pracuje na bázi slévání již seřazených částí pole za pomoci dodatečného pole velikosti
.
Merge sort byl vynalezen v roce 1945 Johnem von Neumannem.
Princip
Slévání
Předpokládejme, že máme dva seznamy (A, B) seřazené v sestupném pořadí. Tyto seznamy můžeme setřídit do jediného seznamu (C) následující procedurou.
V každém kroku vždy porovnejme první prvky obou seznamů (tj. nejvyšší prvky obou seznamů) a vyberme ten vyšší. Tento nakopírujme na konec seznamu C a odstraňme jej ze seznamu původního. Tento postup opakujme tak dlouho, dokud se jeden ze seznamů nevyprázdní. Potom překopírujme zbytek druhého seznamu do C (a odstraňme překopírované prvky z původního seznamu).
Ve skutečnosti slévá merge sort vždy dvě sousední části pole. Drží si dva ukazatele, každý na první prvek seznamu a po každém porovnání přesune jeden z prvků do pomocného pole a posune příslušný ukazatel o jedno místo (címž se dostane na nový nejvyšší prvek příslušného seznamu). Poté, co zkopíruje všechny prvky obou seznamů do pomocného pole, tak celé původní pole přepíše seřazeným seznamem (pomocným polem).
Dělení
Dosud jsme nezmínili, jak algoritmus získá dvě seřazená sousední pole. Dělicí část merge sortu má na svém vstupu celé pole. Toto rozdělí na dvě stejně velké části, tyto dvě části pak dále rekurzivně dělí. V okamžiku, kdy rekurze narazí na seznamy jednotkové velikosti, tak se zastaví. Nyní má algorimus v každé větvi k dispozici dva sousední seznamy, které obsahují jeden prvek a jsou tedy triviálně seřazeny.
Řazení
Merge sort se tedy začne navracet z rekurze a při každém návratu sleje dva seznamy pomocí výše zmíněné procedury slévání. Algoritmus má jistotu, že buď slévá triviálně seřazené prvky nebo seznamy, které již byly slity. V okamžiku, kdy se merge sort plně navrátí z rekurze, tak terminuje. Pole je seřazeno od nevyšší hodnoty.
Kód
/**
* Razeni slevanim (od nejvyssiho)
* @param array pole k serazeni
* @param aux pomocne pole stejne delky jako array
* @param left prvni index na ktery se smi sahnout
* @param right posledni index, na ktery se smi sahnout
*/
public static void mergeSort(int[] array, int[] aux, int left, int right) {
if(left == right) return;
int middleIndex = (left + right)/2;
mergeSort(array, aux, left, middleIndex);
mergeSort(array, aux, middleIndex + 1, right);
merge(array, aux, left, right);
for (int i = left; i <= right; i++) {
array[i] = aux[i];
}
}
/**
* Slevani pro Merge sort
* @param array pole k serazeni
* @param aux pomocne pole (stejne velikosti jako razene)
* @param left prvni index, na ktery smim sahnout
* @param right posledni index, na ktery smim sahnout
*/
private static void merge(int[] array, int[] aux, int left, int right) {
int middleIndex = (left + right)/2;
int leftIndex = left;
int rightIndex = middleIndex + 1;
int auxIndex = left;
while(leftIndex <= middleIndex && rightIndex <= right) {
if (array[leftIndex] >= array[rightIndex]) {
aux[auxIndex] = array[leftIndex++];
} else {
aux[auxIndex] = array[rightIndex++];
}
auxIndex++;
}
while (leftIndex <= middleIndex) {
aux[auxIndex] = array[leftIndex++];
auxIndex++;
}
while (rightIndex <= right) {
aux[auxIndex] = array[rightIndex++];
auxIndex++;
}
}
/**
* Razeni slevanim (od nejvyssiho)
* @param array pole k serazeni
* @param aux pomocne pole stejne delky jako array
* @param left prvni index na ktery se smi sahnout
* @param right posledni index, na ktery se smi sahnout
*/
void mergeSort(int array[], int aux[], int left, int right) {
if (left == right) return;
int middleIndex = (left + right)/2;
mergeSort(array, aux, left, middleIndex);
mergeSort(array, aux, middleIndex + 1, right);
merge(array, aux, left, right);
for (int i = left; i <= right; i++) {
array[i] = aux[i];
}
}
/**
* Slevani pro Merge sort
* @param array pole k serazeni
* @param aux pomocne pole (stejne velikosti jako razene)
* @param left prvni index, na ktery smim sahnout
* @param right posledni index, na ktery smim sahnout
*/
void merge(int array[], int aux[], int left, int right) {
int middleIndex = (left + right)/2;
int leftIndex = left;
int rightIndex = middleIndex + 1;
int auxIndex = left;
while (leftIndex <= middleIndex && rightIndex <= right) {
if (array[leftIndex] >= array[rightIndex]) {
aux[auxIndex] = array[leftIndex++];
} else {
aux[auxIndex] = array[rightIndex++];
}
auxIndex++;
}
while (leftIndex <= middleIndex) {
aux[auxIndex] = array[leftIndex++];
auxIndex++;
}
while (rightIndex <= right) {
aux[auxIndex] = array[rightIndex++];
auxIndex++;
}
}
/**
* Razeni slevanim (od nejvyssiho)
* @param array pole k serazeni
* @param aux pomocne pole stejne delky jako array
* @param left prvni index na ktery se smi sahnout
* @param right posledni index, na ktery se smi sahnout
*/
public static void MergeSort(int[] array, int[] aux, int left, int right)
{
if (left == right) return;
int middleIndex = (left + right) / 2;
MergeSort(array, aux, left, middleIndex);
MergeSort(array, aux, middleIndex + 1, right);
Merge(array, aux, left, right);
for (int i = left; i <= right; i++)
{
array[i] = aux[i];
}
}
/**
* Slevani pro Merge sort
* @param array pole k serazeni
* @param aux pomocne pole (stejne velikosti jako razene)
* @param left prvni index, na ktery smim sahnout
* @param right posledni index, na ktery smim sahnout
*/
private static void Merge(int[] array, int[] aux, int left, int right)
{
int middleIndex = (left + right) / 2;
int leftIndex = left;
int rightIndex = middleIndex + 1;
int auxIndex = left;
while (leftIndex <= middleIndex && rightIndex <= right)
{
if (array[leftIndex] >= array[rightIndex])
{
aux[auxIndex] = array[leftIndex++];
}
else
{
aux[auxIndex] = array[rightIndex++];
}
auxIndex++;
}
while (leftIndex <= middleIndex)
{
aux[auxIndex] = array[leftIndex++];
auxIndex++;
}
while (rightIndex <= right)
{
aux[auxIndex] = array[rightIndex++];
auxIndex++;
}
}
Vezmeš dvě (sousední) posloupnosti (o kterých již víš, že jsou seřazené) a ukážeš na jejich první prvky. Do pomocného pole poté postupně vyskládáváš všechny prvky z obou posloupností dle jejich velikosti. Tím získáš posloupnost, která obsahuje všechny prvky obou slévaných podposloupností a je seřazená. Nakopíruješ ji zpět do původního pole a pokračuješ ve slévání.
Tj. v předposledním kroku máš dvě posloupnosti 8 7 5, 9 6 4 a řadíš od největšího...vytvoříš si pomocné pole velikosti 6. Ukážeš na první prvky obou posloupností a řikáš si:
8 < 9, devítku uložíš do pomocného pole, a v posloupnosti posuneš ukazatel na další prvek. Tj. pomocné pole obsahuje 9
8 > 6, pomocné pole: 9 8
7 > 6, pomocné pole: 9 8 7
5 < 6, pomocné pole: 9 8 7 6
5 > 4, pomocné pole: 9 8 7 6 5
první posloupnost je prázdná, dosypeme do pomocného pole zbytek druhé posloupnosti (který je seřazený, tudíž nemůže řazení rozházet) - pomocné pole 9 8 7 6 5 4. Na závěr vezmeš toto pomocné pole a překopíruješ ho zpět do původního pole (a řadíš dál, pokud je ještě co).