6

重複の可能性：
Javaでランダムピボットを使用したクイックソート

以下に記述されているクイックソートのコードは、配列の最初の要素をピボットとして使用してから、配列を並べ替えます。ここで、最初のピボットではなくランダムにピボットを取得してから配列を並べ替えたいのですが、行き詰まりました。完璧な結果を得るために、以下のコードでどのような変更を加えることができるか教えてください。

import java.util.*;
import javax.swing.JOptionPane;

public class Quicksort {

public static void main(String[] args) {
    String arraylength = JOptionPane.showInputDialog("Enter the length of the array.");

    int a = Integer.parseInt(arraylength);
    if (a == 0) {
        System.out.println("Null Length");
    } else {
        int[] list = new int[a];


        for (int i = 0; i < a; i++) {
            String input = JOptionPane.showInputDialog("Input the number.");
            int c = Integer.parseInt(input);
            list[i] = c;
        }

        System.out.println("Before");
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
        partition(list, 0, list.length - 1);


        System.out.println("\nAfter partitionaing");
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
        quickSort(list, 0, list.length - 1);

        System.out.println("\nAfter Sorting");
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
    }
}

private static int partition(int[] list, int first, int last) {
    int pivot = list[first];
    int low = first + 1;
    int high = last;

    while (high > low) {

        while (low < high && list[low] < pivot) {
            low++;
        }


        while (low < high && list[high] >= pivot) {
            high--;
        }


        if (high > low) {
            int temp = list[high];
            list[high] = list[low];
            list[low] = temp;
        }
    }
    while (high > first && list[high] >= pivot) {
        high--;
    }

    if (pivot > list[high]) {
        list[first] = list[high];
        list[high] = pivot;
        return high;
    } else {
        return first;
    }

}

private static void quickSort(int[] list, int first, int last) {
    if (last > first) {
        int pivotIndex = partition(list, first, last);
        quickSort(list, first, pivotIndex - 1);
        quickSort(list, pivotIndex + 1, last);
    }
}
}
4

3 に答える 3

8

javaからRandomクラスを使用できます。

Random rand = new Random();
int num = begin_sub_array + rand.nextInt(end_sub_array - begin_sub_array);

これにより、サブ配列の先頭（begin_sub_array）からサブ配列の末尾（end_sub_array）までの値が生成されます。変数を取得numし、クイックソートアルゴリズムのピボットとして渡す必要があります。

int pivot = list[num];
于 2012-11-24T17:49:02.360 に答える
4

int rand = (int) (st + (Math.random()*((end-st)+1))); 以下のコード を使用してください

private E[] tofind;
private int sameCounter=0;
private int comparisions;
public void quickSort()
{
    quickInnerSort(0, tofind.length-1);
    System.out.println("jatin");
}
    /**
 * 
 * @param st index of the starting point of the array
 * @param end index of the ending point of the array
 * @param k rank of the element to be found out
 */
private void quickInnerSort(int st, int end)
{
    if(st>end)   
        return;

    //printWithComparisions();
    int cut = partition(st,end);        
    //check k lies in which partition

    quickInnerSort(st,cut-1);
    quickInnerSort(cut+1,end);


}

/**
 * 
 * @param st index of the array from where to partition
 * @param end index of the array till where to partition
 * @return index of the random number chosen to calculate
 */
private int partition(int st, int end)
{

    int rand = (int) (st + (Math.random()*((end-st)+1)));
    //System.out.println("rand ="+tofind[rand]+" index at "+rand);
    E x = tofind[rand];
    sameCounter=0;
    swap(end,rand);
    E x = tofind[end];
    int i = st-1;
    for(int j=st;j<=end-1;j++)
    {
        if(tofind[j].compareTo(x)==0)
            sameCounter++;
        if(tofind[j].compareTo(x)<0)
        {
            i = i+1;
            swap(i,j);
        }

    }
    swap(i+1,end);        
    return i+1;
}
于 2012-11-24T18:12:02.170 に答える
1

このようなことを試してください：-

  int pivot = arr[left + rnd.nextInt(right - left)]; //rnd is a class Random object, which you could set as a private static final field.

  import java.util.Random;


  public class QuickSort {

/**
 * @param args
 */
public static void main(String[] args) {

      int i;
      int array[] = {10,9,1,2,3,4,100,200,300,400};  
      System.out.println(" Quick Sort\n\n");
      System.out.println("Values Before the sort:\n");
      for(i = 0; i < array.length; i++)
      System.out.print( array[i]+"  ");
      System.out.println();
      quickSort(array,0,array.length-1);
      System.out.print("Values after the sort:\n");
      for(i = 0; i <array.length; i++)
      System.out.print(array[i]+"  ");
      System.out.println(); 

}

public static int partition(int arr[], int left, int right)
{
      int i = left, j = right;
      int tmp;



      int pivot = arr[left + rnd.nextInt(right - left)];

      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      return i;
}

public static void quickSort(int arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
}

 }
于 2012-11-24T17:53:06.183 に答える