Реализация BubbleSort в конце QuickSort

Question

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

static int num_comps; 

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

    // max size of array and number of N sets 
    int array_size = 32768; 
    int num_datasets = 10; 

    // array set to max size 
    int[] vals = new int[array_size]; 

    // temporary 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 size; 

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

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

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

     //set the temporary array to the actual array 
     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); 

     num_comps = 0; 
     quickSort(tvals, curr_size); 
     op_counts2[iter] = num_comps; 
    } 

    System.out.println("N  Bubble Sort OP Count Quick Sort OP Count"); 
    for (int k = 0; k < num_datasets; k++) 
    { 
    System.out.println(arraySizes[k] + "\t\t" + op_counts[k] + "\t\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 quickSort(int vals[], int curr_size) 
{ 
    quickSort_R(vals, 0, curr_size - 1); 
} 

static void quickSort_R(int vals[], int l, int r) 
{ 
    if (l < r) 
    { 
     if ((r-1) == 1) // two elements - trivial sort 
     { 
      num_comps = num_comps + 1; 
      if (vals[l] > vals[r]) 
       swap(vals, l, r); 
      return; 
     } 

     // partition the elements on the pivot s 
     int s = partition(vals, l, r); 

     //recurse on the two partitioned values 
     quickSort_R(vals, l, s-1); 
     quickSort_R(vals, s+1, r); 
    } 
} 

static int partition(int vals[], int l, int r) 
{ 
    int mid = (l+r)/2; 
    int p = medianOfThree(vals, l, r); 

    // swap with first element 
    swap(vals, l, p); 

    int pivot_val = vals[l]; 
    int i = l; 
    int j = r+1; 

    do 
    { 
     num_comps = num_comps + 1; 
     do 
     { 
      i = i + 1; 
      num_comps = num_comps + 1; 
     } while (vals[i] < pivot_val); 
     do 
     { 
      j = j - 1; 
      num_comps = num_comps + 1; 
     } while (vals[j] > pivot_val); 
     swap(vals, i, j); 
    } while (i < j); 

    swap(vals, i, j); // undo last swap 
    swap(vals, i, j); // put pivot at j, its correct position 

    return j; 
} 

static int medianOfThree(int vals[], int first, int last) 
{ 
    int mid = (first+last)/2; 
    if (vals[first] <= vals[mid] && vals[mid] <= vals[last]) 
    { 
     num_comps = num_comps + 1; 
     return mid; 
    } 
    else if (vals[mid] <= vals[first] && vals[first] <= vals[last]) 
    { 
     num_comps = num_comps + 1; 
     return first; 
    } 
    else 
     return last; 
} 

static void swap(int vals[], int i, int j) 
{ 
    int temp = vals[i]; 
    vals[i] = vals[j]; 
    vals[j] = temp; 
} 

}

Answer 1

EJP это правильно, но если вы хотите, просто изменить код следующим образом:

public static void quickSort_R(int vals[], int l, int r) { 
    if (l < r) { 
     if((r-l) < 10) { 
      bubbleSort(vals, r-l); //<--HERE 
     } 
     else { 
      if ((r-1) == 1) { // two elements - trivial sort 
       num_comps = num_comps + 1; 
       if (vals[l] > vals[r]) 
        swap(vals, l, r); 
       return; 
      } 

      // partition the elements on the pivot s 
      int s = partition(vals, l, r); 

      //recurse on the two partitioned values 
      quickSort_R(vals, l, s-1); 
      quickSort_R(vals, s+1, r); 
     } 
    } 
}