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í zdrojové kódy si stáhněte z archívu: pr1-lab08.zip.

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.

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.

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)

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:

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
}

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í.

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ě.

--- 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

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).

--- 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

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

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().

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áhněte si a rozbalte databázi letišť do projektové složky pomocí kombinace příkazů wget a tar :

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

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

private String[] names;
private String[] ids;
private double[] latitudes;
private double[] longitudes;

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:

...
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

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

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 .

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

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:

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
}

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 javadoc.

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

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

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ů:

final boolean useBinary = true/false;
final boolean print = false;

lab08