sfrsnyz

LABA 4 timp Pokudin

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