選擇排序和冒泡排序之間的比較次數保持不變

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算法似乎對我好。

兩者都具有相同的兩個循環，所以比較當前實現的計數確實導致相同的值。但是，我認爲你可以優化泡沫排序，以提前停止（當沒有交換時）。同樣，排序算法的強度取決於使用的算法，並且不一定是最少的比較量。因此，針對您的特定任務使用正確的算法，從而繞過特定任務的高成本操作非常重要！