Vajíčková mánie Vajíčková mánie
Vyšlehej si extra vědomosti! Až 100% bodů na prémiový obsah zdarma! Více zde

Quick sort

Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem.
Vydávání, hosting a aktualizace umožňují jeho sponzoři.

Jak již název napovídá, Quicksort je rychlý. On je dokonce nejrychlejší a je to algoritmus, který se skutečně používá v praxi k třídění prvků, proto bude tento článek o něco obsáhlejší, než ostatní. Chová se dobře jak na malých, tak na velkých polích a je paměťově nenáročný. Algoritmus je založen na principu rozděl a panuj, který jsme si již vysvětlili v algoritmu Merge sort.

Quicksort si označí jeden prvek v poli jako tzv. pivot. Výběrem pivotu se prozatím nebudeme zabývat a budeme jako pivot brát vždy první prvek v poli. Nyní zavoláme funkci divide (rozděl), která přeuspořádá pole tak, aby byly zleva prvky menší než pivot, poté následovat pivot sám a za pivotem byly prvky větší, než je on sám. Povšimněte si, že jsem napsal přeuspořádá, nikoli setřídí. Prvky jsou tedy mezi sebou stále rozházené a jediné setřídění spočívá v jejich rozdělení pivotem. Tuto operaci jsme schopni zvládnout v lineárním čase a také velmi rychle. Nyní algoritmus rekurzivně zavoláme na levou polovinu pole před pivotem a na pravou polovinu za pivotem (pivota už necháme tam, kde je). S těmi provedeme to samé, jako s původním polem a takto budeme pokračovat až do chvíle, kdy na vstupu dostaneme jednotkové pole (pole velikosti 1). Po vynoření z rekurze nemusíme dělat už vůbec nic, pole je setříděné. Nyní si algoritmus předvedeme v praxi a řekneme si více o funkci rozděl.

Průběh

Protože Quicksort je velmi rychlý, předvedeme si ho tentokrát na poli o trochu větším, než obvykle, abychom z něj něco vůbec viděli :)
Máme tedy pole následujících prvků:

5 2 9 3 5 1 8

Jako pivot si vybereme první prvek (5).

5 2 9 3 5 1 8

Nyní na pole zavoláme funkci divide. Funkce si jako první uloží pivot na konec pole, aby nepřekážel a také abychom se na něj mohli snadno odkazovat. Udělá to jednoduchým prohozením pivota s posledním prvkem.

8 2 9 3 5 1 5

Nyní si budeme držet pozici, od které začínají prvky větší, než je pivot (tedy pozice prvního většího prvku, než je pivot, dále už jen pozice). Protože jsme na začátku, bude mít hodnotu 0. Pole nyní projedeme cyklem od začátku do předposledního prvku (protože poslední je pivot). Pokud je prvek v poli menší, než je pivot, prohodí se s prvkem na pozici. Protože v tu chvíli se počet prvků menších než pivot zvětší, musíme i pozici zvýšit o 1. Až dojedeme do cíle, prohodíme samotný pivot s pozicí (jeden z větších prvků se tedy dostane na konec a pivot sám bude vymezovat obě části pole). Protože se pozice pivotu jistě posune (těžko bude zase na začátku, když jsme před něj navkládali menší prvky), musí tuto novou pozici funkce divide vrátit, aby s ním Quicksort mohl dále pracovat. V následující vizualizaci algoritmu budu pozici znázorňovat jako tečku.

.8 2 9 3 5 1 5

V našem poli tedy začneme prvním prvkem (8), pozici máme také na začátku. Protože prvek 8 je jistě větší než pivot (5), necháme ho na místě, s pozicí nebudeme hýbat a přistoupíme k dalšímu prvku (2).

.8 2 9 3 5 1 5

2 je jistě menší než 5, proto prvek prohodíme s prvkem na pozici (tedy prvek 2 se prohodí s prvkem 8 ) a pozici posuneme o 1 doprava. Přistoupíme k dalšímu prvku (9).

2 .8 9 3 5 1 5

9 necháme na místě (9 > 5) a přistoupíme k prvku 3.

2 .8 9 3 5 1 5

3 < 5, prohodíme, zvýšíme pozici, jdeme na prvek 5.

2 3 .9 8 5 1 5

5 není menší než 5, necháme být a jdeme ne poslední prvek 1.

2 3 .9 8 5 1 5

1 < 5, prohodíme, zvýšíme.

2 3 1 .8 5 9 5

Nakonec pivot prohodíme s prvkem na pozici.

2 3 1 5 5 9 8

Takhle tedy vypadá pole po zavolání funkce divide, nesmíme zapomenout vrátit pozici, aby Quicksort věděl, kde je nyní pivot. Všimněte si, že výsledek nemá se setříděným polem moc společného, pole se pouze rozdělilo na dvě části pomocí pivotu. Takto nám v podstatě vznikla 2 další pole a to [2, 3, 1] a [5, 9, 8]. Nyní se "rozdvojíme" a pustíme Quicksort na obě vzniklá pole (tedy přesněji na 2 části původního pole, nová pole v podstatě nevznikla, jen se na situaci tak můžeme dívat). Nejprve zpracujeme to první, druhá větev bude zatím chvíli čekat. Původní pole nám samozřejmě nezmizí, jen si budeme všímat jen jeho části a proto bude zbytek znázorněn šedě.

Vybereme pivota (2)

2 3 1 5 5 9 8

Zavoláme na část pole funkci divide, výsledek bude vypadat takto:

1 2 3 5 5 9 8

Když nyní pole opět rozdělíme, dostaneme 2 jednoprvková pole a to [1] a [3]. To je přesně to, čeho jsme chtěli dosáhnout, protože jednoprvkové pole považujeme za triviálně setříděné. Quicksort již na jednoprvkové pole volat funkci divide nebude a levá polovina pole je hotová. Vynoříme se tedy z rekurze a přejdeme k pravé polovině, která na nás zatím čekala. Vybereme pivota, tedy prvek 5.

1 2 3 5 5 9 8

Po zavolání funkce divide se jistě nic nezmění, pivot zůstane na začátku a oba prvky jsou větší než on. Moc si tedy nepomůžeme a pole se nám zkrátí jen o pivot. V nové části pole vybereme pivot (9).

1 2 3 5 5 9 8

Funkce divide vrátí následující výsledek:

1 2 3 5 5 8 9

Jednoprvkové pole ([8]) považujeme za setříděné. Vynoříme se z rekurze a pole je setříděné. Na další třídění se můžete podívat na videoukázce.

1 2 3 5 5 8 9

Video ukázka

Časová složitost

Ohledně stability musím dodat, že zde uvedená funkce divide pro jednoduchost není stabilní. Lze ji však napsat tak, aby stabilní byla. Jak je to však s časovou složitostí? Již jsem se zmínil, že funkce rozděl probíhá v lineárním čase, její časová složitost je tedy O(n). Kolikrát se však provádí? Na to není jednoznačná odpověď a pokud očekáváte háček, očekáváte správně. V ideálním případě nám funkce divide pole rozdělí na 2 stejné poloviny. Když něco dělíme na poloviny, složitost bude jistě dvojkový logaritmus, tedy O(log n). A protože samotné dělení trvá O(n), složitost celého algoritmu by v tomto případě byla naše oblíbené O(n log n). Je dokázáno, že Quicksort má i v průměrném případě opravdu tuto složitost, i když poloviny nejsou vždy přesně dodrženy.

Jak již to bývá, extrémní rychlost Quicksortu je vykoupena špatným chováním algoritmu na již předtříděných polích. Zatím co Bubblesort si na předtříděných polích liboval, Quicksort vybere jako pivot první prvek (tedy nejmenší nebo největší číslo) a funkce rozděl pak logicky před pivota už žádný prvek nadá. Nové pole je tedy vždy menší jen o jeden jediný prvek a druhé pole se vůbec nevytvoří. Složitost nám spadne na O(n2). S tímto problémem souvisí i hackerské útoky na informační systémy. Představte si, že víte, že nějaká firma třídí data v databázi pomocí Quicksortu, který vybírá jako pivota vždy první prvek. Stačí jim poslat tisíce setříděných polí, jejich algoritmus se náhle propadne na časovou složitost O(n2) a protože server s takovou zátěží nepočítá, tak spadne. Tento problém lze však poměrně snadno vyřešit, nicméně je velmi důležité vědět, že existuje.

Variace Quicksortu

Vybírat první prvek tedy asi není úplně nejlepší nápad. Když vybereme poslední, problém bude úplně stejný. Nabízí se nejjednodušší řešení: vybereme prvek prostřední nebo třeba vždy prvek ve 2/3 pole. Útočníka sice zmateme, ale když bude znát naše zdrojové kódy, dokáže opět vyrobit taková pole, aby složitost algoritmu spadla na O(n2).

Dalším řešením by mohlo být vybrat vždy medián a z něj udělat pivot. Pole bychom tak dělili vždy přesně na 2 poloviny. Dokonce i existuje algoritmus, který je schopný najít medián v lineárním čase. Takový Quicksort by měl potom zaručenou asymptotickou časovou složitost opravdu O(n log n). V praxi však bohužel hledání mediánu algoritmus natolik zpomalí, že se pak tuto variantu nevyplatí použít.

Co kdybychom pivot prostě vybírali náhodně? Trefa, této verzi se říká Randomizovaný Quicksort. V praxi výběr náhodného čísla algoritmus časově příliš nezatíží. Prakticky však náhodné číslo neexistuje. Čísla, která generuje počítač, se nazývají pseudonáhodná čísla. Softwarové náhodné generátory totiž většinou pracují se systémovým časem a číselnými řadami. Např. unixové systémy jsou známé tím, že jejich generátory využívají šum ze zvukové karty nebo teploty procesoru. Generátory používané například pro armádní kryptografii mohou využívat štěpení izotopů a podobných jevů. Ale zpět k randomizovanému quicksortu - v 99% případů se jedná o naprosto spolehlivý a rychlý algoritmus. Prakticky je nenapadnutelný, i když teoreticky náhodné číslo neexistuje. Kdyby to však náhodou někomu nestačilo, existuje ještě další varianta quicksortu: Introsort.

Introsort je Quicksort, který nemusí být ošetřený proti napadení a může tedy vybírat jako pivot hned první prvek. Navíc si však bude počítat, jak hluboké je zanoření rekurze. Pokud přesáhne log n, přepne se Quicksort na Heapsort a zbytek pole je setříděný Heapsortem, který má zaručenou složitost O(n log n) na jakémkoli poli. Introsort se v praxi vyskytuje velmi často a je to tedy již pravý algoritmus, kterým většina programů třídí svá data.

Vlastnosti algoritmu

Časová složitost O (n log n) pro průměrný případ, O (n2)
Stabilita Může být implementován stabilně
Rychlost Velmi vysoká

Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům.

Zdrojové kódy

// preusporada pole na prvky mensi nez pivot, pivot a prvky vetsi nez pivot
public static int divide(int[] list, int left, int right, int pivot) {
  int temp = list[pivot]; // prohozeni pivotu s poslednim prvkem
  list[pivot] = list[right];
  list[right] = temp;
  int i = left;
  for (int j = left; j < right; j++) {
    if (list[j] < list[right]) { // prvek je mensi, nez pivot
      temp = list[i]; // prohozeni pivotu s prvkem na pozici
      list[i] = list[j];
      list[j] = temp;
      i++; // posun pozice
    }
  }
  temp = list[i]; // prohozeni pivotu zpet
  list[i] = list[right];
  list[right] = temp;
  return i; // vrati novy index pivotu
}

public static void limited_quicksort(int[] list, int left, int right) {
  if (right >= left) { // podminka rekurze
    int pivot = left; // vyber pivotu
    int new_pivot = divide(list, left, right, pivot);
    // rekurzivni zavolani na obe casti pole
    limited_quicksort(list, left, new_pivot - 1);
    limited_quicksort(list, new_pivot + 1, right);
  }
}

// zavola omezeny quicksort na cele pole
public static void quicksort(int[] list) {
  limited_quicksort(list, 0, list.length - 1);
}
// preusporada pole na prvky mensi nez pivot, pivot a prvky vetsi nez pivot
public static int divide(int[] list, int left, int right, int pivot) {
  int temp = list[pivot]; // prohozeni pivotu s poslednim prvkem
  list[pivot] = list[right];
  list[right] = temp;
  int i = left;
  for (int j = left; j < right; j++) {
    if (list[j] < list[right]) { // prvek je mensi, nez pivot
      temp = list[i]; // prohozeni pivotu s prvkem na pozici
      list[i] = list[j];
      list[j] = temp;
      i++; // posun pozice
    }
  }
  temp = list[i]; // prohozeni pivotu zpet
  list[i] = list[right];
  list[right] = temp;
  return i; // vrati novy index pivotu
}

public static void limited_quicksort(int[] list, int left, int right) {
  if (right >= left) { // podminka rekurze
    int pivot = left; // vyber pivotu
    int new_pivot = divide(list, left, right, pivot);
    // rekurzivni zavolani na obe casti pole
    limited_quicksort(list, left, new_pivot - 1);
    limited_quicksort(list, new_pivot + 1, right);
  }
}

// zavola omezeny quicksort na cele pole
public static void quicksort(int[] list) {
  limited_quicksort(list, 0, list.Length - 1);
}
// preusporada pole na prvky mensi nez pivot, pivot a prvky vetsi nez pivot
function divide(var list: array of integer; left, right, pivot: integer): integer;
var temp, i, j: integer;
begin
  temp:=list[pivot]; // prohozeni pivotu s poslednim prvkem
  list[pivot]:=list[right];
  list[right]:=temp;
  i:=left;
  for j:=left to right do
  if (list[j] < list[right]) then begin // prvek je mensi, nez pivot
    temp:=list[i]; // prohozeni pivotu s prvkem na pozici
    list[i]:=list[j];
    list[j]:=temp;
    inc(i); // posun pozice
  end;
  temp:=list[i]; // prohozeni pivotu zpet
  list[i]:=list[right];
  list[right]:=temp;
  result:=i; // vrati novy index pivotu
end;

// quicksort omezeny na urcitou cast pole
procedure limited_quicksort(var list: array of integer; left, right: integer);
var pivot, new_pivot: integer;
begin
  if (right >= left) then begin // podminka rekurze
    pivot:=left; // vyber pivotu
    new_pivot:=divide(list, left, right, pivot);
    // rekurzivni zavolani na obe casti pole
    limited_quicksort(list, left, new_pivot - 1);
    limited_quicksort(list, new_pivot + 1, right);
  end;
end;

// zavola omezeny quicksort na cele pole
procedure quicksort(var list: array of integer);
begin
  limited_quicksort(list, 0, length(list) - 1);
end;
# preusporada pole na prvky mensi nez pivot, pivot a prvky vetsi nez pivot
def divide(list, left, right, pivot)
  temp = list[pivot] # prohozeni pivotu s poslednim prvkem
  list[pivot] = list[right]
  list[right] = temp
  i = left
  left.upto(right) do |j|
    if (list[j] < list[right]) # prvek je mensi, nez pivot
      temp = list[i] # prohozeni pivotu s prvkem na pozici
      list[i] = list[j]
      list[j] = temp
      i += 1 # posun pozice
    end
  end
  temp = list[i] # prohozeni pivotu zpet
  list[i] = list[right]
  list[right] = temp
  return i # vrati novy index pivotu
end

# quicksort omezeny na urcitou cast pole
def limited_quicksort(list, left, right)
  if (right >= left) # podminka rekurze
    pivot = left # vyber pivotu
    new_pivot = divide(list, left, right, pivot)
    # rekurzivni zavolani na obe casti pole
    limited_quicksort(list, left, new_pivot - 1)
    limited_quicksort(list, new_pivot + 1, right)
  end
end

# zavola omezeny quicksort na cele pole
def quicksort(list)
  limited_quicksort(list, 0, list.length - 1)
end

 

 

Článek pro vás napsal David Čápka
Avatar
Jak se ti líbí článek?
6 hlasů
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor sítě se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Předchozí článek
Merge Sort
Všechny články v sekci
Třídící/řadící algoritmy
Miniatura
Následující článek
Dolní odhad složitosti problému třídění
Aktivity (3)

 

 

Komentáře
Zobrazit starší komentáře (5)

Avatar
Filistin
Člen
Avatar
Filistin:31.5.2015 17:16

Mockrát děkuju. Moc mi to pomohlo. Hlavně ten postup s obrázkama na začatku.

 
Odpovědět 31.5.2015 17:16
Avatar
d.novy
Člen
Avatar
d.novy:16.11.2016 13:08

Když to pustím na pole o velikosti 10000, tak mi to vrací chybu.

Exception in thread "main" java.lang.Stac­kOverflowError
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:78)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)

Tj. zde

int new_pivot = divide(list, left, right, pivot, debug);
// rekurzivni zavolani na obe casti pole
limited_quicksor­t(list, left, new_pivot - 1, debug);
limited_quicksor­t(list, new_pivot + 1, right, debug);

D.

 
Odpovědět 16.11.2016 13:08
Avatar
Luboš Běhounek Satik
Autoredaktor
Avatar
Odpovídá na d.novy
Luboš Běhounek Satik:16.11.2016 14:50

Můžeš buďto zvětšit stack a nebo lepší a čistší řešení je přepsat rekurzi na cyklus.

Editováno 16.11.2016 14:50
Odpovědět  +1 16.11.2016 14:50
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Kún
Člen
Avatar
Lukáš Kún:29.11.2017 0:28

Moje C# verze bez rekurze:

public static T[] QuickSort<T>(T[] pole)
            where T : IComparable<T>
        {
            Random rnd = new Random();

            int[] lims = new int[pole.Length];
            int li = -1;

            lims[++li] = 0;
            lims[++li] = pole.Length - 1;

            while (li > 0)
            {
                int p = lims[li--];
                int l = lims[li--];
                int prv = l;
                int pos = p;

                Swap(pole, pos, rnd.Next(l, p));

                while (l < p)
                {
                    if (pole[l].CompareTo(pole[pos]) == 1)
                        Swap(pole, l, --p);
                    else
                        l++;
                }

                Swap(pole, pos, p);

                if (pos - prv > 1)
                {
                    if (p < pos)
                    {
                        lims[++li] = p + 1;
                        lims[++li] = pos;
                    }
                    if (prv < p)
                    {
                        lims[++li] = prv;
                        lims[++li] = p - 1;
                    }
                }
            }

            return pole;
        }

static void Swap<T>(T[] pole, int i1, int i2)
        {
            T tmp = pole[i1];
            pole[i1] = pole[i2];
            pole[i2] = tmp;
        }

Testováno celkem dlouho testem generujícím náhodně dlouhá pole s náhodnými čísly - vše prošlo, tak snad by to mělo fungovat. Ovšem nejsem žádný profík, takže kdo ví :D

Případné námitky rád uvítám.

 
Odpovědět 29.11.2017 0:28
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:24.4.2018 16:08

Časová složitost - Tady zalezi na kodu algoritmu. Bezny quick sort na O(n*n) pro opacne serazene pole cisel (desc). Cili, mate z nej bubble sort. Pro normalni zamichani je obvykle stejne rychly jako modifikovany merge sort. Mozna o neco rychlejsi.

 
Odpovědět 24.4.2018 16:08
Avatar
Patrik Pastor:Včera 14:28

proc se nepouziva casteji merge sort, kdyz ma stejnou rychlost i stabilitu, ale navic je u nej 100% ze bude mit slozitos O {n*log(n)}, narozdil od quick sortu, kde to muze spadnout na n2

 
Odpovědět Včera 14:28
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Patrik Pastor
David Čápka:Včera 15:09

Merge sort a quicksort mají stejnou časovou složitost. To znamená, že od určitého počtu prvků jsou stejně rychlé. Na malých polích ale quicksort vychází lépe a proto je to nejčastěji volený algoritmus.

Odpovědět  +1 Včera 15:09
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
Odpovídá na David Čápka
Patrik Pastor:Včera 21:14

jak se vlastne ta slozitos meri? resp. kdyz rikas, ze na male pole je quicksort rychlejsi nez merge, rikas tim o kolik milisekund se provede trideni rychleji? nebo jakym zpusobem se meri (resp co je vysledek mereni), a jake jednotky. dik

 
Odpovědět Včera 21:14
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Patrik Pastor
patrik.valkovic:Včera 21:39

Ahoj. Složitost se měří obecně (jako abstrakce slouží Turingův stroj, ale to je už trochu komplikované). Obecně se vezme časově nejnáročnější operace (což je v tomto případě porovnání / přesun prvků) a počítá se, kolikrát je operace provedena.
Dále můžeš rozlišovat složitost v nejlepším případě, v nejhorším případě a v průměru. Dále existuje i složitost asymptotická (průměrná složitost při velkém množství operací, ale ta se u třídících algoritmů moc nepoužívá).
Složitost neudává nic o reálné rychlosti. Na některém stroji může běžet sekundu a na některém minutu. Důležité je, že pro velké množství prvků, bude vždy O(n*log n) lepší než O(n2). Pro příklad seřazení 10 hodnot trvá bubblesortem 10ms a quicksortem 20ms. Ale pro 10000 hodnot to bude bubblesortem 10000ms a quicksortem 1000ms (čísla jsem si vymyslel).
Jak říkáš, quicksort je v průměrném případě nejlepší třídící algoritmus, ale v nejhorším je složitost n2, proto většina implementací má tzv. fallback, který přepne na jiný třídící algoritmus, pokud se situace zdá být špatná.
Mergesort má nevýhodu, že není inplace, tedy potřebuješ alokovat větší paměťové místo (tj. má paměťovou složitost větší než quicksort), ale je stabilní.
Mergesort lze dále použít pro spojové seznamy (poté lze přepsat na inplace verzi) a pro třídění velkých dat (jelikož nemusí být všechny data uložené v paměti.
Quicksort je by default nestabilní (lze implementovat i stabilní verzi) a je inplace.
Třetím často používaným algoritmem je heapsort, která není stabilní, ale je zaručena složitost O(n*log n). V průměru má o něco horší složitost než pro quicksort (má vyšší konstantu složitosti).
Výběr ideálního třídícího algoritmu tedy závisí na situaci.

Odpovědět  +1 Včera 21:39
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Odpovídá na patrik.valkovic
Patrik Pastor:Včera 21:48

fakt moc diky za takove lidi. Ted je mi to zase o neco vice jasnejsi. Rad bych se prece jen jeste zeptal (snad uz nepusobim doterne, vim, hodne se ptam), na onu stabilitu. Tedy rozdil mezi stabilni a nestabilni nebo jak to co to vlastne je (kdyz pises, ze quicksort je defaulnute nestabilno, ale da se stabilizovat). a za 2) u mergesort rozumim spojovym zaznamum (ktera se na sebe referuji), ale nerozumim, jak to, ze by data nemusela byt ulozena v pameti, jak jinak by k nim mel pristup (prece i ty zaznamy jsou fyzicky v pameti). Jinak jeste jednou diky za vysvetleni

 
Odpovědět Včera 21:48
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 15. Zobrazit vše