Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.LinkedList;
- import java.util.List;
- import java.util.Scanner;
- public class SortingClass {
- private static int quickSortCheckingNumber=0;
- private static int quickSortReplaceNumber=0;
- private static void quickSort(List<Integer> arr, int low, int high) {
- if (arr == null || arr.size() == 0){
- quickSortCheckingNumber++;
- return;
- }
- if (low >= high){
- quickSortCheckingNumber++;
- return;
- }
- int middle = low + (high - low) / 2;
- int pivot = arr.get(middle);
- int i = low, j = high;
- while (i <= j) {
- while (arr.get(i) < pivot) {
- quickSortCheckingNumber++;
- i++;
- }
- while (arr.get(j) > pivot) {
- quickSortCheckingNumber++;
- j--;
- }
- if (i <= j) {
- quickSortCheckingNumber++;
- quickSortReplaceNumber++;
- int temp = arr.get(i);
- arr.set(i,arr.get(j));
- arr.set(j,temp);
- i++;
- j--;
- }
- }
- if (low < j){
- quickSortCheckingNumber++;
- quickSort(arr, low, j);
- }
- if (high > i){
- quickSortCheckingNumber++;
- quickSort(arr, i, high);
- }
- }
- private static void quickSortString(List<String> arr, int low, int high) {
- if (arr == null || arr.size() == 0){
- quickSortCheckingNumber++;
- return;
- }
- if (low >= high){
- quickSortCheckingNumber++;
- return;
- }
- int middle = low + (high - low) / 2;
- String pivot = arr.get(middle);
- int i = low, j = high;
- while (i <= j) {
- while (arr.get(i).length() < pivot.length()) {
- quickSortCheckingNumber++;
- i++;
- }
- while (arr.get(j).length() > pivot.length()) {
- quickSortCheckingNumber++;
- j--;
- }
- if (i <= j) {
- quickSortCheckingNumber++;
- quickSortReplaceNumber++;
- String temp = arr.get(i);
- arr.set(i,arr.get(j));
- arr.set(j,temp);
- i++;
- j--;
- }
- }
- if (low < j){
- quickSortCheckingNumber++;
- quickSortString(arr, low, j);
- }
- if (high > i){
- quickSortCheckingNumber++;
- quickSortString(arr, i, high);
- }
- }
- public static void bubbleInt(List<Integer> list){ //пузорьковая сортировка чисел по возрастанию
- long start=System.currentTimeMillis();
- System.out.println("ДО: "+ list);
- boolean flag=false;
- int replaceNumber=0;
- int checkingNumber=0;
- while (!flag){
- flag=true;
- for(int i=1;i<list.size();i++) {
- if (list.get(i) <list.get(i - 1)) {
- replaceNumber++;
- checkingNumber++;
- int value = list.get(i - 1);
- list.set(i - 1, list.get(i));
- list.set(i, value);
- flag=false;
- }
- else
- checkingNumber++;
- }
- }
- long finish=System.currentTimeMillis();
- System.out.println("После: "+list);
- System.out.println("Время выполнения: "+(finish-start));
- System.out.println("Количество проверок: "+checkingNumber);
- System.out.println("Количество обменов: "+replaceNumber);
- }
- public static void setQuickSortCheckingNumber(int quick) {
- quickSortCheckingNumber = quick;
- }
- public static void setQuickSortReplaceNumber(int quick) {
- quickSortReplaceNumber = quick;
- }
- public static void bubbleString(List<String> list){ //пузырьковая сортировка строк по длине
- long start=System.currentTimeMillis();
- System.out.println("ДО: "+ list);
- int replaceNumber=0;
- int checkingNumber=0;
- boolean flag=false;
- while (!flag){
- flag=true;
- for(int i=1;i<list.size();i++) {
- if (list.get(i).length() <list.get(i - 1).length()) {
- replaceNumber++;
- checkingNumber++;
- String value = list.get(i - 1);
- list.set(i - 1, list.get(i));
- list.set(i, value);
- flag=false;
- }
- else
- checkingNumber++;
- }
- }
- long finish=System.currentTimeMillis();
- System.out.println("После: "+list);
- System.out.println("Время выполнения: "+(finish-start));
- System.out.println("Количество проверок: "+checkingNumber);
- System.out.println("Количество обменов: "+replaceNumber);;
- }
- public static void shellInt(List<Integer> array) {
- long start=System.currentTimeMillis();
- int replaceNumber=0;
- int checkingNumber=0;
- System.out.println("ДО: "+ array);
- int h = 1;
- while (h*3 < array.size())
- h = h * 3 + 1;
- while(h >= 1) {
- int length = array.size();
- for (int i = h; i < length; i++) {
- for (int j = i; j >= h; j = j - h) {
- if (array.get(j) < array.get(j-h)){
- int value=array.get(j);
- array.set(j,array.get(j-h));
- array.set(j-h,value);
- checkingNumber++;
- replaceNumber++;
- }
- else{
- checkingNumber++;
- break;
- }
- }
- }
- h = h/3;
- }
- long finish=System.currentTimeMillis();
- System.out.println("После: "+array);
- System.out.println("Время выполнения: "+(finish-start));
- System.out.println("Количество проверок: "+checkingNumber);
- System.out.println("Количество обменов: "+replaceNumber);
- }
- public static void shellString(List<String> array) {
- long start=System.currentTimeMillis();
- int replaceNumber=0;
- int checkingNumber=0;
- System.out.println("ДО: "+ array);
- int h = 1;
- while (h*3 < array.size())
- h = h * 3 + 1;
- while(h >= 1) {
- int length = array.size();
- for (int i = h; i < length; i++) {
- for (int j = i; j >= h; j = j - h) {
- if (array.get(j).length() < array.get(j-h).length()){
- String value=array.get(j);
- array.set(j,array.get(j-h));
- array.set(j-h,value);
- checkingNumber++;
- replaceNumber++;
- }
- else{
- checkingNumber++;
- break;
- }
- }
- }
- h = h/3;
- }
- long finish=System.currentTimeMillis();
- System.out.println("После: "+array);
- System.out.println("Время выполнения: "+(finish-start));
- System.out.println("Количество проверок: "+checkingNumber);
- System.out.println("Количество обменов: "+replaceNumber);
- }
- public static void quickInt(List<Integer> list){
- long start=System.currentTimeMillis();
- System.out.println("ДО: "+ list);
- quickSort(list,0,list.size()-1);
- long finish=System.currentTimeMillis();
- System.out.println("После: "+list);
- System.out.println("Время выполнения: "+(finish-start));
- System.out.println("Количество проверок: "+quickSortCheckingNumber);
- System.out.println("Количество обменов: "+quickSortReplaceNumber);
- setQuickSortCheckingNumber(0);
- setQuickSortReplaceNumber(0);
- }
- public static void quickString(List<String> list){
- long start=System.currentTimeMillis();
- System.out.println("ДО: "+ list);
- quickSortString(list,0,list.size()-1);
- long finish=System.currentTimeMillis();
- System.out.println("После: "+list);
- System.out.println("Время выполнения: "+(finish-start));
- System.out.println("Количество проверок: "+quickSortCheckingNumber);
- System.out.println("Количество обменов: "+quickSortReplaceNumber);
- setQuickSortCheckingNumber(0);
- setQuickSortReplaceNumber(0);
- }
- public static void LSDsortInt(List<Integer> array){
- long start=System.currentTimeMillis();
- sort(array);
- long finish=System.currentTimeMillis();
- System.out.println("После: "+array);
- System.out.println("Время выполнения: "+(finish-start));
- System.out.println("Количество проверок: "+quickSortCheckingNumber);
- System.out.println("Количество обменов: "+quickSortReplaceNumber);
- setQuickSortReplaceNumber(0);
- setQuickSortCheckingNumber(0);
- }
- private static void sort(List<Integer> array ){
- int radix=10;
- if (array.size()== 0) {
- quickSortCheckingNumber++;
- return;
- }
- // Determine minimum and maximum values
- int minValue = array.get(0);
- int maxValue = array.get(0);
- for (int i = 1; i < array.size(); i++) {
- if (array.get(i) < minValue) {
- quickSortCheckingNumber++;
- minValue = array.get(i);
- } else if (array.get(i) > maxValue) {
- quickSortCheckingNumber++;
- maxValue = array.get(i);
- }
- }
- int exponent = 1;
- while ((maxValue - minValue) / exponent >= 1) {
- countingSortByDigit(array, radix, exponent, minValue);
- exponent *= radix;
- }
- }
- private static void countingSortByDigit(List<Integer> array, int radix, int exponent, int minValue) {
- int bucketIndex;
- int[] buckets = new int[radix];
- int[] output = new int[array.size()];
- // Initialize bucket
- for (int i = 0; i < radix; i++) {
- buckets[i] = 0;
- }
- // Count frequencies
- for (Integer integer : array) {
- bucketIndex = (int) (((integer - minValue) / exponent) % radix);
- buckets[bucketIndex]++;
- }
- for (int i = 1; i < radix; i++) {
- buckets[i] += buckets[i - 1];
- }
- for (int i = array.size() - 1; i >= 0; i--) {
- bucketIndex = (int)(((array.get(i) - minValue) / exponent) % radix);
- output[--buckets[bucketIndex]] = array.get(i);
- }
- for (int i = 0; i < array.size(); i++) {
- array.set(i,output[i]);
- quickSortCheckingNumber++;
- quickSortReplaceNumber++;
- }
- }
- public static void LSDsortString(List<String> array){
- long start=System.currentTimeMillis();
- sortString(array);
- long finish=System.currentTimeMillis();
- System.out.println("После: "+array);
- System.out.println("Время выполнения: "+(finish-start));
- System.out.println("Количество проверок: "+quickSortCheckingNumber);
- System.out.println("Количество обменов: "+quickSortReplaceNumber);
- setQuickSortReplaceNumber(0);
- setQuickSortCheckingNumber(0);
- }
- private static void sortString(List<String> array ){
- int radix=10;
- if (array.size()== 0) {
- quickSortCheckingNumber++;
- return;
- }
- // Determine minimum and maximum values
- int minValue = array.get(0).length();
- int maxValue = array.get(0).length();
- for (int i = 1; i < array.size(); i++) {
- if (array.get(i).length() < minValue) {
- quickSortCheckingNumber++;
- minValue = array.get(i).length();
- } else if (array.get(i).length() > maxValue) {
- quickSortCheckingNumber++;
- maxValue = array.get(i).length();
- }
- }
- int exponent = 1;
- while ((maxValue - minValue) / exponent >= 1) {
- countingSortByDigitString(array, radix, exponent, minValue);
- exponent *= radix;
- }
- }
- private static void countingSortByDigitString(List<String> array, int radix, int exponent, int minValue) {
- int bucketIndex;
- int[] buckets = new int[radix];
- String[] output = new String[array.size()];
- // Initialize bucket
- for (int i = 0; i < radix; i++) {
- buckets[i] = 0;
- }
- // Count frequencies
- for (String integer : array) {
- bucketIndex = (int) (((integer.length() - minValue) / exponent) % radix);
- buckets[bucketIndex]++;
- }
- for (int i = 1; i < radix; i++) {
- buckets[i] += buckets[i - 1];
- }
- for (int i = array.size() - 1; i >= 0; i--) {
- bucketIndex = (int)(((array.get(i).length() - minValue) / exponent) % radix);
- output[--buckets[bucketIndex]] = array.get(i);
- }
- for (int i = 0; i < array.size(); i++) {
- array.set(i,output[i]);
- quickSortCheckingNumber++;
- quickSortReplaceNumber++;
- }
- }
- public static void menu() {
- Scanner sc = new Scanner(System.in);
- int choose1 = -1;
- while (true) {
- System.out.println("Выберете тип объекта, с которым нужно проводить сортировку: ");
- System.out.println("Массив чисел-1");
- System.out.println("Массив строк-2");
- System.out.println("Список чисел-3");
- System.out.println("Список строк-4");
- System.out.println("Выход-0");
- choose1 = sc.nextInt();
- if (choose1 == 0)
- break;
- System.out.println("Введите размерность массива: ");
- int size = sc.nextInt();
- while(true) {
- System.out.println("Выберете метод сортировки");
- System.out.println("Обменная сортировка-1");
- System.out.println("Сортировка Шелла-2");
- System.out.println("Быстрая сортировка-3");
- System.out.println("LSD-сортировка-4");
- System.out.println("Выход на предыдащий шаг-0");
- int choose2 = sc.nextInt();
- if(choose2==0)
- break;
- else if (choose1 == 1) {
- List<Integer> list = Randomizer.randomArrayListInt(size);
- if (choose2 == 1) {
- bubbleInt(list);
- } else if (choose2 == 2) {
- shellInt(list);
- } else if (choose2 == 3) {
- quickInt(list);
- } else if (choose2 == 4) {
- LSDsortInt(list);
- }
- } else if (choose1 == 2) {
- List<String> list = Randomizer.randomArrayListString(size);
- if (choose2 == 1) {
- bubbleString(list);
- } else if (choose2 == 2) {
- shellString(list);
- } else if (choose2 == 3) {
- quickString(list);
- } else if (choose2 == 4) {
- LSDsortString(list);
- }
- } else if (choose1 == 3) {
- List<Integer> list = Randomizer.randomLinkedListInt(size);
- if (choose2 == 1) {
- bubbleInt(list);
- } else if (choose2 == 2) {
- shellInt(list);
- } else if (choose2 == 3) {
- quickInt(list);
- } else if (choose2 == 4) {
- LSDsortInt(list);
- }
- } else if (choose1 == 4) {
- List<String> list = Randomizer.randomLinkedListString(size);
- if (choose2 == 1) {
- bubbleString(list);
- } else if (choose2 == 2) {
- shellString(list);
- } else if (choose2 == 3) {
- quickString(list);
- } else if (choose2 == 4) {
- LSDsortString(list);
- }
- }
- }
- }
- }
- private static class Randomizer { //класс для генерации структур данных произвольного размера
- public static ArrayList<Integer> randomArrayListInt(int size){
- ArrayList<Integer> arr=new ArrayList<>();
- for(int i=0;i<size;i++){
- arr.add((int)(Math.random()*200+1));
- }
- return arr;
- }
- public static LinkedList<Integer> randomLinkedListInt(int size){
- LinkedList<Integer> arr=new LinkedList<>();
- for(int i=0;i<size;i++){
- arr.add((int)(Math.random()*200+1));
- }
- return arr;
- }
- public static ArrayList<String > randomArrayListString(int size){
- ArrayList<String> arr=new ArrayList<>();
- for(int i=0;i<size;i++){
- arr.add(randomString());
- }
- return arr;
- }
- public static LinkedList<String> randomLinkedListString(int size){
- LinkedList<String> arr=new LinkedList<>();
- for(int i=0;i<size;i++){
- arr.add(randomString());
- }
- return arr;
- }
- private static String randomString()
- {
- int n=(int)(Math.random()*100+1);
- String AlphaNumericString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + "0123456789" + "abcdefghijklmnopqrstuvxyz";
- StringBuilder sb = new StringBuilder(n);
- for (int i = 0; i < n; i++) {
- int index = (int)(AlphaNumericString.length() * Math.random());
- sb.append(AlphaNumericString.charAt(index));
- }
- return sb.toString();
- }
- }
- }
- /////////////
- public class Main {
- public static void main(String[] args) {
- SortingClass.menu();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement