sfrsnyz

Григорьев ТИМП ЛАБА 4

May 8th, 2021
809
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 sort=new SortingClass();
  5.         sort.Manual();
  6.     }
  7. }
  8.  
  9. //////////// Random
  10. import java.util.ArrayList;
  11. import java.util.LinkedList;
  12.  
  13. public class Random {
  14.     public ArrayList<Integer> randomArrayListInt(int size){
  15.         ArrayList<Integer> arr=new ArrayList<>();
  16.         for(int i=0;i<size;i++){
  17.             arr.add((int)(Math.random()*200+1));
  18.         }
  19.         return arr;
  20.     }
  21.     public LinkedList<Integer> randomLinkedListInt(int size){
  22.         LinkedList<Integer> arr=new LinkedList<>();
  23.         for(int i=0;i<size;i++){
  24.             arr.add((int)(Math.random()*200+1));
  25.         }
  26.         return arr;
  27.     }
  28.     public  ArrayList<String > randomArrayListString(int size){
  29.         ArrayList<String> arr=new ArrayList<>();
  30.         for(int i=0;i<size;i++){
  31.             arr.add(randomString());
  32.         }
  33.         return arr;
  34.     }
  35.     public LinkedList<String> randomLinkedListString(int size){
  36.         LinkedList<String> arr=new LinkedList<>();
  37.         for(int i=0;i<size;i++){
  38.             arr.add(randomString());
  39.         }
  40.         return arr;
  41.     }
  42.  
  43.     private String randomString()
  44.     {
  45.         int n=(int)(Math.random()*100+1);
  46.         String AlphaNumericString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + "0123456789" + "abcdefghijklmnopqrstuvxyz";
  47.         StringBuilder sb = new StringBuilder(n);
  48.         for (int i = 0; i < n; i++) {
  49.             int index = (int)(AlphaNumericString.length() * Math.random());
  50.             sb.append(AlphaNumericString.charAt(index));
  51.         }
  52.         return sb.toString();
  53.     }
  54. }
  55.  
  56. ///////////// SortingClass
  57.  
  58.  
  59. import java.util.List;
  60. import java.util.Scanner;
  61.  
  62. public class SortingClass {
  63.     private int CheckingNumber=0;
  64.     private int ReplaceNumber=0;
  65.  
  66.     public void hairbrushSortInt(List<Integer> list){ //сортировка расечской чисел
  67.         long start=System.currentTimeMillis();
  68.         System.out.println("ДО: "+ list);
  69.         boolean check=false;
  70.         int replace=0;
  71.         int checking=0;
  72.         while (!check){
  73.             check=true;
  74.             for(int i=1;i<list.size();i++) {
  75.                 if (list.get(i) <list.get(i - 1)) {
  76.                     replace++;
  77.                     checking++;
  78.                     int value = list.get(i - 1);
  79.                     list.set(i - 1, list.get(i));
  80.                     list.set(i, value);
  81.                     check=false;
  82.                 }
  83.                 else
  84.                     checking++;
  85.             }
  86.         }
  87.         long finish=System.currentTimeMillis();
  88.         System.out.println("После: "+list);
  89.         System.out.println("Время выполнения: "+(finish-start));
  90.         System.out.println("Количество проверок: "+checking);
  91.         System.out.println("Количество обменов: "+replace);
  92.         System.out.println();
  93.     }
  94.     private void hairBrushSortString(List<String> list){ //сортировка расческой строк
  95.         long start=System.currentTimeMillis();
  96.         System.out.println("ДО: "+ list);
  97.         int replace=0;
  98.         int checking=0;
  99.         boolean check=false;
  100.         while (!check){
  101.             check=true;
  102.             for(int i=1;i<list.size();i++) {
  103.                 if (list.get(i).length() <list.get(i - 1).length()) {
  104.                     replace++;
  105.                     checking++;
  106.                     String  value = list.get(i - 1);
  107.                     list.set(i - 1, list.get(i));
  108.                     list.set(i, value);
  109.                     check=false;
  110.                 }
  111.                 else
  112.                     checking++;
  113.             }
  114.         }
  115.         long finish=System.currentTimeMillis();
  116.         System.out.println("После: "+list);
  117.         System.out.println("Время выполнения: "+(finish-start));
  118.         System.out.println("Количество проверок: "+checking);
  119.         System.out.println("Количество обменов: "+replace);;
  120.         System.out.println();
  121.     }
  122.     private  void quickSortInt(List<Integer> arr, int low, int high) {
  123.         if (arr == null || arr.size() == 0){
  124.             CheckingNumber++;
  125.             return;
  126.         }
  127.         if (low >= high){
  128.             CheckingNumber++;
  129.             return;
  130.         }
  131.         int middle = low + (high - low) / 2;
  132.         int pivot = arr.get(middle);
  133.         int i = low, j = high;
  134.         while (i <= j) {
  135.             while (arr.get(i) < pivot) {
  136.                 CheckingNumber++;
  137.                 i++;
  138.             }
  139.             while (arr.get(j) > pivot) {
  140.                 CheckingNumber++;
  141.                 j--;
  142.             }
  143.  
  144.             if (i <= j) {
  145.                 CheckingNumber++;
  146.                ReplaceNumber++;
  147.                 int temp = arr.get(i);
  148.                 arr.set(i,arr.get(j));
  149.                 arr.set(j,temp);
  150.                 i++;
  151.                 j--;
  152.             }
  153.         }
  154.         if (low < j){
  155.             CheckingNumber++;
  156.             quickSortInt(arr, low, j);
  157.         }
  158.         if (high > i){
  159.             CheckingNumber++;
  160.             quickSortInt(arr, i, high);
  161.         }
  162.     }
  163.     private  void quickSortString(List<String> arr, int low, int high) {
  164.         if (arr == null || arr.size() == 0){ CheckingNumber++;
  165.             return;
  166.         }
  167.         if (low >= high){
  168.             CheckingNumber++;
  169.             return;
  170.         }
  171.         int middle = low + (high - low) / 2;
  172.         String  pivot = arr.get(middle);
  173.         int i = low, j = high;
  174.         while (i <= j) {
  175.             while (arr.get(i).length() < pivot.length()) { CheckingNumber++;
  176.                 i++;
  177.             }
  178.             while (arr.get(j).length() > pivot.length()) { CheckingNumber++;
  179.                 j--;
  180.             }
  181.  
  182.             if (i <= j) { CheckingNumber++;ReplaceNumber++;
  183.                 String temp = arr.get(i);
  184.                 arr.set(i,arr.get(j));
  185.                 arr.set(j,temp);
  186.                 i++;
  187.                 j--;
  188.             }
  189.         }
  190.         if (low < j){ CheckingNumber++;
  191.             quickSortString(arr, low, j);
  192.         }
  193.         if (high > i){
  194.             CheckingNumber++;
  195.             quickSortString(arr, i, high);
  196.         }
  197.     }
  198.     private void fastSortInt(List<Integer> list){ // быстрая сортировка чисел
  199.         long start=System.currentTimeMillis();
  200.         System.out.println("ДО: "+ list);
  201.         quickSortInt(list,0,list.size()-1);
  202.         long finish=System.currentTimeMillis();
  203.         System.out.println("После: "+list);
  204.         System.out.println("Время выполнения: "+(finish-start));
  205.         System.out.println("Количество проверок: "+CheckingNumber);
  206.         System.out.println("Количество обменов: "+ReplaceNumber);
  207.         System.out.println();
  208.         CheckingNumber=0;
  209.         ReplaceNumber=0;
  210.     }
  211.     private void fastSortString(List<String> list){ //быстрая сортировка строк
  212.         long start=System.currentTimeMillis();
  213.         System.out.println("ДО: "+ list);
  214.         quickSortString(list,0,list.size()-1);
  215.         long finish=System.currentTimeMillis();
  216.         System.out.println("После: "+list);
  217.         System.out.println("Время выполнения: "+(finish-start));
  218.         System.out.println("Количество проверок: "+CheckingNumber);
  219.         System.out.println("Количество обменов: "+ReplaceNumber);
  220.         System.out.println();
  221.         CheckingNumber=0;
  222.         ReplaceNumber=0;
  223.     }
  224.     private void pasteSortString(List<String> list) { //сортировка вставками строк
  225.         long start=System.currentTimeMillis();
  226.         int replaceNumber=0;
  227.         int checkingNumber=0;
  228.         System.out.println("ДО: "+ list);
  229.         int h = 1;
  230.         while (h*3 < list.size())
  231.             h = h * 3 + 1;
  232.  
  233.         while(h >= 1) {
  234.             int length = list.size();
  235.             for (int i = h; i < length; i++) {
  236.                 for (int j = i; j >= h; j = j - h) {
  237.                     if (list.get(j).length() < list.get(j-h).length()){
  238.                         String  value=list.get(j);
  239.                         list.set(j,list.get(j-h));
  240.                         list.set(j-h,value);
  241.                         checkingNumber++;
  242.                         replaceNumber++;
  243.                     }
  244.                     else{
  245.                         checkingNumber++;
  246.                         break;
  247.                     }
  248.                 }
  249.             }
  250.             h = h/3;
  251.         }
  252.         long finish=System.currentTimeMillis();
  253.         System.out.println("После: "+list);
  254.         System.out.println("Время выполнения: "+(finish-start));
  255.         System.out.println("Количество проверок: "+checkingNumber);
  256.         System.out.println("Количество обменов: "+replaceNumber);
  257.         System.out.println();
  258.     }
  259.     private void pasteSortInt(List<Integer> list) { //сортировка вставками чисел
  260.         long start=System.currentTimeMillis();
  261.         int replaceNumber=0;
  262.         int checkingNumber=0;
  263.         System.out.println("ДО: "+ list);
  264.         int h = 1;
  265.         while (h*3 < list.size())
  266.             h = h * 3 + 1;
  267.  
  268.         while(h >= 1) {
  269.             int length = list.size();
  270.             for (int i = h; i < length; i++) {
  271.                 for (int j = i; j >= h; j = j - h) {
  272.                     if (list.get(j) < list.get(j-h)){
  273.                         int value=list.get(j);
  274.                         list.set(j,list.get(j-h));
  275.                         list.set(j-h,value);
  276.                         checkingNumber++;
  277.                         replaceNumber++;
  278.                     }
  279.                     else{
  280.                         checkingNumber++;
  281.                         break;
  282.                     }
  283.                 }
  284.             }
  285.             h = h/3;
  286.         }
  287.         long finish=System.currentTimeMillis();
  288.         System.out.println("После: "+list);
  289.         System.out.println("Время выполнения: "+(finish-start));
  290.         System.out.println("Количество проверок: "+checkingNumber);
  291.         System.out.println("Количество обменов: "+replaceNumber);
  292.         System.out.println();
  293.     }
  294.     private void countingSortInt(List<Integer> list){//сортировка подсчетом чисел
  295.         long start=System.currentTimeMillis();
  296.         int replaceNumber=0;
  297.         int checkingNumber=0;
  298.         System.out.println("ДО: "+ list);
  299.         for (int left = 0; left < list.size(); left++) {
  300.             int minInd = left;
  301.             for (int i = left; i < list.size(); i++) {
  302.                 if (list.get(i) < list.get(minInd)) {
  303.                     checkingNumber++;
  304.                     minInd = i;
  305.                 }
  306.             }
  307.             int value= list.get(left);
  308.             list.set(left,list.get(minInd));
  309.             list.set(minInd, value);
  310.             replaceNumber++;
  311.         }
  312.         long finish=System.currentTimeMillis();
  313.         System.out.println("После: "+list);
  314.         System.out.println("Время выполнения: "+(finish-start));
  315.         System.out.println("Количество проверок: "+checkingNumber);
  316.         System.out.println("Количество обменов: "+replaceNumber);
  317.         System.out.println();
  318.     }
  319.     private void countingSortString(List<String > list){//сортировка подсчетом строк
  320.         long start=System.currentTimeMillis();
  321.         int replaceNumber=0;
  322.         int checkingNumber=0;
  323.         System.out.println("ДО: "+ list);
  324.         for (int left = 0; left < list.size(); left++) {
  325.             int minInd = left;
  326.             for (int i = left; i < list.size(); i++) {
  327.                 if (list.get(i).length() < list.get(minInd).length()) {
  328.                     checkingNumber++;
  329.                     minInd = i;
  330.                 }
  331.             }
  332.             String  value= list.get(left);
  333.             list.set(left,list.get(minInd));
  334.             list.set(minInd, value);
  335.             replaceNumber++;
  336.         }
  337.         long finish=System.currentTimeMillis();
  338.         System.out.println("После: "+list);
  339.         System.out.println("Время выполнения: "+(finish-start));
  340.         System.out.println("Количество проверок: "+checkingNumber);
  341.         System.out.println("Количество обменов: "+replaceNumber);
  342.         System.out.println();
  343.     }
  344.     public void Manual() {
  345.         Scanner sc = new Scanner(System.in);
  346.         int choose1 = 10;
  347.         while (true) {
  348.             Random rand=new Random();
  349.             System.out.println("Выберете тип объекта, с которым нужно проводить сортировку: ");
  350.             System.out.println("Массив чисел-1");
  351.             System.out.println("Массив строк-2");
  352.             System.out.println("Связный список чисел-3");
  353.             System.out.println("Связный список строк-4");
  354.             System.out.println("Выход-0");
  355.             choose1 = sc.nextInt();
  356.             if (choose1 ==0)
  357.                 break;
  358.             System.out.println("Введите размерность массива: ");
  359.             int size = sc.nextInt();
  360.             while(true) {
  361.                 System.out.println("Выберете метод сортировки");
  362.                 System.out.println("Сортировка расческой-1");
  363.                 System.out.println("Сортировка вставками-2");
  364.                 System.out.println("Быстрая сортировка (разделитель справа)-3");
  365.                 System.out.println("Сортировка подсчетом-4");
  366.                 System.out.println("Выход на предыдащий шаг-0");
  367.                 int choose2 = sc.nextInt();
  368.                 if(choose2==0)
  369.                     break;
  370.                 else if (choose1 == 1) {
  371.                     List<Integer> list = rand.randomArrayListInt(size);
  372.                     if (choose2 == 1) {
  373.                         hairbrushSortInt(list);
  374.                     } else if (choose2 == 2) {
  375.                         pasteSortInt(list);
  376.                     } else if (choose2 == 3) {
  377.                        fastSortInt(list);
  378.                     } else if (choose2 == 4) {
  379.                        countingSortInt(list);
  380.                     }
  381.                 }
  382.                 else if (choose1 == 2) {
  383.                     List<String> list = rand.randomArrayListString(size);
  384.                     if (choose2 == 1) {
  385.                         countingSortString(list);
  386.                     } else if (choose2 == 2) {
  387.                         countingSortString(list);
  388.                     } else if (choose2 == 3) {
  389.                         countingSortString(list);
  390.                     } else if (choose2 == 4) {
  391.                         countingSortString(list);
  392.                     }
  393.                 }
  394.                 else if (choose1 == 3) {
  395.                     List<Integer> list = rand.randomLinkedListInt(size);
  396.                     if (choose2 == 1) {
  397.                         hairbrushSortInt(list);
  398.                     } else if (choose2 == 2) {
  399.                         pasteSortInt(list);
  400.                     } else if (choose2 == 3) {
  401.                         fastSortInt(list);
  402.                     } else if (choose2 == 4) {
  403.                         countingSortInt(list);
  404.                     }
  405.                 }
  406.                 else if (choose1 == 4) {
  407.                     List<String> list = rand.randomLinkedListString(size);
  408.                     if (choose2 == 1) {
  409.                         countingSortString(list);
  410.                     } else if (choose2 == 2) {
  411.                         countingSortString(list);
  412.                     } else if (choose2 == 3) {
  413.                         countingSortString(list);
  414.                     } else if (choose2 == 4) {
  415.                         countingSortString(list);
  416.                     }
  417.                 }
  418.             }
  419.         }
  420.     }
  421. }
  422.  
RAW Paste Data