Merge sort
Mergesort je řadící algoritmus na principu slévání již seřazených částí pole, který vymyslel v roce 1945 John von Neumann. Mergesort je stabilní algoritmus s asymptotickou složitostí . Nevýhodou mergesortu je potřeba pomocného pole velikosti n.
Princip
Předpokládejme, že máme dva seřazené seznamy (řazené od největšího po nejmenšího). Vytvoření seřazeného celku je poměrně jednoduché – vybereme vždy z obou částí ten prvek, jenž je nejvyšší a uložíme jej do nového (pomocného) seznamu (z původního seznamu jej odstraníme). Takto postupujeme, dokud se jeden z původních seznamů nevyprázdní. Až se tak stane, tak přidáme na konec nového seznamu zbylé prvky druhé části.
Nyní vyvstává otázka, jak získat ony dvě seřazené části. Odpovědí je rekurze a organizovanané rozkládání a skládání pole. Vezmeme původní pole a rozdělíme jej na poloviny a toto zopakujeme pro obě poloviny pole. Tímto se dostaneme až k elementárnímu případu - jednomu prvku - který je triviálně seřazen. Při návratu z rekurze již jen sléváme obě poloviny pomocí procedury, kterou jsme si popsali výše.
Implementace slévání
Z implementačního hlediska je zapotřebí naprogramovat samotné slévání efektivně. Proto budeme při celém řazení používat pouze jedno pomocné pole velikosti n. Pokud budeme řadit dva úseky pole, z nichž ten první začíná na indexu i, tak si vytvoříme ukazatele na čela jednotlivých seznamů a ukazatel do pomocného pole. Vždy provedeme operaci porovnání čel obou seznamů a vybereme ten prvek, který má vyšší hodnotu. Tento prvek překopírujeme do pomocného pole, a posuneme jak ukazatel příslušného pole, tak ukazatel pole pomocného. V okamžiku, kdy je již jedno pole vyčerpáno, dokopírujeme do pomocného pole zbytek prvků druhého seznamu. V tento okamžik vezmeme celé pomocné pole a překopírujeme jej zpět do původního pole (s počátkem na indexu i)
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++;
}
}
