====== 8 - Pole  ======

Toto cvičení je rozdělené na dvě hlavní části. Cílem první části cvičení je vyzkoušet si práci s polem a implementovat třídící altoritmus bubblesort. V druhé části si ukážeme praktické použití při vyhledávání ve světové databázi letišť.


=====Výchozí program v Javě =====

Výchozí zdrojové kódy si stáhněte z archívu: {{:courses:a0b36pr1:labs:pr1-lab08.zip|pr1-lab08.zip}}.

=====Informace k procvičovanému tématu =====

==== Třídicí algoritmy ====

Třídicí neboli řadicí algoritmy slouží k uspořádání množiny prvků do posloupnosti. Existuje celá řada těchto algoritmů (Bubble sort, Insertion sort, Merge sort, Selection sort, Bucket sort, Heap sort...), které se liší nejen implementační náročností, ale také dalším vlastnostmi jako je například výpočetní složitost. Abychom mohli vybrat ten správný algoritmus pro náš konkrétní třídicí problém, můžeme tyto algoritmy posuzovat podle vlasností jako jsou:
  * výpočetní složitost (tj. počet provedených instrukcí nebo potřebná paměť);
  * výkon algoritmu / programu (tj. jeho časová náročnost pro konkrétní vstupy);
  * stabilita algoritmu (řazení je stabilní, pokud nedojde v jeho průběhu k prohození prvků se stejnou hodnotou);
  * implementační náročnost.

<note tip>Doplňující informace na  [[http://cs.wikipedia.org/wiki/%C5%98adic%C3%AD_algoritmus]]</note>

==== Bubblesort ==== 
Bubble sort (bublinkové řazení) je jednoduchý stabilní řadicí algoritmus s asymptotickou složitostí O(n^2). 

Algoritmus porovnává dva sousední prvky, a pokud je nižší číslo nalevo od vyššího, tak je prohodí (nižší číslo je lehčí a rychleji stoupá ke konci pole) a se stejnou logikou pokračuje na dalším indexu. Pokud jsou čísla ve správném pořadí, tak je neprohodí – pouze postoupí dále (algoritmus tím našel lehčí bublinku). Na konci iterace se tímto způsobem na konec pole vždy dostane ta nejlehčí bublinka (nejnižší číslo). Dva příklady vizualizace průběhu řazení jsou uvedeny na obrázcích. Kreativní vizualizaci průběhu algoritmu lze shlédnout na [[https://www.youtube.com/watch?v=lyZQPjUT5B4]].


{{:courses:a0b36pr1:tutorials:08:bubble_sort_animation.gif|}}
{{:courses:a0b36pr1:tutorials:08:bubble-sort-example-300px.gif|}}

Tento princip řazení můžeme realizovat ve dvou variantách:
  * Varianta 1
-Projedeme vždy celé pole: NxN=N^2
  * Varianta 2 (se zarážkou)
- Když víme, že na konci pole bude již správný prvek, tak tento prvek v další iteraci nemusíme kontrolovat. Toto opakujeme.
 (n-1) + (n-2) + (n-3) + ... + (1) krát.
 (Asymptoticky je to ale pořád N^2)

==== Binární vyhledávání ==== 

Abychom vyhledali v poli prvek se zadanou hodnotou, můžeme použít naivní metodu, která projde celé pole a každý prvek porovná se zadanou hodnotou. Tato metoda není příliš efektivní a její časová složitost je O(n).

V případě, že máme pole **seřazené**, můžeme použít rychlejší metodu -- **binární vyhledávání**. Binární vyhledávání porovná prostřední hodnotu v poli s hledanou hodnotou. V případě, že je hledaná hodnota větší, uvažujeme dále pouze druhou polovinu pole (případně první polovinu pole, pokud je hledaná hodnota menší). Dělení pole na dvě přibližně stejné poloviny provádíme, dokud nemá pole délku pouze 1. Algoritmus poté vrátí index hledané hodnoty v poli. Tento algoritmus má logaritmickou časovou složitost O(log(n)). Algorithmus binárního vyhledávání můžeme implementovat například takto:

<code java>
public int binarySearch(T[] array, T value){
  int minIdx = 0;
  int maxIdx = array.length - 1;
  
  while (minIdx < maxIdx) {
    int center = (minIdx + maxIdx) / 2;
    if(value > array[center]){
      minIdx = center + 1; // in interval <center + 1, maxIdx>
    } else {
      maxIdx = center;     // in interval <minIdx, center>
    }
  }
  
  // minIdx = maxIdx
  return (array[minIdx] == value) ? minIdx : -1; // -1 >> not found
}
</code>

<note tip>Doplňující informace na  [[https://en.wikipedia.org/wiki/Binary_search_algorithm]]</note>

=====Průběh cvičení =====

==== Část 1 - Implementace algoritmu bubblesort  ====

V této části budeme používat třídu **Start**, která obsahuje hlavní main metodu. Do třídy **Lab08** se bude implementovat kód ze cvičení.

=== Část 1.1 ===

Naimplementujte příkaz ''printArray()'' ve třídě ''Lab08''. Tento příkaz vypíše na standartní výstup obsah pole ''array'', které se nachází také v této třídě.

<code java>
--- Příklad očekávaného výstupu programu
Element of array at position 0 with value 10
Element of array at position 1 with value 500
Element of array at position 2 with value 8
Element of array at position 3 with value 75
Element of array at position 4 with value 66
Element of array at position 5 with value 2
Element of array at position 6 with value 3
Element of array at position 7 with value 55
Element of array at position 8 with value 100
</code>

=== Část 1.2 ===

Napište program, který realizuje bublinkové třídění (bubblesort) do příkazu bubbleSort(). Pro výměnu prvků naimplementujte příkaz ''swap''. U této první varianty procházejte pole v každém cyklu n-krát (nápověda: n-krát vnitřní cyklus, n-krát vnější cyklus).

<code java>
--- Příklad očekávaného výstupu programu po zavolání bubblesort() a printArray()
Element of array at position 0 with value 500
Element of array at position 1 with value 100
Element of array at position 2 with value 75
Element of array at position 3 with value 66
Element of array at position 4 with value 55
Element of array at position 5 with value 10
Element of array at position 6 with value 8
Element of array at position 7 with value 3
Element of array at position 8 with value 2
</code>

=== Část 1.3 ===

Přepište bubblesort, který jste naimplementovali v části 3 do varianty se zarážkou.

=== Část 1.4 ===

Napište program, který bude realizovat bubblesort jako v předchozích částech, ale tato alternativní implementace projede celé pole jen jednou když už je předem setříděné. Program napište do příkazu adaptedBubbleSort().


==== Část 2 - Vyhledávání v seznamu letišť  ====

V této části si vyzkoušíme příklad, který je motivovám reálným problémem. Představte si, že jste programátor letecké společnosti. Vaším úkolem je napsat program, který rychle odpoví na otázku, jak daleko jsou od sebe dvě zadaná letiště. Tato informace je pro piloty kritická, protože musejí vypočítat správné množství paliva pro svůj let. Databáze obsahuje přes 47 tisíc letišť, a proto by bylo značně neefektivní prohledávat pomocí naivního procházení celého seznamu. Seznam letišť si proto nejprve seřádíme a následně budeme vyhledávat pomocí binárního vyhledávání volacích znaků.

Budeme používat třídu **Airports** z balíčku cz.cvut.fel.pr1.airports, která obsahuje hlavní main metodu a budeme do ní implementovat kód.



=== Část 1.1 ===

Stáhněte si a rozbalte {{:courses:a0b36pr1:labs:airports.tar.gz|databázi letišť}} do projektové složky pomocí kombinace příkazů wget a tar :

<code bash>
wget -qO- https://cw.fel.cvut.cz/wiki/_media/courses/a0b36pr1/labs/airports.tar.gz | tar zxf -
</code>

=== Část 1.2 ===

Připravený kód již obsahuje načtení databáze letišť ze souboru ''airports.csv''. Informace jsou nahrány do čtveřice polí:

<code java>
private String[] names;
private String[] ids;
private double[] latitudes;
private double[] longitudes;
</code>

Spusťte třídu **Airports**. Připravený kód obsahuje naivní metodu vyhledávání (indexOfAirportLinear()). Po spuštění by se měly vypsat vzdálenosti mezi zadanými letišti:

<code java>
...
Distance between LKPR-Ruzyně International Airport and EGLL-London Heathrow Airport is 1044,566252 km
Distance between VHHH-Chek Lap Kok International Airport and YMML-Melbourne International Airport is 7414,594523 km
Distance between KLAX-Los Angeles International Airport and RJTT-Tokyo International Airport is 8814,884564 km
Distance between VYEL-Naypyidaw Airport and FMMI-Ivato Airport is 6819,496274 km
Distance between EBBR-Brussels Airport and CYUL-Montreal / Pierre Elliott Trudeau International Airport is 5555,406762 km
Distance between HUEN-Entebbe International Airport and LKPR-Ruzyně International Airport is 5829,636270 km
The batch took 30125 ms
</code>

Celkem se vyhodnotí 6000 dotazů za přibližně půl minuty.

=== Část 1.3 ===

Pokud chceme zrychlit náš program, můžeme vyzkoušet "profilování". To nám pomůže odhalit, které části programu jsou nejvíce vypočetně náročné. 

Profilování můžeme spustit jednoduše pomocí tlačítka {{:courses:a0b36pr1:labs:lab08-tlacitko.png|}}.


Měli bychom dostat nějaký takovýto výstup:

{{:courses:a0b36pr1:labs:lab08-profiling.png|}}

=== Část 1.4 ===

Implementujte metodu ''swap(i,j)'', která prohodí dvě letiště na seznamu na i-té a j-té pozici. Nezapomeňte, že informace o letišti jsou uloženy ve čtyřech polích, proto je nutné upravit všechny čtyři pole:

<code java>
private void swap(int i, int j) {
  swap(i, j, names);
  swap(i, j, ids);
  swap(i, j, longitudes);
  swap(i, j, latitudes);
}

private void swap(int i, int j, double[] array){
  // TODO
}

private void swap(int i, int j, String[] array){
  // TODO
}
</code>

<note tip>Všimněte si, že používáme tři různé metody se stejným názvem. Kompilátor je rozlišuje podle různého počtu argumentů a jejich datového typu.</note>

=== Část 1.5 ===

Nyní si letiště seřadíme **alfabeticky** podle volacích znaků (pole idx) pomocí algoritmu bubblesort. Při prohazování dvou letišť použijeme metodu ''swap(i,j)''. Pro porovnání dvou textů můžeme použít metodu ''compareTo()''. Pomocí metody compareTo() dokážeme určit, jestli je jeden objekt "větší", ekvivalentní nebo menší než druhý. Pro přesný popis si prostudujte [[https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html|javadoc]].

<code java>
if (ids[i].compareTo(ids[i + 1]) > 0) { // [i] is greater than [i+1]
  swap(i, i + 1);
}
</code>


=== Část 1.6 ===

Implementujte metodu ''indexOfAirportBinary()'' pro binární vyhledávání.

=== Část 1.7 ===

Zkontrolujte výledky a diskutujte časový rozdíl mezi lineárním a binárním vyhledáváním. Pro větší přesnost měření je potřeba vypnout výpis výledků:

<code java>
final boolean useBinary = true/false;
final boolean print = false;
</code>

=====Domácí úkol=====
[[courses:a0b36pr1:hw:lab08|]]