Domů / ... / Řadící algoritmy / Merge sort

/**
 * Implementace algoritmu merge sort.
 * @param pole pole k seřazení
 * @author Vojtěch Hordějčuk
 */
public static <T extends Comparable<? super T>> void mergeSort (final T pole[])
{
  // vytvoř dočasné pole o stejné velikosti
  T pracovni[] = new T[pole.length];

  // spusť rekurzivní řazení pro celé pole
  mergeSort (pole, pracovni, 0, pole.length - 1);
}

/**
 * Hlavní metoda pro rekurzivní řazení.
 * @param pole pole k seřazení
 * @param pracovni pracovní pole o stejné velikosti
 * @param prvni index prvního prvku
 * @param posledni index poslední prvku
 * @author Vojtěch Hordějčuk
 */
private static <T extends Comparable<? super T>> void mergeSort (final T pole[], final T pracovni[], int prvni, int posledni)
{
  // řadit je nutné pouze část pole s více než jedním prvkem
  if (prvni != posledni)
  {
    // vypočítej index středu
    int stredni = (prvni + posledni) / 2;

    // seřaď levou polovinu (včetně středu)
    mergeSort (pole, pracovni, 0, stredni);

    // seřaď pravou polovinu (bez středu)
    mergeSort (pole, pracovni, stredni + 1, posledni);

    // slij obě seřazené poloviny dohromady do neklesajícího pořadí
    merge (pole, pracovni, prvni, stredni, posledni);

    // zkopíruj pracovní pole do původního
    for (int i = prvni; i <= posledni; i ++)
    {
      pole[i] = pracovni[i];
    }
  }
}

/**
 * Metoda pro slévání dvou seřazených částí pole do pole pracovního.
 * @param pole pole k seřazení (vstup)
 * @param pracovni pracovní pole o stejné velikosti (výstup)
 * @param prvni index prvního prvku
 * @param stredni index středního prvku
 * @param posledni index posledního prvku
 * @author Vojtěch Hordějčuk
 */
private static <T extends Comparable<? super T>> void merge (final T pole[], final T pracovni[], int prvni, int stredni, int posledni)
{
  // nastav index výsledného pole na začátek levé poloviny
  int indexFinal = prvni;

  // nastav levý index na začátek levé poloviny
  int indexLevy = prvni;

  // nastav pravý index na začátek pravé poloviny
  // index je roven polovině plus jedna, protože střed patří do levé poloviny
  int indexPravy = stredni + 1;

  while (indexLevy <= stredni && indexPravy <= posledni)
  {
    if (pole[indexLevy].compareTo (pole[indexPravy]) <= 0)
    {
      // ulož menší prvek z levé poloviny a posuň ukazatele
      pracovni[indexFinal ++] = pole[indexLevy ++];
    }
    else
    {
      // ulož menší prvek z pravé poloviny a posuň ukazatele
      pracovni[indexFinal ++] = pole[indexPravy ++];
    }
  }

  // zkopíruj zbývající prvky z levé části pole
  while (indexLevy <= stredni)
  {
    pracovni[indexFinal ++] = pole[indexLevy ++];
  }

  // zkopíruj zbývající prvky z pravé části pole
  while (indexPravy <= posledni)
  {
    pracovni[indexFinal ++] = pole[indexPravy ++];
  }
}

% ROZDĚLOVÁNÍ
% ===========

% triviální případy
divide([],[],[]).
divide([A],[A],[]).
% první prvek seznamu vložit na začátek druhého, druhý prvek na začátek třetího, poté rekurzivně zopakovat se zbytkem seznamu
divide([H1,H2|T],[H1|T1],[H2|T2]) :- divide(T,T1,T2).

% SLÉVÁNÍ
% =======

% triviální případy
merge(A,[],A).
merge([],A,A).
% je-li prvek H1 menší nebo roven H2, vložit jej na začátek seznamu a rekurzivně opakovat
merge([H1|T1],[H2|T2],[H1|Y]) :- H1 =< H2,merge(T1,[H2|T2],Y).
% je-li prvek H1 větší než H2, vložit jej na konec seznamu a rekurzivně opakovat
merge([H1|T1],[H2|T2],[H2|Y]) :- H1 > H2,merge([H1|T1],T2,Y).

% ŘAZENÍ
% ======

% triviální případy
sorter([],[]).
sorter([A],[A]).
% zajistit správné pořadí dvojice prvků
sorter([A,B],[A,B]) :- A =< B.
sorter([A,B],[B,A]) :- A > B.
% obecný případ - rozdělit pole na dvě části, seřadit je a poté spojit dohromady
sorter(A,B) :- divide(A,P1,P2),sorter(P1,R1),sorter(P2,R2),merge(R1,R2,B).