searchable.searchsequence

## Class QuickSortedSearchSequence

- java.lang.Object
- - searchable.searchsequence.SearchSequence
  - - searchable.searchsequence.SearchSequenceWithOrderedSelect
    - - searchable.searchsequence.SortedSearchSequence
      - - searchable.searchsequence.QuickSortedSearchSequence

- All Implemented Interfaces:
    Searchable, SearchableWithMedian

      class QuickSortedSearchSequence
      extends SortedSearchSequence
      implements Searchable

  Implementace vyhledávací posloupnosti seřazené quicksortem.

  Popis: Operace insert je rychlá, ale může narušit seřazení prvků v posloupnosti. Proto před operacemi select, update nebo remove, které následují po operaci insert, musíme seřadit posloupnost. K tomu slouží metoda sort.

  Užití: instance této třídy lze používat v aplikacích

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `private class` | `QuickSortedSearchSequence.Parts` Strukturovaný výsledek metody partition.

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `private int` | `moveCnt` počítadlo provozního měření

    - ### Fields inherited from class searchable.searchsequence.SortedSearchSequence

      `isSorted, sortCounter`

    - ### Fields inherited from class searchable.searchsequence.SearchSequence

      `sequence`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `QuickSortedSearchSequence(SortableSequenceFactory aFactory, int aSize)` Vyrobí instanci vyhledávací posloupnosti QuickSortedSearchSequence.

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `private void` | `median(ShallowSequence segment, int offset)` Pomocná metoda na hledání mediánu.
    `private QuickSortedSearchSequence.Parts` | `partition(ShallowSequence segment)` Rozdělí úsek posloupnosti na dva úseky podle pivota.
    `private void` | `quick(ShallowSequence segment)` Rekurzivní část metody sort.
    `SearchableElement` | `selectMedian()` Najde medián.
    `protected int` | `sort()` Seřadí prvky posloupnosti vzestupně podle klíčů.

    - ### Methods inherited from class searchable.searchsequence.SortedSearchSequence

      `getSortCounter, insert, remove, select, update`

    - ### Methods inherited from class searchable.searchsequence.SearchSequenceWithOrderedSelect

      `orderedSelect`

    - ### Methods inherited from class searchable.searchsequence.SearchSequence

      `getCount, getOperationCounter, getReadable, isEmpty, isFull, setSequence`

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

    - ### Methods inherited from interface searchable.searchableinterface.Searchable

      `getCount, getOperationCounter, getReadable, getSortCounter, insert, isEmpty, isFull, remove, select, update`

- - ### Field Detail

    - #### moveCnt

          private int moveCnt

      počítadlo provozního měření

  - ### Constructor Detail

    - #### QuickSortedSearchSequence

          public QuickSortedSearchSequence(SortableSequenceFactory aFactory,
                                           int aSize)

      Vyrobí instanci vyhledávací posloupnosti QuickSortedSearchSequence.

      Popis: inicializuje atributy instance.

      Parameters:
        `aFactory` - továrna na seřaditelné posloupnosti
        `aSize` - kapacita seřaditelné posloupnosti

  - ### Method Detail

    - #### partition

          private QuickSortedSearchSequence.Parts partition(ShallowSequence segment)

      Rozdělí úsek posloupnosti na dva úseky podle pivota.

      Popis: za pivota zvolí první prvek posloupnosti. Tato funkce má výpočetní složitost O(n). To je klíč k efektivitě Quicksortu.

      Mění: změní
      `moveCnt -` tam počítá přesuny prvků (provozní měření)
      `upper -` tam vytvoří úsek z prvků větších než pivot
      `lower -` tam vytvoří úsek z prvků menších než pivot

      Parameters:
        `segment` - úsek, který se dělí
      Returns:
        struktura se složkami lower a upper

    - #### quick

          private void quick(ShallowSequence segment)

      Rekurzivní část metody sort. Seřadí prvky mělké posloupnosti segment vzestupně podle klíčů.

      Popis: Quciksort vybere pivota, podle kterého rozdělí pole na úsek menších a větších prvků; pak seřadí oba úseky stejným postupem. Není stabilní!

      Mění: změní pořadí prvků v posloupnosti.

      Parameters:
        `segment` - mělká posloupnost prvků, které se mají seřadit.

    - #### sort

          protected int sort()

      Seřadí prvky posloupnosti vzestupně podle klíčů.

      Popis: Quciksort: vybere pivota, podle kterého rozdělí pole na úsek menších a větších prvků; pak seřadí oba úseky stejným postupem. Není stabilní!

      Mění: změní pořadí prvků v posloupnosti.

      Specified by:
        `sort` in class `SortedSearchSequence`
      Returns:
        počet kroků potřebných k seřazení posloupnosti

    - #### median

          private void median(ShallowSequence segment,
                              int offset)

      Pomocná metoda na hledání mediánu. Viz selectMedian.
      Parameters:
        `segment` - úsek posloupnosti, kde leží medián
        `offset` - umístění úseku v posloupnosti sequence

    - #### selectMedian

          public SearchableElement selectMedian()

      Najde medián.

      Popis: Vybere prostřední prvek ze seřazené posloupnosti modifikovaným quicksortem.

      POZOR: není stabilní!

      Poznámka: Medián je prostřední prvek z posloupnosti nebo jiné uspořádané struktury. V případě sudého počtu prvků není výsledek jednoznačný - je lhostejné, který se najde.

      Specified by:
        `selectMedian` in interface `SearchableWithMedian`
      Overrides:
        `selectMedian` in class `SortedSearchSequence`
      Returns:
        medián posloupnosti