Advertisement
sfrsnyz

TIMP 4 V

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