Searching and Sorting

Write a Java program to sort an array of integers using binary insertion sort method. Binary insertion method is a modified insertion method that uses binary search to find the insertion point.

public static void binaryInsertionSort (int[] a)

Arrange a competition between different sorting methods:
  1. insertion sort
  2. binary insertion sort (your program)
  3. quicksort
  4. Java API built-in sort
  5. radix sort
Create a long random array of integer elements and provide a copy of the same array to all methods during the competition. Let the size of an array be 64000, 128000, 256000 and 512000 elements (if your computer is slow you can make these numbers smaller but arrange at least four rounds) . Measure the running time of each method for each competition round and put this data into a table in xls ("old" Excel) format. Create a line diagram to illustrate the growth of running time depending on amount of data. All five lines have to be on the same diagram (x-axis: amount of data, y-axis: running time in ms).

Measure only "clean" sorting time, average of several attempts gives even better result.

You have to upload both your program AND your xls-file with the diagram to Moodle in time!

Järjestamine ja otsimine

Koostada meetod juhusliku täisarvumassiivi järjestamiseks kahendpistemeetodil (pistemeetod, milles pistekoht leitakse kahendotsimise abil).

public static void binaryInsertionSort (int[] a)

Need meetodid on loengul käsitletud.

Korraldada "aus võistlus" meetodite vahel, mõõtes lahendamisaega ühe ja sama juhusliku massiivi järjestamiseks erinevate meetoditega: pistemeetodil, kahendpistemeetodil (teie koostatud programm), kiirmeetodil, Java APIs sisalduva meetodiga ja positsioonimeetodil.

Andmemahud olgu näiteks  64000, 128000, 256000 ja 512000 elementi (aeglase arvuti korral võite võtta vähem elemente). Koostada lahendusaegadest tabel (soovitavalt "vanas" xls-formaadis) ja joongraafik, millel paigutada samasse teljestikku kõik viis joont (lahendamisaja sõltuvus andmemahust erinevate meetodite korral): x-teljel on andmemaht, y-teljel lahendusaeg.

Mõõta ainult järjestamiseks kuluvat aega iga meetodi jaoks võimalikult segamatult. Parema tulemuse saate, kui teete mitu mõõtmist ning leiate tulemustest keskmise.

Tähtaeg on teie rühma materjalide juures Moodle's, lahendused saata Moodle kaudu: programm automaattestina ja tabel/graafikud Excel failina.
Õigeaegse ja korrektse lahenduse eest kuni 6 punkti (3 - kahendpistemeetod, 3 - tabelid ja graafikud).

Jaanus Pöial