sfrsnyz

LABA 4 timp Narhov

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