Main.java

import java.util.Random;
import java.util.Scanner;


//klasa przechowująca i sortująca wydzielone potablice pięcio-elementowe
class Sort_Median {

    public int[] array;                         //tablica elementów
    private int nElems;
    private int size;                           //liczba elementów tablicy
//-----------------------------------------------------------------------------

    public Sort_Median(int max) {
        array = new int[max];
        nElems = 0;                             //na razie brak elementów
        size = max;
    }

//-----------------------------------------------------------------------------

    public void insert(int pos, int value) {    //wstawienie elementu do tablicy
        array[pos] = value;                     //wstawiamy
        nElems++;                               //zwiększamy licznik elementów
    }

//-----------------------------------------------------------------------------

    public int sort() {
        for (int i = 1; i < nElems; i++) {
            int j = i - 1;
            int v = array[i];
            while (j >= 0 && v < array[j]) {
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = v;
        }

        /**for (int i = 0; i < nElems; i++) {
            System.out.print(array[i] + ", ");
        }
        System.out.println();**/
        int med = array[nElems / 2];                //mediana z posortowanej tablicy
        return med;
    }

}

//-----------------------------------------------------------------------------

class Array {

    public int[] array;                             //tablica elementów
    private int nElems;
    private int size;                               //liczba elementów tablicy
//-----------------------------------------------------------------------------

    public Array(int max) {
        array = new int[max];
        
        nElems = 0;                                 //na razie brak elementów
        size = max;
    }
//-----------------------------------------------------------------------------

    public void insert(int value) {
        array[nElems] = value;                      //wstawiamy
        nElems++;                                   //zwiększamy licznik elementów
    }
//-----------------------------------------------------------------------------

    public void randomize() {
        Random random = new Random();
        array[nElems] = random.nextInt(100);        //wstawiamy
        nElems++;
    }
//-----------------------------------------------------------------------------

    public void display() {
        for (int i = 0; i < nElems; i++) {
            System.out.print(array[i] + ", ");
        }
        System.out.println();
    }
//-----------------------------------------------------------------------------

    public void sort() {
        //sortowanie przez wstawianie
        for (int i = 1; i < nElems; i++) {
            int j = i - 1;
            int v = array[i];
            while (j >= 0 && v < array[j]) {
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = v;
        }
    }

    public int mediana( int n, int[] S ) {
        int[] medians;                                          //deklaracja tablicy median z median
        int medians_elems = 0;                                  //aktualna ilosc median z median
        if (n % 5 != 0) medians = new int[n / 5 + 1];           //sprawdzamy czy ilość median jest podzielan przez pięć
        else medians = new int[n / 5];                          //i alokujemy tablicę odpowiedniego rozmiaru        
        for (int i = 0; i < n/5; i++) {                         //przeglądamy tablicę podzieloną na pięć części
            Sort_Median five = new Sort_Median(5);              //tworzymy tablicę piątek
            for (int j = 0; j < 5; j++) five.insert(j, S[i*5+j]);   //wstawiamy do tablicy elementy z i-tej piątki
            int med = five.sort();                              //sortujemy utworzoną tablicę z elementów z i-tej piątki i
                                                                //otrzymujemy medianę danej podtablicy
            medians[medians_elems++] = med;                     //otrzymaną mediane wrzucamy do tablicy median z median
        }
        if (n % 5 != 0) {                                       //jeśli ilosc elementow tablicy dzieli sie z reszta przez 5
            Sort_Median fiveModulo = new Sort_Median(n % 5);    //deklaracja tablicy o wielkości reszty z dzielenia przez 5
            for (int j = 0; j < n % 5; j++)
                fiveModulo.insert(j, S[(n/5)*5+j]);             //wstawianie to tablicy elementów pozostałych po podzieleniu przez 5
            int med = fiveModulo.sort();                        //sortujemy utworzoną tablice z elementów z pozostałości po
                                                                //podzieleniu przez 5 i otrzymyjemy medianę danej podtablicy
            if (medians_elems == 0) {                           //jesli tablica median z median jest pusta tzn że mamy tylko
                                                                //jedną mediane z median (tablica ma mniej niż 5 elementów)
                return med;                                     //zwracamy wyszukaną mediane
            }
            medians[medians_elems++] = med;                     //dodajemy wyszukaną medianę do tablicy median z median
        }
        return mediana(medians_elems, medians);                 //wywołujemy rekurencyjnie funkcję dla tablicy z medianami
                                                                //podtablic pięcio-elementowych
    }
//-----------------------------------------------------------------------------
    //wyszukiwanie k-tego elementu w tablicy
    public int Select(int[] S, int k, int n) {
        int[] S1 = new int[n];
        int[] S2 = new int[n];
        int[] S3 = new int[n];
        int s1_elems =0;
        int s2_elems =0;
        int s3_elems =0;

        int p = mediana( n, S );


        for (int i = 0; i < n; i++) {
            if (S[i] < p) {
                S1[s1_elems++] = S[i];
            }
            if (S[i] > p) {
                S3[s3_elems++] = S[i];
            }
            if (S[i] == p) {
                S2[s2_elems++] = S[i];
            }
        }

        if (k <= s1_elems) {            
            return Select(S1, k, s1_elems);
        }
        if (k <= s1_elems + s2_elems) {            
            return p;
        }
        return Select(S3, k - s1_elems - s2_elems, s3_elems);
    }

}


public class Main {

    public static void menu() {
        System.out.println("[1] Wylosuj tablicę automatycznie");
        System.out.println("[2] Wczytaj tablicę z klawiatury");
        System.out.println("[0] Zakończ pracę");
    }

    public static void rand(Array tab, int N) {
        Random random = new Random();
        for(int i = 0;i < N; i++) {
            tab.insert(random.nextInt(2000));
        }
    }

    public static void test_1() {
        System.out.println("Test 1");
        int N = 50;
        Array array = new Array(N);
        rand(array, N);
        int k = 14;
        System.out.println(k + " element to = " + array.Select(array.array, k, N));
    }

    public static void test_2() {
        System.out.println("Test 2");
        int N = 100;
        Array array = new Array(N);
        rand(array, N);
        int k = 39;
        System.out.println(k + " element to = " + array.Select(array.array, k, N));
    }

    public static void test_3() {
        System.out.println("Test 3");
        int N = 1000;
        Array array = new Array(N);
        rand(array, N);
        int k = 345;
        System.out.println(k + " element to = " + array.Select(array.array, k, N));
    }

    public static void test_4() {
        System.out.println("Test 4");
        int N = 1000000;
        Array array = new Array(N);
        rand(array, N);
        int k = 5654;
        System.out.println(k + " element to = " + array.Select(array.array, k, N));
    }

    public static void test_5() {
        System.out.println("Test 5");
        int N = 3000000;
        Array array = new Array(N);
        rand(array, N);
        int k = 432443;
        System.out.println(k + " element to = " + array.Select(array.array, k, N));
    }   

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        boolean test = true;
        if (test) {
            //test_1();
            //test_2();
            //test_3();
            //test_4();
            test_5();
        } else {
            int option = 1;
            while (option != 0) {
                menu();
                option = in.nextInt();
                System.out.println("Podaj rozmiar tablicy");
                int N = in.nextInt();
                Array array = new Array(N);
                int k = 10;
                int result = 0;
                switch (option) {
                    case 1 :
                        Random random = new Random();
                        for(int i = 0;i < N; i++) {
                            array.insert(random.nextInt(100));
                        }
                        System.out.println("Podaj który element wyszukać : ");
                        k = in.nextInt();
                        result = array.Select(array.array, k, N);
                        System.out.println(k + " element to = " + result);
                        break;
                    case 2 :
                        for(int i = 0;i < N; i++) {
                            System.out.println("Podaj " + i + " element : ");
                            array.insert(in.nextInt());
                        }
                        System.out.println("Podaj który element wyszukać : ");
                        k = in.nextInt();
                        result = array.Select(array.array, k, N);
                        System.out.println(k + " element to = " + result);
                        break;
                    case 0 :
                        option = 0;
                        break;
                }
            }
        }
    }

}