SelectionSort и BubbleSort - как подсчитать количество сравнений и обмен номерами?

Question

Прежде всего, я видел аналогичный вопрос, связанный с C++, но я не совсем понял его - плюс мой вопрос о Java.

В принципе, я закодировал два метода, которые могут использовать SelectionSort и BubbleSort в анализируемом массиве. Хотя я считаю, что у меня есть методы, работающие корректно (у меня есть тесты, и все они отсортировали числа в порядке возрастания), я не уверен, правильно ли я рассчитываю количество сравнений и числовых свопов. Если кто-то сможет проверить мой код ниже и предложить некоторые отзывы, я буду очень благодарен.

Примечание. Я могу заархивировать файлы проекта Java и отправлять их кому-либо, если это необходимо.

BubbleSort метод:

public String bubbleSort(int[] numbers) 
    { 
     System.out.println("******|Bubble Sort|******"); 
     StringBuilder originalArray = new StringBuilder(); 

     for(int i = 0; i <= numbers.length - 1; i++) 
     { 
      originalArray.append(numbers[i] + " "); 
     } 
     System.out.println("Original array: " + originalArray); 
     int temp; // temporary variable 

     //Set boolean variable to true, 
     //to allow the first pass. 
     boolean pass = true; 

     int comparisons = 0; 
     int swaps = 0; 

     //While a pass can be made, 
     while(pass) 
     { 
      //Set the boolean value to false, 
      //indicating a number swap could 
      //be made. 
      pass = false; 

      for(int i = 0; i < numbers.length - 1; i++) 
      { 
       //increment the number of comparisons by 1. 
       comparisons++; 
       if(numbers[i] > numbers[i+1]) 
       { 
        temp = numbers[i]; 
        numbers[i] = numbers[i + 1]; 
        numbers[i+1] = temp; 

        //increment the amount of swaps made by 1, 
        //to put numbers in correct order. 
        swaps++; 
        pass = true; 
       } 
      } 
     } 

     //Create a StringBuilder object - to hold 
     //the output of sorted numbers. 
     StringBuilder sb = new StringBuilder(); 

     //Loop through the now sorted array - appending 
     //each subsequent number in the array to the 
     //StringBuilder object. 
     for(int i = 0; i < numbers.length; i++) 
     { 
      sb.append(numbers[i] + " "); 
     } 

     //Return the final results of the sorted array. 
     return "Sorted Array (asc): " + sb.toString() + "\nComparisons made: " + comparisons 
       + "\nSwaps made: " + swaps; 
    } 

метод сортировка выбором

public String selectionSort(int[] numbers) 
    { 
     System.out.println("******|Selection Sort|******"); 
     StringBuilder originalArray = new StringBuilder(); 

     int comparisons = 0; 
     int swaps = 0; 

     for(int i = 0; i <= numbers.length - 1; i++) 
     { 
      originalArray.append(numbers[i] + " "); 
     } 
     System.out.println("Original array: " + originalArray); 

     //Declare variable to hold first element 
     int first; 

     //declare temporary variable, to be used in 
     //swapping integers. 
     int temp; 

     for(int x = numbers.length - 1; x > 0; x--) 
     { 
      first = 0; 
      comparisons++; 
      for(int y = 1; y <= x; y++) 
      { 
       //comparisons++; 
       if(numbers[y] > numbers[first]) 
       { 
        first = y; 
        //comparisons++; 
        swaps++; 
       } 
       temp = numbers[first]; 
       numbers[first] = numbers[x]; 
       numbers[x] = temp; 
       //swaps++; 
      } 
     } 

     //Create a StringBuilder object - to hold 
     //the output of sorted numbers. 
     StringBuilder sb = new StringBuilder(); 

     //Loop through the now sorted array - appending 
     //each subsequent number in the array to the 
     //StringBuilder object. 
     for(int i = 0; i < numbers.length; i++) 
     { 
      sb.append(numbers[i] + " "); 
     } 

     //Return the final results of the sorted array. 
     return "Sorted Array (asc): " + sb.toString() + "\nComparisons made: " + comparisons 
       + "\nSwaps made: " + swaps; 
    } 

Answer 1

Для пузырьковой сортировки:

сравнений ключей ->(N * (N-1))/2

Пункт назначения (свопы) ->3 * (п-1)

Для выбора СНП:

Ключевые сличения ->(п * (п-1))/2 (такой же, как пузырь)

Пункт Назначения (свопы) ->(N * (N-1))/4

(Обратите внимание, что п является номер вашего размера массива)