Свиридов ТИМП 4

////////////// Main
public class Main {
    public static void main(String[] args) {
        SortingClass.menu();
    }
}

////////////// Randomizer
import java.util.ArrayList;
import java.util.LinkedList;


public class Randomizer {

    public static ArrayList<Integer> randomArrayListInt(int size){
       ArrayList<Integer> arr=new ArrayList<>();
        for(int i=0;i<size;i++){
            arr.add((int)(Math.random()*200+1));
        }
        return arr;
    }
    public static LinkedList<Integer> randomLinkedListInt(int size){
        LinkedList<Integer> arr=new LinkedList<>();
        for(int i=0;i<size;i++){
            arr.add((int)(Math.random()*200+1));
        }
        return arr;
    }
    public static ArrayList<String > randomArrayListString(int size){
        ArrayList<String> arr=new ArrayList<>();
        for(int i=0;i<size;i++){
            arr.add(randomString());
        }
        return arr;
    }
    public static LinkedList<String> randomLinkedListString(int size){
        LinkedList<String> arr=new LinkedList<>();
        for(int i=0;i<size;i++){
            arr.add(randomString());
        }
        return arr;
    }

    private static String randomString()
        {
            int n=(int)(Math.random()*100+1);
            String AlphaNumericString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + "0123456789" + "abcdefghijklmnopqrstuvxyz";
            StringBuilder sb = new StringBuilder(n);
            for (int i = 0; i < n; i++) {
                int index = (int)(AlphaNumericString.length() * Math.random());
                sb.append(AlphaNumericString.charAt(index));
            }
            return sb.toString();

        }
}

////////////////// SortingClass
import java.util.List;
import java.util.Scanner;

public class SortingClass {
    private static int quickSortCheckingNumber=0;
    private static int quickSortReplaceNumber=0;

    private  static void quickSort(List<Integer> arr, int low, int high) {
        if (arr == null || arr.size() == 0){
            quickSortCheckingNumber++;
            return;
        }
        if (low >= high){
            quickSortCheckingNumber++;
            return;
        }
        int middle = low + (high - low) / 2;
        int pivot = arr.get(middle);
        int i = low, j = high;
        while (i <= j) {
            while (arr.get(i) < pivot) {
                quickSortCheckingNumber++;
                i++;
            }
            while (arr.get(j) > pivot) {
                quickSortCheckingNumber++;
                j--;
            }

            if (i <= j) {
                quickSortCheckingNumber++;
                quickSortReplaceNumber++;
                int temp = arr.get(i);
                arr.set(i,arr.get(j));
                arr.set(j,temp);
                i++;
                j--;
            }
        }
        if (low < j){
            quickSortCheckingNumber++;
            quickSort(arr, low, j);
        }
        if (high > i){
            quickSortCheckingNumber++;
            quickSort(arr, i, high);
        }
    }

    private  static void quickSortString(List<String> arr, int low, int high) {
        if (arr == null || arr.size() == 0){
            quickSortCheckingNumber++;
            return;
        }
        if (low >= high){
            quickSortCheckingNumber++;
            return;
        }
        int middle = low + (high - low) / 2;
        String  pivot = arr.get(middle);
        int i = low, j = high;
        while (i <= j) {
            while (arr.get(i).length() < pivot.length()) {
                quickSortCheckingNumber++;
                i++;
            }
            while (arr.get(j).length() > pivot.length()) {
                quickSortCheckingNumber++;
                j--;
            }

            if (i <= j) {
                quickSortCheckingNumber++;
                quickSortReplaceNumber++;
                String temp = arr.get(i);
                arr.set(i,arr.get(j));
                arr.set(j,temp);
                i++;
                j--;
            }
        }
        if (low < j){
            quickSortCheckingNumber++;
            quickSortString(arr, low, j);
        }
        if (high > i){
            quickSortCheckingNumber++;
            quickSortString(arr, i, high);
        }
    }

    public static void bubbleInt(List<Integer> list){ //пузорьковая сортировка чисел по возрастанию
        long start=System.currentTimeMillis();
        System.out.println("ДО: "+ list);
        boolean flag=false;
        int replaceNumber=0;
        int checkingNumber=0;
        while (!flag){
            flag=true;
            for(int i=1;i<list.size();i++) {
                if (list.get(i) <list.get(i - 1)) {
                    replaceNumber++;
                    checkingNumber++;
                    int value = list.get(i - 1);
                    list.set(i - 1, list.get(i));
                    list.set(i, value);
                    flag=false;
                }
                else
                    checkingNumber++;
            }
        }
        long finish=System.currentTimeMillis();
        System.out.println("После: "+list);
        System.out.println("Время выполнения: "+(finish-start));
        System.out.println("Количество проверок: "+checkingNumber);
        System.out.println("Количество обменов: "+replaceNumber);
    }

    public static void setQuickSortCheckingNumber(int quick) {
        quickSortCheckingNumber = quick;
    }

    public static void setQuickSortReplaceNumber(int quick) {
        quickSortReplaceNumber = quick;
    }

    public static void bubbleString(List<String> list){ //пузырьковая сортировка строк по длине
        long start=System.currentTimeMillis();
        System.out.println("ДО: "+ list);
        int replaceNumber=0;
        int checkingNumber=0;
        boolean flag=false;
        while (!flag){
            flag=true;
            for(int i=1;i<list.size();i++) {
                if (list.get(i).length() <list.get(i - 1).length()) {
                    replaceNumber++;
                    checkingNumber++;
                    String  value = list.get(i - 1);
                    list.set(i - 1, list.get(i));
                    list.set(i, value);
                    flag=false;
                }
                else
                    checkingNumber++;
            }
        }
        long finish=System.currentTimeMillis();
        System.out.println("После: "+list);
        System.out.println("Время выполнения: "+(finish-start));
        System.out.println("Количество проверок: "+checkingNumber);
        System.out.println("Количество обменов: "+replaceNumber);;
    }

    public static void shellInt(List<Integer> array) {
        long start=System.currentTimeMillis();
        int replaceNumber=0;
        int checkingNumber=0;
        System.out.println("ДО: "+ array);
        int h = 1;
        while (h*3 < array.size())
            h = h * 3 + 1;

        while(h >= 1) {
            int length = array.size();
            for (int i = h; i < length; i++) {
                for (int j = i; j >= h; j = j - h) {
                    if (array.get(j) < array.get(j-h)){
                        int value=array.get(j);
                        array.set(j,array.get(j-h));
                        array.set(j-h,value);
                        checkingNumber++;
                        replaceNumber++;
                    }
                    else{
                        checkingNumber++;
                        break;
                    }
                }
            }
            h = h/3;
        }
        long finish=System.currentTimeMillis();
        System.out.println("После: "+array);
        System.out.println("Время выполнения: "+(finish-start));
        System.out.println("Количество проверок: "+checkingNumber);
        System.out.println("Количество обменов: "+replaceNumber);
    }

    public static void shellString(List<String> array) {
        long start=System.currentTimeMillis();
        int replaceNumber=0;
        int checkingNumber=0;
        System.out.println("ДО: "+ array);
        int h = 1;
        while (h*3 < array.size())
            h = h * 3 + 1;

        while(h >= 1) {
            int length = array.size();
            for (int i = h; i < length; i++) {
                for (int j = i; j >= h; j = j - h) {
                    if (array.get(j).length() < array.get(j-h).length()){
                        String  value=array.get(j);
                        array.set(j,array.get(j-h));
                        array.set(j-h,value);
                        checkingNumber++;
                        replaceNumber++;
                    }
                    else{
                        checkingNumber++;
                        break;
                    }
                }
            }
            h = h/3;
        }
        long finish=System.currentTimeMillis();
        System.out.println("После: "+array);
        System.out.println("Время выполнения: "+(finish-start));
        System.out.println("Количество проверок: "+checkingNumber);
        System.out.println("Количество обменов: "+replaceNumber);
    }

    public static void quickInt(List<Integer> list){
        long start=System.currentTimeMillis();
        System.out.println("ДО: "+ list);
        quickSort(list,0,list.size()-1);
        long finish=System.currentTimeMillis();
        System.out.println("После: "+list);
        System.out.println("Время выполнения: "+(finish-start));
        System.out.println("Количество проверок: "+quickSortCheckingNumber);
        System.out.println("Количество обменов: "+quickSortReplaceNumber);
        setQuickSortCheckingNumber(0);
        setQuickSortReplaceNumber(0);
    }

    public static void quickString(List<String> list){
        long start=System.currentTimeMillis();
        System.out.println("ДО: "+ list);
        quickSortString(list,0,list.size()-1);
        long finish=System.currentTimeMillis();
        System.out.println("После: "+list);
        System.out.println("Время выполнения: "+(finish-start));
        System.out.println("Количество проверок: "+quickSortCheckingNumber);
        System.out.println("Количество обменов: "+quickSortReplaceNumber);
        setQuickSortCheckingNumber(0);
        setQuickSortReplaceNumber(0);
    }

    public static void LSDsortInt(List<Integer> array){
        long start=System.currentTimeMillis();
        sort(array);
        long finish=System.currentTimeMillis();
        System.out.println("После: "+array);
        System.out.println("Время выполнения: "+(finish-start));
        System.out.println("Количество проверок: "+quickSortCheckingNumber);
        System.out.println("Количество обменов: "+quickSortReplaceNumber);
        setQuickSortReplaceNumber(0);
        setQuickSortCheckingNumber(0);
    }

    private static void sort(List<Integer> array ){
        int radix=10;
        if (array.size()== 0) {
            quickSortCheckingNumber++;
            return;
        }
        // Determine minimum and maximum values
        int minValue = array.get(0);
        int maxValue = array.get(0);
        for (int i = 1; i < array.size(); i++) {
            if (array.get(i) < minValue) {
                quickSortCheckingNumber++;
                minValue = array.get(i);
            } else if (array.get(i) > maxValue) {
                quickSortCheckingNumber++;
                maxValue = array.get(i);
            }
        }

        int exponent = 1;
        while ((maxValue - minValue) / exponent >= 1) {
           countingSortByDigit(array, radix, exponent, minValue);
            exponent *= radix;
        }
    }

    private static void countingSortByDigit(List<Integer> array, int radix, int exponent, int minValue) {
        int bucketIndex;
        int[] buckets = new int[radix];
        int[] output = new int[array.size()];

        // Initialize bucket
        for (int i = 0; i < radix; i++) {
            buckets[i] = 0;
        }

        // Count frequencies
        for (Integer integer : array) {
            bucketIndex = (int) (((integer - minValue) / exponent) % radix);
            buckets[bucketIndex]++;
        }

        for (int i = 1; i < radix; i++) {
            buckets[i] += buckets[i - 1];
        }

        for (int i = array.size() - 1; i >= 0; i--) {
            bucketIndex = (int)(((array.get(i) - minValue) / exponent) % radix);
            output[--buckets[bucketIndex]] = array.get(i);
        }
        for (int i = 0; i < array.size(); i++) {
            array.set(i,output[i]);
            quickSortCheckingNumber++;
            quickSortReplaceNumber++;
        }
    }

    public static void LSDsortString(List<String> array){
        long start=System.currentTimeMillis();
        sortString(array);
        long finish=System.currentTimeMillis();
        System.out.println("После: "+array);
        System.out.println("Время выполнения: "+(finish-start));
        System.out.println("Количество проверок: "+quickSortCheckingNumber);
        System.out.println("Количество обменов: "+quickSortReplaceNumber);
        setQuickSortReplaceNumber(0);
        setQuickSortCheckingNumber(0);
    }

    private static void sortString(List<String> array ){
        int radix=10;
        if (array.size()== 0) {
            quickSortCheckingNumber++;
            return;
        }
        // Determine minimum and maximum values
        int minValue = array.get(0).length();
        int maxValue = array.get(0).length();
        for (int i = 1; i < array.size(); i++) {
            if (array.get(i).length() < minValue) {
                quickSortCheckingNumber++;
                minValue = array.get(i).length();
            } else if (array.get(i).length() > maxValue) {
                quickSortCheckingNumber++;
                maxValue = array.get(i).length();
            }
        }

        int exponent = 1;
        while ((maxValue - minValue) / exponent >= 1) {
            countingSortByDigitString(array, radix, exponent, minValue);
            exponent *= radix;
        }
    }

    private static void countingSortByDigitString(List<String> array, int radix, int exponent, int minValue) {
        int bucketIndex;
        int[] buckets = new int[radix];
        String[] output = new String[array.size()];

        // Initialize bucket
        for (int i = 0; i < radix; i++) {
            buckets[i] = 0;
        }

        // Count frequencies
        for (String integer : array) {
            bucketIndex = (int) (((integer.length() - minValue) / exponent) % radix);
            buckets[bucketIndex]++;
        }

        for (int i = 1; i < radix; i++) {
            buckets[i] += buckets[i - 1];
        }

        for (int i = array.size() - 1; i >= 0; i--) {
            bucketIndex = (int)(((array.get(i).length() - minValue) / exponent) % radix);
            output[--buckets[bucketIndex]] = array.get(i);
        }
        for (int i = 0; i < array.size(); i++) {
            array.set(i,output[i]);
            quickSortCheckingNumber++;
            quickSortReplaceNumber++;
        }
    }

    public static void menu() {
        Scanner sc = new Scanner(System.in);
        int choose1 = -1;
        while (true) {
            System.out.println("Выберете структуру данных: ");
            System.out.println("Численный массив-1");
            System.out.println("Строковый массив-2");
            System.out.println("Численный список-3");
            System.out.println("Строковый список-4");
            System.out.println("Выход-0");
            choose1 = sc.nextInt();
            if (choose1 == 0)
                break;
            System.out.println("Задайте размерность: ");
            int size = sc.nextInt();
            while(true) {
                System.out.println("Выберете способ сортировки");
                System.out.println("Медленная сортировка обменами-1");
                System.out.println("Сортировка Шелла-2");
                System.out.println("Быстрая сортировка-3");
                System.out.println("Сортировка подсчетом-4");
                System.out.println("Выход на предыдущий шаг-0");
                int choose2 = sc.nextInt();
                if(choose2==0)
                    break;
                else if (choose1 == 1) {
                    List<Integer> list = Randomizer.randomArrayListInt(size);
                    if (choose2 == 1) {
                        bubbleInt(list);
                    } else if (choose2 == 2) {
                        shellInt(list);
                    } else if (choose2 == 3) {
                        quickInt(list);
                    } else if (choose2 == 4) {
                        LSDsortInt(list);
                    }
                } else if (choose1 == 2) {
                    List<String> list = Randomizer.randomArrayListString(size);
                    if (choose2 == 1) {
                        bubbleString(list);
                    } else if (choose2 == 2) {
                        shellString(list);
                    } else if (choose2 == 3) {
                        quickString(list);
                    } else if (choose2 == 4) {
                        LSDsortString(list);
                    }
                } else if (choose1 == 3) {
                    List<Integer> list = Randomizer.randomLinkedListInt(size);
                    if (choose2 == 1) {
                        bubbleInt(list);
                    } else if (choose2 == 2) {
                        shellInt(list);
                    } else if (choose2 == 3) {
                        quickInt(list);
                    } else if (choose2 == 4) {
                        LSDsortInt(list);
                    }
                } else if (choose1 == 4) {
                    List<String> list = Randomizer.randomLinkedListString(size);
                    if (choose2 == 1) {
                        bubbleString(list);
                    } else if (choose2 == 2) {
                        shellString(list);
                    } else if (choose2 == 3) {
                        quickString(list);
                    } else if (choose2 == 4) {
                        LSDsortString(list);
                    }
                }
            }
        }
    }

}