Sorting Algorithms

import java.util.Random;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        Random random = new Random();
        int[]testArray = new int[10000];
        for(int i = 0; i < testArray.length; i++) {
            testArray[i] = random.nextInt(100);
        }
        int[]testArray2 = Arrays.copyOf(testArray, testArray.length);
        int[]testArray3 = Arrays.copyOf(testArray, testArray.length);
        int[]testArray4 = Arrays.copyOf(testArray, testArray.length);
        int[]testArray5 = Arrays.copyOf(testArray, testArray.length);
        int[]testArray6 = Arrays.copyOf(testArray, testArray.length);
        int[]testArray7 = Arrays.copyOf(testArray, testArray.length);
        //int[]testArray6 = {9,8,1,6,5,2};

        //BUBBLE SORT
        System.out.println("BUBBLE SORT");
        //Main.printArray(testArray);
        long start = System.currentTimeMillis();
        BubbleSort.sort(testArray);
        System.out.println("Czas sortowania: " + (System.currentTimeMillis() - start) + " milisekund");
        //Main.printArray(testArray);
        //SELECT SORT
        System.out.println("\nSELECT SORT");
        //Main.printArray(testArray2);
        long start2 = System.currentTimeMillis();
        SelectSort.sort(testArray2);
        System.out.println("Czas sortowania: " + (System.currentTimeMillis() - start2) + " milisekund");
        //Main.printArray(testArray2);
        //INSERTION SORT
        System.out.println("\nINSERTION SORT");
        //Main.printArray(testArray3);
        long start3 = System.currentTimeMillis();
        InsertionSort.sort(testArray3);
        System.out.println("Czas sortowania: " + (System.currentTimeMillis() - start3) + " milisekund");
        //Main.printArray(testArray3);
        //MERGE SORT
        System.out.println("\nMERGE SORT");
        //Main.printArray(testArray4);
        long start4 = System.currentTimeMillis();
        MergeSort.sort(testArray4);
        System.out.println("Czas sortowania: " + (System.currentTimeMillis() - start4) + " milisekund");
        //Main.printArray(testArray4);
        //HEAP SORT
        System.out.println("\nHEAP SORT");
        //Main.printArray(testArray5);
        long start5 = System.currentTimeMillis();
        HeapSort.sort(testArray5);
        System.out.println("Czas sortowania: " + (System.currentTimeMillis() - start5) + " milisekund");
        //Main.printArray(testArray5);
        //QUICK SORT
        System.out.println("\nQUICK SORT");
        //Main.printArray(testArray6);
        long start6 = System.currentTimeMillis();
        QuickSort.sort(testArray6);
        System.out.println("Czas sortowania: " + (System.currentTimeMillis() - start6) + " milisekund");
        //Main.printArray(testArray6);
        //SHELL SORT
        System.out.println("\nSHELL SORT");
        //Main.printArray(testArray7);
        long start7 = System.currentTimeMillis();
        //ShellSort.sort(testArray7, ShellSort::shellDistance);
        ShellSort.sort(testArray7, ShellSort::sedgewickDistance);
        System.out.println("Czas sortowania: " + (System.currentTimeMillis() - start7) + " milisekund");
        //Main.printArray(testArray7);

    }
    private static void printArray(int[]arr) {
        for(int j = 0; j < arr.length; j++) {
            System.out.print(arr[j] + " ");
        }
        System.out.println();
    }
}

public class SortUtils {

    public static void swap(int[]array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}

public class InsertionSort {  //sortowanie przez wstawianie

    public static void sort(int[]arrayToSort) {
        int n = arrayToSort.length;
        int current;
        int otherIndex;
        for(int i = 1; i < n; i++) {   //zaczynamy od drugiego elementu
            current = arrayToSort[i];  //zapamietujemy 2gi element tablicy
            otherIndex = i;            //j.w
            while(otherIndex > 0 && current < arrayToSort[otherIndex - 1]) {  //sprawdzamy czy obecny element jest mniejeszy od poprzedniego
                arrayToSort[otherIndex] = arrayToSort[otherIndex - 1];  //podmieniamy pomocniczą zmienną, liczbą 1sza (teraz na pozycji 0 i 1 jest ta sama liczba, większa)
                otherIndex--;  //zmniejszamy indeks na poprzedni (przesuwamy sie po tablicy do tyłu) i porównujemy wartosci liczb ponownie.
            }
            arrayToSort[otherIndex] = current;  //ustawiamy naszą zapamiętaną liczbę na odpowiedniej pozycji w tablicy do posortowania (pozycja ta będzie wiadoma dzięki petli "while")
        }
    }
}

public class SelectSort {   //sortowanie przez wybieranie najmniejszego indeksu

    public static void sort(int[]arrayToSort) {
        int n = arrayToSort.length;
        int minIndex;
        for(int i = 0; i < n - 1; i++) {
            minIndex = i;   //ustawianie wartosci indeksu "i" ktorego bedziemy porównywać z reszta liczb
            for(int j = i + 1; j < n; j++) {
                if(arrayToSort[j] < arrayToSort[minIndex]) {  //jeżeli następna liczba jest mniejsza niz wartosc indeksu to ustawiamy nowy indeks
                    minIndex = j;  //ustawiamy nowe indeks
                }
            }
                if(minIndex != i){                    //sprawdzanie czy zmieniliśmy wartość pierwotnego indeksu.
                    SortUtils.swap(arrayToSort, minIndex, i); //zamiana miejscami mniejszej liczby spod "i" z minIndeks
            }
        }
    }
}

public class BubbleSort {  //sortowanie babelkowe. Największa liczba ustawiana jest na samym koncu

    public static void sort(int[]arrayToSort) {
        int n = arrayToSort.length;
        int it = 0;  // licznik konca tablicy (w petli for nie bedzie już porownywal ostatnich znaków)
        boolean swapped = true;
        while (it < n - 1 && swapped) {
            swapped = false;
            for (int j = 0; j < n - 1 - it; j++) {  //iterujemy po ciagu liczb z pominięciem "it"
                if (arrayToSort[j] > arrayToSort[j + 1]) {  //porównujemy dwie liczby
                    SortUtils.swap(arrayToSort, j, j + 1);  //jak liczba po lewej stronie jest większa to zamieniamy ją miejscami z liczba po prawej stronie
                    swapped = true;  //warunek ktory sprawdza czy byla jakas zamiana.
                }
            }
            it++; //zmniejszamy tablice
        }
    }
}

public class MergeSort {   //sortowanie przez scalanie

    private static int[]extraArray;

    public static void sort(int[]arrayToSort) {
        extraArray = new int[arrayToSort.length];
        mergeSort(arrayToSort, 0 , arrayToSort.length -1); //lewa granica i prawa granica tablicy
    }
    private static void mergeSort (int[]array, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {  //dzielenie tablicy do jednego elementu
            int middle = (leftIndex + rightIndex) / 2;
            mergeSort(array, leftIndex, middle);  //dzielenie lewej czesci do 2 elementów rekurencyjnie
            mergeSort(array, middle + 1, rightIndex);  //dzielenie prawej czesci do 2 elementów rekurencyjnie
            merge(array, leftIndex, middle, rightIndex); //łaczenie czesci lewej i prawej (wykona sie dopiero wtedy gdy wywołania rekurencyjne beda skonczone)
        }
    }
    private static void merge(int[]array, int leftIndex, int middleIndex, int rightIndex) {  //wypisywanie 0ego i 1ego elementu tablicy do posortowania (plus zwiekszenie licznika "i")
        for (int i = leftIndex; i <= rightIndex; i++) {
            extraArray[i] = array[i];   //do tablicy pomocniczej wpisujemy dwie kolejne liczby (z tablicy do posortowania)
        }

        //ustawianie wskaźników
        int finger1 = leftIndex;   //pierwsza liczba z lewej strony o indeksie 0   --lewa
        int finger2 = middleIndex + 1; //pierwsza liczba z prawej strony           --prawa
        int current = leftIndex;
        ///////////////////////

        while(finger1 <= middleIndex && finger2 <= rightIndex) {  //?????
            //porownywanie elementów
            if(extraArray[finger1] <= extraArray[finger2]) {  //porownywanie wartosci liczb po indeksie (czy wartosc finger 1 jest mniejsza o wartosci finger2)
                array[current] = extraArray[finger1];
                finger1++;
            }
            else {
                array[current] = extraArray[finger2];
                finger2++;
            }
            ////////////////////////////
            current++;  //zwiekszam indeks o jeden i wpisuje/porównuje kolejną liczbę
        }
        while(finger1 <= middleIndex) {   //jezeli prawa strona sie skonczyla i jest posortowana to tutaj zostaje dopisana liczba z lewej storny lub jak
                                          //z lewej strony sie skonczy liczba to to sie nie wykona bo prawa strona bewdzie juz na swoim miejscu.
            array[current] = extraArray[finger1];
            finger1++;
            current++;
        }
    }
}

public class HeapSort {  //sortowanie przez kopcowanie

    public static void sort(int[]arrayToSort) {
        int n = arrayToSort.length;

        for (int i = n/2 - 1; i>=0; i--){      //tworzenie kopca i szukanie ostatniego rodzica
            HeapSort.validateMaxHeap(arrayToSort, n, i);    //sprawdzanie czy jest 'maxheap'
        }
        for (int i = n - 1; i>0; i--){          //iterowanie od konca do poczatku
            SortUtils.swap(arrayToSort, 0, i);  //zamiana ostatniego elementu kopca z pierwszysm rodzicem (czyli najwieksza wartosc wedruje na sam koniec)
            n--;                                //zmniejszanie kopca poprzez odcięcię ostatniego dziecka z najwiekszą wartością
            HeapSort.validateMaxHeap(arrayToSort, n, 0); //walidacja kopca zmniejszonego o 1
        }
    }
    private static void validateMaxHeap(int[] array, int heapSize, int parentIndex){

        ///////ustawianie wskaźników
        int maxIndex = parentIndex;
        int leftChild = parentIndex * 2 + 1;
        int rightChild = parentIndex * 2 + 2;
        ////////////////////////////

        if(leftChild < heapSize && array[leftChild] > array[maxIndex]){  //sprawdzanie po wartosci
            maxIndex = leftChild;
        }
        if(rightChild < heapSize && array[rightChild] > array[maxIndex]){ //sprawdzanie po wartosci
            maxIndex = rightChild;
        }
        if(maxIndex != parentIndex){                       //jeżeli rodzic został zamieniony z dzieckiem to:
            SortUtils.swap(array, maxIndex, parentIndex);  //zamieniamy miejscami parentIndex z maxIndex (od tej pory oryginalny rodzic jest na mijescu dziecka ktore było większe)
            validateMaxHeap(array, heapSize, maxIndex);    //i sprawdzamy rekurencyjnie czy struktura drzewa jest zachowana. (czy rodzic ma większą wartość niz jego dzieci)
        }
    }
}

public class QuickSort {   //Sorotwanie z pivotem

    public static void sort(int[]arrayToSort) {
        int n = arrayToSort.length;
        quicksort(arrayToSort, 0, n-1);
    }
    public static void quicksort(int[]array, int left, int right) {
        if (left >= right){  //sprawdzanie czy jest wiecej niz jedna liczba
            return;
        }
        ///////////////////////////ustawianie wskaźników
        int pivotValue = array[right];
        int border = left - 1;   //granica po ktorej sortujemy
        int i = left;            //iteracja po liczbach
        ///////////////////////////


        while (i < right){                //jak doszlismy do konca lanucha to wychodzimy z petli...
            if (array[i] < pivotValue){   //sprawdzanie wartości (czy liczba po lewej stronie granicy jest mniejsza od pivota)
                border++;                 //jak jest mniejsza to przesywamy granice o jeden w prawo
                if(border != i){          //zamieniamy liczbe spod "i" z liczba po lewej stronie od granicy
                    SortUtils.swap(array, border, i);
                }
            }
            i++;
        }
        border++;   //...i przesuwamy granice w prawo
        if (border != right){  //zamieniamy miejscami pivota z liczba po lewej stronie od granicy
            SortUtils.swap(array, border, right);
        }
        quicksort(array, left, border-1);  //sprawdzamy lewa strone rekurencyjnie
        quicksort(array, border+1, right);  //sprawdzamy prawa strone rekurencyjnie
    }

}

import java.util.ArrayList;
import java.util.Collections;
import java.util.function.Function;

public class ShellSort {

    public static void sort(int[]arr, Function<Integer, Integer[]> distGenerator){  //interfejs java8 - poczytac
        int n = arr.length;
        int iter = 1;
        Integer[] distances = distGenerator.apply(n);
        int distance = distances[distances.length - iter];  //pobieranie dystansu od konca (od najwiekszego dystansu do najmniejszego)
        int current, otherIndex;  //zmienne dla porównywanych liczb
        while(distance >= 1){  //SPRAWDZIĆ
            for(int i = distance; i < n; i++){  //sortowanie przez wstawianie
                current = arr[i];  //wartosc "i"
                otherIndex = i;  //indeks "i"
                while(otherIndex >= distance && current < arr[otherIndex - distance]){ //porównujemy wartość pierwszej liczby zza połowy z wartością liczby minus dystans (czyli prawą liczbe z lewą ze swojej pary)
                    arr[otherIndex] = arr[otherIndex - distance];  //jeżeli liczba po prawej stronie jest mniejsza to nadpisujemy ją liczbą z lewej strony.
                    otherIndex -= distance;  //ustawiamy indeks na liczbie po lewej stronie zeby ją zmienić. (ustawiamy ja tak że odejmujemy wartosc dystnasu)
                }
                arr[otherIndex] = current;  //ustawiamy zamieniona liczbe w nowe miejsce (czyli zapamiętana z prawej strony (current) na lewą stronę. (czyli minus dystans).
            }
            distance = distances[distances.length - ++iter];  //zmniejszamy dystans przez pobranie z wygenerowanej wczesniej tablicy dystansów, kolejnego dystansu.
        }
    }

    public static Integer[] shellDistance(int numberOfElements){
        ArrayList<Integer> distances = new ArrayList<>();
        int iteration = 1;
        int generated;
        do{
            generated = numberOfElements / (int)Math.pow(2, iteration);
            distances.add(generated);
            iteration++;
        }while(generated > 0);
        Collections.reverse(distances);
        return distances.toArray(new Integer[distances.size()]);
    }

    // 4^k + 3*2^(k-1) + 1
    public static Integer[] sedgewickDistance(int numberOfElements){
        int generated = 0;
        ArrayList<Integer> distances = new ArrayList<>();
        int k = 0;
        while(generated < numberOfElements){
            if(distances.isEmpty()){
                distances.add(0);
                distances.add(1);
            } else{
                generated = (int) (Math.pow(4, k) + 3 * Math.pow(2, k-1) + 1);
                if(generated < numberOfElements){
                    distances.add(generated);
                }
            }
            k++;
        }
        return distances.toArray(new Integer[distances.size()]);
    }

}