AP_Lab_10

package com.com;

class selectionSort {                                                  //Алгоритм вибором:
    private void swap(int arr[], int i1, int i2) {
        int temp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = temp;
    }

    public void sort(int arr[]) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min_index = i;                                         //Крок 1: запам'ятовуємо позицію
            int min_value = arr[i];                                    //і значення елементу і-того індекса в основному масиві
            for (int j = i; j < arr.length; j++) {                     //Крок 2: звіряємо з усіми елементами в подальшому масиві
                if (min_value > arr[j]) {                              //Крок 3: якщо наш елемент, який ми запам'ятали, є більшим за інший подальший елемент
                    min_index = j;                                     //тоді ми запам'ятовуємо менший елемент, а також його позицію(індекс). Повторюємо крок 3 до тих пір,
                    min_value = arr[j];                                //поки не дійдемо кінця масиву
                }
            }
            swap(arr, min_index, i);                                   //Крок 4: після того, як знайшовся менший елемент за і-тий елемент основного масиву у кроці 3,
        }                                                              //ми їх міняємо місцями. Продовжуємо алгоритм з кроку 1, поки не дійдемо кінця масиву.
    }

    public selectionSort(int arr[]) {
        sort(arr);
    }
}

class mergeSort {                                                      //Алгоритм злиття:
    private void merge(int arr[], int leftSize, int middleSize, int rightSize) {
        int i, j, k;
        int num1 = middleSize - leftSize + 1;                          //Крок 1: знаходимо кіл-сть елментів лівого
        int num2 = rightSize - middleSize;                             //і правого масиву
        int[] arrLeft = new int[num1];                                 //Крок 2: створюємо масиви з відповідно знайденими кілкостями у кроці 1
        int[] arrRight = new int[num2];
        for (i = 0; i < num1; i++)                                     //Крок 3: заповнюємо масиви елементами
            arrLeft[i] = arr[leftSize + i];
        for (j = 0; j < num2; j++)
            arrRight[j] = arr[middleSize + 1 + j];
        i = 0;
        j = 0;
        k = leftSize;                                                  //Примітка: локальний перший елемент
        while (i < num1 && j < num2) {                                 //Крок 4: починаємо заповнювати основний масив сортуючи елементи з створених масивів
            if (arrLeft[i] <= arrRight[j]) {                           //у кроці 2 за такими принципами - якщо елемент лівого масиву є меншим за елемент правого масиву,
                arr[k] = arrLeft[i];                                   //тоді ми додаємо лівий елемент до основного масиву і переміщаємось на один елемент вперед
                i++;                                                   //в лівому масиві, якщо ж елемент лівого масиву є більшим за правий, тоді додаємо елемент правого
            } else {                                                   //масиву у основний масив і переміщаємось на один елемент вперед в правому масиві.
                arr[k] = arrRight[j];                                  //Продовжуємо цей алгоритм до тих пір, поки ми не дійдемо кінця якого-небудь масиву.
                j++;
            }
            k++;                                                       //Примітка: кожен раз робимо крок вперед в основному масиві
        }
        while (i < num1) {                                             //Крок 5: якщо є якийсь залишок в правому або лівому масиві, тоді ми його записуємо у основний масив
            arr[k] = arrLeft[i];
            i++;
            k++;
        }
        while (j < num2) {
            arr[k] = arrRight[j];
            j++;
            k++;
        }
    }

    public void sort(int arr[], int leftSize, int rightSize) {
        if (leftSize < rightSize) {                                    //Крок 2: продовжуємо крок перший, поки кількість елментів в масиві не стане 1 - переходимо на крок 3
            int middleSize = leftSize + (rightSize - leftSize) / 2;    //Крок 1: ділимо масив на дві частини рекурсивно (масив ділиться умовно)
            sort(arr, leftSize, middleSize);                           //- знайдемо центр масиву (кожен раз центр буде новий)
            sort(arr, middleSize + 1, rightSize);
            merge(arr, leftSize, middleSize, rightSize);               //Крок 3: далі сортуємо масив за алгоритмом (продовження алгоритму в методі "merge"
        }                                                              // і кроки нумерються спочатку) рекурсивно
    }

    public mergeSort(int arr[]) {
        sort(arr, 0, arr.length - 1);
    }
}

class gnomeSort {                                                      //Алгоритм гнома:
    private void swap(int arr[], int i1, int i2) {
        int temp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = temp;
    }

    public void sort(int arr[]) {
        int n = 0;
        while (n < arr.length) {                                       //Крок 3: Повторюємо алгоримт з першого кроку, поки гноим не дійде кінця списку
            if (n == 0)                                                //Крок 1: робимо один крок вперед, якщо ми на початковій позиції.
                n++;
            if (arr[n] >= arr[n - 1])                                  //Крок 2: перевіряємо, чи минулий елемент менший за даний, якщо так - робимо крок вперед,
                n++;
            else {                                                     //якщо ні - міняємо елементи місцями і робимо крок назад
                swap(arr, n, n - 1);
                n--;
            }
        }
    }

    public gnomeSort(int arr[]) {
        sort(arr);
    }
}

class cocktailShakerSort {                                             //Коктейльний алгоритм:
    private void swap(int arr[], int i1, int i2) {
        int temp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = temp;
    }

    public void sort(int arr[]) {
        int max_index = arr.length;                                    //Примітка: права границя
        int min_index = 0;                                             //Примітка: ліва границя
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < max_index - 1; j++) {                  //Крок 1: проходимо по масиву від лівої границія до кінця правої границі,
                if (arr[j] > arr[j + 1])                               //якщо даний елемент є більшим за наступний - міняємо їх місцями
                    swap(arr, j, j + 1);
            }
            --max_index;                                               //Крок 2: зменшуємо на одиницю праву границю
            for (int j = max_index; j > min_index; j--) {              //Крок 3: проходимо по маисву від правої границі до початку лівої границі,
                if (arr[j] < arr[j - 1])                               //якщо данний елемент є більшим за попередній - міняємо їх місцями
                    swap(arr, j, j - 1);
            }
            ++min_index;                                               //Крок 4: збільшуємо ліву границю
        }                                                              //Крок 5: продовжуємо алгоритм починаючи з першого кроку доти,
    }                                                                  //поки основний цикл не закінчить свою роботу

    public cocktailShakerSort(int arr[]) {
        sort(arr);
    }
}

public class Main {

    public static void main(String[] args) {
//        СОРТУВАННЯ ВИБОРОМ
        int[] arr = {3, 23, 5, 3, 32, 32, 213, 234, 5, 2, 12, -123, -213, 213, 234, -2, -32, 8932, 23, -123, 0};
        System.out.print("Сорутвання вибором до: ");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();

        selectionSort selectionSort = new selectionSort(arr);
        System.out.print("Сорутвання вибором після: ");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
        System.out.println();
//        СОРТУВАННЯ ВИБОРОМ

//        СОРТУВАННЯ ЗЛИТТЯМ
        int[] arr1 = {32, 53, -23, 342, 134, 12, 423, 12, 43, -233, -23, -4532, -234, 0};
        System.out.print("Сорутвання злиттям до: ");
        for (int i = 0; i < arr1.length; i++)
            System.out.print(arr1[i] + " ");
        System.out.println();

        mergeSort mergeSort = new mergeSort(arr1);
        System.out.print("Сорутвання злиттям після: ");
        for (int i = 0; i < arr1.length; i++)
            System.out.print(arr1[i] + " ");
        System.out.println();
        System.out.println();
//        СОРТУВАННЯ ЗЛИТТЯМ

//        СОРТУВАННЯ ГНОМОМ
        int[] arr2 = {32, 2345, 12, 123, 5432, -12, -45, -234, 213, 23, 123, 45, -324, -213, -123213, 0};
        System.out.print("Сорутвання гномом до: ");
        for (int i = 0; i < arr2.length; i++)
            System.out.print(arr2[i] + " ");
        System.out.println();

        gnomeSort gnomeSort = new gnomeSort(arr2);
        System.out.print("Сорутвання гномом після: ");
        for (int i = 0; i < arr2.length; i++)
            System.out.print(arr2[i] + " ");
        System.out.println();
        System.out.println();
//        СОРТУВАННЯ ГНОМОМ

//        КОКТЕЙЛЬНЕ СОРТУВАННЯ
        int[] arr3 = {-32, -4233, -32, -213, 234, 234, 324, 21, 4, 873, 37, 84, -32, -3, -12, -3, -1, -2, 3, 5, 5, 0};
        System.out.print("Коктейльним сортуванням до: ");
        for (int i = 0; i < arr3.length; i++)
            System.out.print(arr3[i] + " ");
        System.out.println();

        cocktailShakerSort cocktailShakerSort = new cocktailShakerSort(arr3);
        System.out.print("Коктейльним сортуванням після: ");
        for (int i = 0; i < arr3.length; i++)
            System.out.print(arr3[i] + " ");
        System.out.println();
//        КОКТЕЙЛЬНЕ СОРТУВАННЯ
    }
}