sfrsnyz

My TIMP LABA 4

May 8th, 2021
591
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ////////////// Main
  2. public class Main {
  3.     public static void main(String[] args) {
  4.         SortingClass.menu();
  5.     }
  6. }
  7.  
  8. ////////////// Randomizer
  9. import java.util.ArrayList;
  10. import java.util.LinkedList;
  11.  
  12.  
  13. public class Randomizer {
  14.  
  15.     public static ArrayList<Integer> randomArrayListInt(int size){
  16.        ArrayList<Integer> arr=new ArrayList<>();
  17.         for(int i=0;i<size;i++){
  18.             arr.add((int)(Math.random()*200+1));
  19.         }
  20.         return arr;
  21.     }
  22.     public static LinkedList<Integer> randomLinkedListInt(int size){
  23.         LinkedList<Integer> arr=new LinkedList<>();
  24.         for(int i=0;i<size;i++){
  25.             arr.add((int)(Math.random()*200+1));
  26.         }
  27.         return arr;
  28.     }
  29.     public static ArrayList<String > randomArrayListString(int size){
  30.         ArrayList<String> arr=new ArrayList<>();
  31.         for(int i=0;i<size;i++){
  32.             arr.add(randomString());
  33.         }
  34.         return arr;
  35.     }
  36.     public static LinkedList<String> randomLinkedListString(int size){
  37.         LinkedList<String> arr=new LinkedList<>();
  38.         for(int i=0;i<size;i++){
  39.             arr.add(randomString());
  40.         }
  41.         return arr;
  42.     }
  43.  
  44.     private static String randomString()
  45.         {
  46.             int n=(int)(Math.random()*100+1);
  47.             String AlphaNumericString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + "0123456789" + "abcdefghijklmnopqrstuvxyz";
  48.             StringBuilder sb = new StringBuilder(n);
  49.             for (int i = 0; i < n; i++) {
  50.                 int index = (int)(AlphaNumericString.length() * Math.random());
  51.                 sb.append(AlphaNumericString.charAt(index));
  52.             }
  53.             return sb.toString();
  54.  
  55.         }
  56. }
  57.  
  58. ////////////////// SortingClass
  59. import java.util.List;
  60. import java.util.Scanner;
  61.  
  62. public class SortingClass {
  63.     private static int quickSortCheckingNumber=0;
  64.     private static int quickSortReplaceNumber=0;
  65.  
  66.     private  static void quickSort(List<Integer> arr, int low, int high) {
  67.         if (arr == null || arr.size() == 0){
  68.             quickSortCheckingNumber++;
  69.             return;
  70.         }
  71.         if (low >= high){
  72.             quickSortCheckingNumber++;
  73.             return;
  74.         }
  75.         int middle = low + (high - low) / 2;
  76.         int pivot = arr.get(middle);
  77.         int i = low, j = high;
  78.         while (i <= j) {
  79.             while (arr.get(i) < pivot) {
  80.                 quickSortCheckingNumber++;
  81.                 i++;
  82.             }
  83.             while (arr.get(j) > pivot) {
  84.                 quickSortCheckingNumber++;
  85.                 j--;
  86.             }
  87.  
  88.             if (i <= j) {
  89.                 quickSortCheckingNumber++;
  90.                 quickSortReplaceNumber++;
  91.                 int temp = arr.get(i);
  92.                 arr.set(i,arr.get(j));
  93.                 arr.set(j,temp);
  94.                 i++;
  95.                 j--;
  96.             }
  97.         }
  98.         if (low < j){
  99.             quickSortCheckingNumber++;
  100.             quickSort(arr, low, j);
  101.         }
  102.         if (high > i){
  103.             quickSortCheckingNumber++;
  104.             quickSort(arr, i, high);
  105.         }
  106.     }
  107.  
  108.     private  static void quickSortString(List<String> arr, int low, int high) {
  109.         if (arr == null || arr.size() == 0){
  110.             quickSortCheckingNumber++;
  111.             return;
  112.         }
  113.         if (low >= high){
  114.             quickSortCheckingNumber++;
  115.             return;
  116.         }
  117.         int middle = low + (high - low) / 2;
  118.         String  pivot = arr.get(middle);
  119.         int i = low, j = high;
  120.         while (i <= j) {
  121.             while (arr.get(i).length() < pivot.length()) {
  122.                 quickSortCheckingNumber++;
  123.                 i++;
  124.             }
  125.             while (arr.get(j).length() > pivot.length()) {
  126.                 quickSortCheckingNumber++;
  127.                 j--;
  128.             }
  129.  
  130.             if (i <= j) {
  131.                 quickSortCheckingNumber++;
  132.                 quickSortReplaceNumber++;
  133.                 String temp = arr.get(i);
  134.                 arr.set(i,arr.get(j));
  135.                 arr.set(j,temp);
  136.                 i++;
  137.                 j--;
  138.             }
  139.         }
  140.         if (low < j){
  141.             quickSortCheckingNumber++;
  142.             quickSortString(arr, low, j);
  143.         }
  144.         if (high > i){
  145.             quickSortCheckingNumber++;
  146.             quickSortString(arr, i, high);
  147.         }
  148.     }
  149.  
  150.     public static void bubbleInt(List<Integer> list){ //пузорьковая сортировка чисел по возрастанию
  151.         long start=System.currentTimeMillis();
  152.         System.out.println("ДО: "+ list);
  153.         boolean flag=false;
  154.         int replaceNumber=0;
  155.         int checkingNumber=0;
  156.         while (!flag){
  157.             flag=true;
  158.             for(int i=1;i<list.size();i++) {
  159.                 if (list.get(i) <list.get(i - 1)) {
  160.                     replaceNumber++;
  161.                     checkingNumber++;
  162.                     int value = list.get(i - 1);
  163.                     list.set(i - 1, list.get(i));
  164.                     list.set(i, value);
  165.                     flag=false;
  166.                 }
  167.                 else
  168.                     checkingNumber++;
  169.             }
  170.         }
  171.         long finish=System.currentTimeMillis();
  172.         System.out.println("После: "+list);
  173.         System.out.println("Время выполнения: "+(finish-start));
  174.         System.out.println("Количество проверок: "+checkingNumber);
  175.         System.out.println("Количество обменов: "+replaceNumber);
  176.     }
  177.  
  178.     public static void setQuickSortCheckingNumber(int quick) {
  179.         quickSortCheckingNumber = quick;
  180.     }
  181.  
  182.     public static void setQuickSortReplaceNumber(int quick) {
  183.         quickSortReplaceNumber = quick;
  184.     }
  185.  
  186.     public static void bubbleString(List<String> list){ //пузырьковая сортировка строк по длине
  187.         long start=System.currentTimeMillis();
  188.         System.out.println("ДО: "+ list);
  189.         int replaceNumber=0;
  190.         int checkingNumber=0;
  191.         boolean flag=false;
  192.         while (!flag){
  193.             flag=true;
  194.             for(int i=1;i<list.size();i++) {
  195.                 if (list.get(i).length() <list.get(i - 1).length()) {
  196.                     replaceNumber++;
  197.                     checkingNumber++;
  198.                     String  value = list.get(i - 1);
  199.                     list.set(i - 1, list.get(i));
  200.                     list.set(i, value);
  201.                     flag=false;
  202.                 }
  203.                 else
  204.                     checkingNumber++;
  205.             }
  206.         }
  207.         long finish=System.currentTimeMillis();
  208.         System.out.println("После: "+list);
  209.         System.out.println("Время выполнения: "+(finish-start));
  210.         System.out.println("Количество проверок: "+checkingNumber);
  211.         System.out.println("Количество обменов: "+replaceNumber);;
  212.     }
  213.  
  214.     public static void shellInt(List<Integer> array) {
  215.         long start=System.currentTimeMillis();
  216.         int replaceNumber=0;
  217.         int checkingNumber=0;
  218.         System.out.println("ДО: "+ array);
  219.         int h = 1;
  220.         while (h*3 < array.size())
  221.             h = h * 3 + 1;
  222.  
  223.         while(h >= 1) {
  224.             int length = array.size();
  225.             for (int i = h; i < length; i++) {
  226.                 for (int j = i; j >= h; j = j - h) {
  227.                     if (array.get(j) < array.get(j-h)){
  228.                         int value=array.get(j);
  229.                         array.set(j,array.get(j-h));
  230.                         array.set(j-h,value);
  231.                         checkingNumber++;
  232.                         replaceNumber++;
  233.                     }
  234.                     else{
  235.                         checkingNumber++;
  236.                         break;
  237.                     }
  238.                 }
  239.             }
  240.             h = h/3;
  241.         }
  242.         long finish=System.currentTimeMillis();
  243.         System.out.println("После: "+array);
  244.         System.out.println("Время выполнения: "+(finish-start));
  245.         System.out.println("Количество проверок: "+checkingNumber);
  246.         System.out.println("Количество обменов: "+replaceNumber);
  247.     }
  248.  
  249.     public static void shellString(List<String> array) {
  250.         long start=System.currentTimeMillis();
  251.         int replaceNumber=0;
  252.         int checkingNumber=0;
  253.         System.out.println("ДО: "+ array);
  254.         int h = 1;
  255.         while (h*3 < array.size())
  256.             h = h * 3 + 1;
  257.  
  258.         while(h >= 1) {
  259.             int length = array.size();
  260.             for (int i = h; i < length; i++) {
  261.                 for (int j = i; j >= h; j = j - h) {
  262.                     if (array.get(j).length() < array.get(j-h).length()){
  263.                         String  value=array.get(j);
  264.                         array.set(j,array.get(j-h));
  265.                         array.set(j-h,value);
  266.                         checkingNumber++;
  267.                         replaceNumber++;
  268.                     }
  269.                     else{
  270.                         checkingNumber++;
  271.                         break;
  272.                     }
  273.                 }
  274.             }
  275.             h = h/3;
  276.         }
  277.         long finish=System.currentTimeMillis();
  278.         System.out.println("После: "+array);
  279.         System.out.println("Время выполнения: "+(finish-start));
  280.         System.out.println("Количество проверок: "+checkingNumber);
  281.         System.out.println("Количество обменов: "+replaceNumber);
  282.     }
  283.  
  284.     public static void quickInt(List<Integer> list){
  285.         long start=System.currentTimeMillis();
  286.         System.out.println("ДО: "+ list);
  287.         quickSort(list,0,list.size()-1);
  288.         long finish=System.currentTimeMillis();
  289.         System.out.println("После: "+list);
  290.         System.out.println("Время выполнения: "+(finish-start));
  291.         System.out.println("Количество проверок: "+quickSortCheckingNumber);
  292.         System.out.println("Количество обменов: "+quickSortReplaceNumber);
  293.         setQuickSortCheckingNumber(0);
  294.         setQuickSortReplaceNumber(0);
  295.     }
  296.  
  297.     public static void quickString(List<String> list){
  298.         long start=System.currentTimeMillis();
  299.         System.out.println("ДО: "+ list);
  300.         quickSortString(list,0,list.size()-1);
  301.         long finish=System.currentTimeMillis();
  302.         System.out.println("После: "+list);
  303.         System.out.println("Время выполнения: "+(finish-start));
  304.         System.out.println("Количество проверок: "+quickSortCheckingNumber);
  305.         System.out.println("Количество обменов: "+quickSortReplaceNumber);
  306.         setQuickSortCheckingNumber(0);
  307.         setQuickSortReplaceNumber(0);
  308.     }
  309.  
  310.     public static void LSDsortInt(List<Integer> array){
  311.         long start=System.currentTimeMillis();
  312.         sort(array);
  313.         long finish=System.currentTimeMillis();
  314.         System.out.println("После: "+array);
  315.         System.out.println("Время выполнения: "+(finish-start));
  316.         System.out.println("Количество проверок: "+quickSortCheckingNumber);
  317.         System.out.println("Количество обменов: "+quickSortReplaceNumber);
  318.         setQuickSortReplaceNumber(0);
  319.         setQuickSortCheckingNumber(0);
  320.     }
  321.  
  322.     private static void sort(List<Integer> array ){
  323.         int radix=10;
  324.         if (array.size()== 0) {
  325.             quickSortCheckingNumber++;
  326.             return;
  327.         }
  328.         // Determine minimum and maximum values
  329.         int minValue = array.get(0);
  330.         int maxValue = array.get(0);
  331.         for (int i = 1; i < array.size(); i++) {
  332.             if (array.get(i) < minValue) {
  333.                 quickSortCheckingNumber++;
  334.                 minValue = array.get(i);
  335.             } else if (array.get(i) > maxValue) {
  336.                 quickSortCheckingNumber++;
  337.                 maxValue = array.get(i);
  338.             }
  339.         }
  340.  
  341.         int exponent = 1;
  342.         while ((maxValue - minValue) / exponent >= 1) {
  343.            countingSortByDigit(array, radix, exponent, minValue);
  344.             exponent *= radix;
  345.         }
  346.     }
  347.  
  348.     private static void countingSortByDigit(List<Integer> array, int radix, int exponent, int minValue) {
  349.         int bucketIndex;
  350.         int[] buckets = new int[radix];
  351.         int[] output = new int[array.size()];
  352.  
  353.         // Initialize bucket
  354.         for (int i = 0; i < radix; i++) {
  355.             buckets[i] = 0;
  356.         }
  357.  
  358.         // Count frequencies
  359.         for (Integer integer : array) {
  360.             bucketIndex = (int) (((integer - minValue) / exponent) % radix);
  361.             buckets[bucketIndex]++;
  362.         }
  363.  
  364.         for (int i = 1; i < radix; i++) {
  365.             buckets[i] += buckets[i - 1];
  366.         }
  367.  
  368.         for (int i = array.size() - 1; i >= 0; i--) {
  369.             bucketIndex = (int)(((array.get(i) - minValue) / exponent) % radix);
  370.             output[--buckets[bucketIndex]] = array.get(i);
  371.         }
  372.         for (int i = 0; i < array.size(); i++) {
  373.             array.set(i,output[i]);
  374.             quickSortCheckingNumber++;
  375.             quickSortReplaceNumber++;
  376.         }
  377.     }
  378.  
  379.     public static void LSDsortString(List<String> array){
  380.         long start=System.currentTimeMillis();
  381.         sortString(array);
  382.         long finish=System.currentTimeMillis();
  383.         System.out.println("После: "+array);
  384.         System.out.println("Время выполнения: "+(finish-start));
  385.         System.out.println("Количество проверок: "+quickSortCheckingNumber);
  386.         System.out.println("Количество обменов: "+quickSortReplaceNumber);
  387.         setQuickSortReplaceNumber(0);
  388.         setQuickSortCheckingNumber(0);
  389.     }
  390.  
  391.     private static void sortString(List<String> array ){
  392.         int radix=10;
  393.         if (array.size()== 0) {
  394.             quickSortCheckingNumber++;
  395.             return;
  396.         }
  397.         // Determine minimum and maximum values
  398.         int minValue = array.get(0).length();
  399.         int maxValue = array.get(0).length();
  400.         for (int i = 1; i < array.size(); i++) {
  401.             if (array.get(i).length() < minValue) {
  402.                 quickSortCheckingNumber++;
  403.                 minValue = array.get(i).length();
  404.             } else if (array.get(i).length() > maxValue) {
  405.                 quickSortCheckingNumber++;
  406.                 maxValue = array.get(i).length();
  407.             }
  408.         }
  409.  
  410.         int exponent = 1;
  411.         while ((maxValue - minValue) / exponent >= 1) {
  412.             countingSortByDigitString(array, radix, exponent, minValue);
  413.             exponent *= radix;
  414.         }
  415.     }
  416.  
  417.     private static void countingSortByDigitString(List<String> array, int radix, int exponent, int minValue) {
  418.         int bucketIndex;
  419.         int[] buckets = new int[radix];
  420.         String[] output = new String[array.size()];
  421.  
  422.         // Initialize bucket
  423.         for (int i = 0; i < radix; i++) {
  424.             buckets[i] = 0;
  425.         }
  426.  
  427.         // Count frequencies
  428.         for (String integer : array) {
  429.             bucketIndex = (int) (((integer.length() - minValue) / exponent) % radix);
  430.             buckets[bucketIndex]++;
  431.         }
  432.  
  433.         for (int i = 1; i < radix; i++) {
  434.             buckets[i] += buckets[i - 1];
  435.         }
  436.  
  437.         for (int i = array.size() - 1; i >= 0; i--) {
  438.             bucketIndex = (int)(((array.get(i).length() - minValue) / exponent) % radix);
  439.             output[--buckets[bucketIndex]] = array.get(i);
  440.         }
  441.         for (int i = 0; i < array.size(); i++) {
  442.             array.set(i,output[i]);
  443.             quickSortCheckingNumber++;
  444.             quickSortReplaceNumber++;
  445.         }
  446.     }
  447.  
  448.     public static void menu() {
  449.         Scanner sc = new Scanner(System.in);
  450.         int choose1 = -1;
  451.         while (true) {
  452.             System.out.println("Выберете тип объекта, с которым нужно проводить сортировку: ");
  453.             System.out.println("Массив чисел-1");
  454.             System.out.println("Массив строк-2");
  455.             System.out.println("Список чисел-3");
  456.             System.out.println("Список строк-4");
  457.             System.out.println("Выход-0");
  458.             choose1 = sc.nextInt();
  459.             if (choose1 == 0)
  460.                 break;
  461.             System.out.println("Введите размерность массива: ");
  462.             int size = sc.nextInt();
  463.             while(true) {
  464.                 System.out.println("Выберете метод сортировки");
  465.                 System.out.println("Пузырьковая сортировка-1");
  466.                 System.out.println("Сортировка Шелла-2");
  467.                 System.out.println("Быстрая сортировка-3");
  468.                 System.out.println("LSD-сортировка-4");
  469.                 System.out.println("Выход на предыдащий шаг-0");
  470.                 int choose2 = sc.nextInt();
  471.                 if(choose2==0)
  472.                     break;
  473.                 else if (choose1 == 1) {
  474.                     List<Integer> list = Randomizer.randomArrayListInt(size);
  475.                     if (choose2 == 1) {
  476.                         bubbleInt(list);
  477.                     } else if (choose2 == 2) {
  478.                         shellInt(list);
  479.                     } else if (choose2 == 3) {
  480.                         quickInt(list);
  481.                     } else if (choose2 == 4) {
  482.                         LSDsortInt(list);
  483.                     }
  484.                 } else if (choose1 == 2) {
  485.                     List<String> list = Randomizer.randomArrayListString(size);
  486.                     if (choose2 == 1) {
  487.                         bubbleString(list);
  488.                     } else if (choose2 == 2) {
  489.                         shellString(list);
  490.                     } else if (choose2 == 3) {
  491.                         quickString(list);
  492.                     } else if (choose2 == 4) {
  493.                         LSDsortString(list);
  494.                     }
  495.                 } else if (choose1 == 3) {
  496.                     List<Integer> list = Randomizer.randomLinkedListInt(size);
  497.                     if (choose2 == 1) {
  498.                         bubbleInt(list);
  499.                     } else if (choose2 == 2) {
  500.                         shellInt(list);
  501.                     } else if (choose2 == 3) {
  502.                         quickInt(list);
  503.                     } else if (choose2 == 4) {
  504.                         LSDsortInt(list);
  505.                     }
  506.                 } else if (choose1 == 4) {
  507.                     List<String> list = Randomizer.randomLinkedListString(size);
  508.                     if (choose2 == 1) {
  509.                         bubbleString(list);
  510.                     } else if (choose2 == 2) {
  511.                         shellString(list);
  512.                     } else if (choose2 == 3) {
  513.                         quickString(list);
  514.                     } else if (choose2 == 4) {
  515.                         LSDsortString(list);
  516.                     }
  517.                 }
  518.             }
  519.         }
  520.     }
  521.  
  522. }
RAW Paste Data