代码之家  ›  专栏  ›  技术社区  ›  Adam

在快速排序结束时实现BubbleSort

  •  0
  • Adam  · 技术社区  · 13 年前

    我终于让我的bubblesort和quicksort工作了,但我很好奇如何更改我的代码,这样当我在quicksord中到达最后10个排序元素时,我会改为bubblesoort,以加快开销时间。

    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;
    }
    

    }

    1 回复  |  直到 13 年前
        1
  •  2
  •   Jared Nielsen    13 年前

    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);
            }
        }
    }