私はついにバブルソートとクイックソートを機能させましたが、コードを変更して、クイックソートでソートされている最後の10個の要素に到達したときに、代わりにバブルソートに変更してオーバーヘッド時間を短縮する方法に興味があります。
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;
}
}