Количество сравнений между сортировкой сортировки и сортировкой пузырьков продолжает расти одинаково

Question

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

static int num_comps; 

public static void main(String[] args) 
{ 
    Random rnd = new Random(); 

    // max size of array 
    // number of N inputs 
    int array_size = 32768; 
    int num_datasets = 12; 

    // allocate array once to the max size 
    int[] vals = new int[array_size]; 

    // temp array with allocated array to max size 
    int[] tvals = new int[array_size]; 

    // array to hold operation counts 
    int[] op_counts = new int[num_datasets]; 
    int[] op_counts2 = new int[num_datasets]; 

    // array to hold the size of each array 
    // 
    int[] arraySizes = new int[num_datasets]; 

    int i; 
    int j; 
    int sz; 

    for (i = 0, sz = 16; i < num_datasets; i++, sz *= 2) 
     arraySizes[i] = sz; 

    for (int iter = 0; iter < num_datasets; iter++) 
    { 
     int curr_size = arraySizes[iter]; 

     // load array with random values 
     // 
     for (i = 0; i < curr_size; i++) 
      vals[i] = rnd.nextInt(4999); 

     for (i = 0; i < curr_size; i++) 
      tvals[i] = vals[i]; 

     // run the bubble sort algorithm 
     // 
     num_comps = 0; 
     bubbleSort(tvals, curr_size); 
     op_counts[iter] = num_comps; 
     //System.out.println("Num comps at " + iter + " is " + num_comps); 

     // run the selection-sort algorithm 
     num_comps = 0; 
     selectionSort(tvals, curr_size); 
     op_counts2[iter] = num_comps; 
     //System.out.println("Num comps at " + iter + " is " + num_comps); 
    } 

    System.out.println("Operation Counts (N vs. op Count): "); 
    for (int k = 0; k < num_datasets; k++) 
     System.out.println(arraySizes[k] + "\t\t" + op_counts[k] + "\t\t" + op_counts2[k]); 
} 

static void bubbleSort(int vals[], int curr_size) 
{ 
    int temp; 
    for (int i = 0; i < curr_size - 1; i++) 
    { 
     for (int j = 0; j < curr_size - i - 1; j++) 
     { 
      // swap 
      num_comps = num_comps + 1; 
      if (vals[j+1] < vals[j]) 
      { 
       temp = vals[j]; 
       vals[j] = vals[j+1]; 
       vals[j+1] = temp; 
      } 
     } 
    } 
} 

static void selectionSort(int vals[], int curr_size) 
{ 
    int temp; 
    for(int i=0; i<curr_size - 1; i++) 
    { 
     for(int j=i+1; j<curr_size; j++) 
     { 
      num_comps = num_comps + 1; 
      if(vals[i] > vals[j]) 
      { 
       temp = vals[j]; 
       vals[j] = vals[i]; 
       vals[i] = temp; 
      } 
     } 
    } 
} 

Answer 1

Ваш selection sort алгоритм не выполняет поиск наименьшего значения в списке. И заменив его потом индексом внешнего цикла.

Вы должны сделать что-то вроде этого:

static void selectionSort(int vals[], int curr_size) 
{ 
    int temp; 
    for(int i=0; i<curr_size - 1; i++) 
    { 
     int lowest = i; 
     for(int j=i+1; j<curr_size; j++) 
     { 
      num_comps = num_comps + 1; 
      if(vals[lowest] > vals[j]) 
      { 
       lowest = j; 
      } 
     } 

     // swap lowest with current index 
     temp = vals[lowest]; 
     vals[lowest] = vals[i]; 
     vals[i] = temp; 
    } 
} 

(конечно, это может быть оптимизировано дополнительно) Сила этого алгоритма является не количество сравнений, но это количество свопы (который находится в минимум, я полагаю).

Ваш bubble sort алгоритм кажется мне в порядке.

Оба имеют те же две петли, поэтому сравнение отсчетов текущих реализаций действительно приводит к тем же значениям. Но, я думаю, вы можете оптимизировать сортировку пузырьков, чтобы остановиться раньше (когда не было найдено свопов). Опять же, сила алгоритмов сортировки зависит от использованных и не обязательно является наименьшим количеством сравнений. Таким образом, использование правильного алгоритма для вашей конкретной задачи и, тем самым, обход задач высокой стоимости, связанных с конкретными задачами, важно!