おはようございます。5,000 個の要素の配列でのクイックソートのビッグ O 表記を明確にしたかったのです。クイックソートをランダムな順序 (200、20、4 など)、並べ替えた順序 (1、2、3、4、5 など)、および逆の並べ替え順序 (4999、4998、4997、4996 など) で実行しています。 ....) 真ん中からピボットを選択しています。
Big O 表記を調べると、クイックソートの場合は O (n log n) であることがわかります。これは、私にとっては ... 基数 2 のログを使用する場合、O(5000 * 12.287712) = 61438.56、基数を使用する場合10 log O(5000 * 3.69897) = 18494.85 なので、61438.56 を使用すると想定しています。出力 (以下に掲載) を見ると、それほど時間はかかりません。
私は、ランダムな順序、ソートされた順序、および逆のソートされた順序のテストから一般的に期待されるものを比較するときに、アイデアを得ようとしています。私は自分のJavaコードを5回実行した結果を投稿しましたが、考えすぎているか、間違った場所で比較を行っている可能性がありますが、異なるパスでの比較には大きな違いがあったと思います.
必要に応じてコードを投稿できますが、4 つのスペースをインデントすることができず、それを行う自動化された方法があるかどうかわからないため、問題がありました。
1 回目の実行: Random-Order-Number of swaps 16196 Sorted-Order-Number of swaps 18242 Reverse-Sorted-Number of swaps 22790
2 回目の実行: ランダム順序 - 行われたスワップの数 16072 ソートされた順序 - 行われたスワップの数 18118 リバース - ソート - 行われたスワップの数 22666
3 回目の実行: ランダム順序 - 行われたスワップの数 16205 ソートされた順序 - 行われたスワップの数 18251 リバース - ソート - 行われたスワップの数 22799
4 回目の実行: Random-Order-Number of swaps 16333 Sorted-Order-Number of swaps 18379 Reverse-Sorted-Number of swaps 22927
5 回目の実行: Random-Order-Number of swaps 16283 Sorted-Order-Number of swaps 18329 Reverse-Sorted-Number of swaps 22877
package QuickSort;
import java.util.Random;
public class QuickSortApp
{
/**
* @param args the command line arguments
*/
public static void main(String[] args)
{
// This for loop just runs through the code 20 times.
for(int loop = 0; loop < 20; loop++)
{
// This creates an array with 5000 random numbers
int maxSize = 5000;
ArrayQuickSort arr;
Random rnd = new Random();
arr = new ArrayQuickSort(maxSize);
ArrayQuickSort.setSwapCount(0);
ArrayQuickSort.setMedianCount(0);
for (int j = 0; j < maxSize; j++)
{
int n = rnd.nextInt(50000);
arr.insert(n);
}
// This creates a sorted array to test
ArrayQuickSort arrSorted;
arrSorted = new ArrayQuickSort(maxSize);
ArrayQuickSort.setSwapCount(0);
ArrayQuickSort.setMedianCount(0);
for (int j = 0; j < maxSize; j++)
{
int n = j + 1;
arrSorted.insert(n);
}
// This creates a reverse sorted array for checks
ArrayQuickSort arrReverseSorted;
arrReverseSorted = new ArrayQuickSort(maxSize);
ArrayQuickSort.setSwapCount(0);
ArrayQuickSort.setMedianCount(0);
for (int j = 5000; j > 0; j--)
{
int n = j;
arrReverseSorted.insert(n);
}
arr.quickSort();
System.out.println("Random-Order-Number of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount() );
arrSorted.quickSort();
System.out.println("Sorted-Order-Number of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount());
arrReverseSorted.quickSort();
System.out.println("Reverse-Sorted-Number of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount());
}
}
}
package QuickSort;
public class ArrayQuickSort {
private int[] theArray;
private int nElms;
private static int swapCount=0;
private static int medianCount = 0;
public ArrayQuickSort(int max) {
theArray = new int[max];
nElms = 0;
}
public void insert(int value) {
theArray[nElms] = value;
nElms++;
}
public void display() {
System.out.print("Array = ");
for (int i = 0; i < nElms; i++)
{
System.out.print(theArray[i] + " ");
if(i%25==0)
System.out.println();
}
System.out.println();
}
private void swap(int dx1, int dx2) {
int temp = theArray[dx1];
theArray[dx1] = theArray[dx2];
theArray[dx2] = temp;
swapCount++; // I am counting here to see how many times numbers are swapped.
}
private int medianOf3(int left, int right)
{
int center =(left+right)/2;
if(theArray[left] > theArray[center])
swap(left, center);
if(theArray[left] > theArray[right])
swap(left, right);
if(theArray[center] > theArray[right])
swap(center, right);
swap(center, right);
medianCount++; // I am counting here to see how many times the pivot is changed
return theArray[right];
}
public void quickSort()
{
recQuickSort(0, nElms -1);
}
private void recQuickSort(int left, int right)
{
int size = right-left+1;
if(size < 5)
insertionSort(left, right);
else
{
int median = medianOf3(left, right);
int partition = partitionIt(left, right, median);
recQuickSort(left, partition-1);
recQuickSort(partition+1, right);
}
}
private int partitionIt(int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right;
while (true) {
while (theArray[++leftPtr] < pivot)
;
while (theArray[--rightPtr] > pivot)
;
if(leftPtr >= rightPtr)
break;
else
swap(leftPtr, rightPtr);
}
swap(leftPtr, right);
return leftPtr;
}
private void insertionSort(int left, int right) {
int in, out;
for (out = left + 1; out <= right; out++) {
int temp = theArray[out];
in = out;
while (in > left && theArray[in - 1] >= temp) {
theArray[in] = theArray[in - 1];
in--;
}
theArray[in] = temp;
}
}
public static int getMedianCount()
{
return medianCount;
}
public static void setMedianCount(int medianCount)
{
ArrayQuickSort.medianCount = medianCount;
}
public static int getSwapCount()
{
return swapCount;
}
public static void setSwapCount(int swapCount)
{
ArrayQuickSort.swapCount = swapCount;
}
}