6

Javaでクイックソートを実装する際に問題が発生しました。このプログラムを実行すると、stackoverflowエラーが発生しますが、その理由はよくわかりません。誰かがエラーを指摘できれば、それは素晴らしいことです。

siは開始インデックスです。eiは終了インデックスです。

public static void qsort(int[] a, int si, int ei){

    //base case
    if(ei<=si || si>=ei){}


    else{ 
        int pivot = a[si]; 
        int length = ei - si + 1; 
        int i = si+1; int tmp; 

        //partition array 
        for(int j = si+1; j<length; j++){
            if(pivot > a[j]){
                tmp = a[j]; 
                a[j] = a[i]; 
                a[i] = tmp; 

                i++; 
            }
        }

        //put pivot in right position
        a[si] = a[i-1]; 
        a[i-1] = pivot; 

        //call qsort on right and left sides of pivot
        qsort(a, 0, i-2); 
        qsort(a, i, a.length-1); 
    }
}
4

10 に答える 10

7

まず、Keithが提案したように、qsort再帰呼び出しの境界を修正する必要があります。そうしないと、配列全体が常に何度もソートされるためです。パーティションループを調整する必要があります。jは、サブ配列の最初から最後（最後の要素を含む）までのインデックスです。したがって、si + 1からei（eiを含む）にループする必要があります。

つまり、これは修正されたコードです。いくつかのテストケースを実行しましたが、問題なくソートされているようです。

    public static void qsort(int[] a, int si, int ei){
    //base case
    if(ei<=si || si>=ei){}

    else{ 
        int pivot = a[si]; 
        int i = si+1; int tmp; 

        //partition array 
        for(int j = si+1; j<= ei; j++){
            if(pivot > a[j]){
                tmp = a[j]; 
                a[j] = a[i]; 
                a[i] = tmp; 

                i++; 
            }
        }

        //put pivot in right position
        a[si] = a[i-1]; 
        a[i-1] = pivot; 

        //call qsort on right and left sides of pivot
        qsort(a, si, i-2); 
        qsort(a, i, ei); 
    }
}
于 2013-02-16T15:21:14.097 に答える
1 
int partition(int array[], int too_big_index, int too_small_index)
{
     int x = array[too_big_index];
     int i = too_big_index;
     int j = too_small_index;
     int temp;
     do
     {                 
         while (x <array[j])
        {
              j --;
        } 
         while (x >array[i])
         {
              i++;
         } 
          if (i < j)
         { 
                 temp = array[i];    
                 array[i] = array[j];
                 array[j] = temp;
         }
     }while (i < j);     
     return j;           // middle  
}

void QuickSort(int num[], int too_big_index, int too_small_index)
{
      // too_big_index =  beginning of array
      // too_small_index = end of array

     int middle;
     if (too_big_index < too_small_index)
    {
          middle = partition(num, too_big_index, too_small_index);
          QuickSort(num, too_big_index, middle);   // sort first section
          QuickSort(num, middle+1, too_small_index);    // sort second section
     }
     return;
}



void main()
{
    int arr[]={8,7,13,2,5,19,1,40,12,34};

    QuickSort(arr,0,9);
    for(int i=0;i<10;i++)
         System.out.println(arr[i]);
}
于 2016-10-21T17:17:12.833 に答える
0

手に無制限の再帰バグがある可能性があります。クイックスキャンからはわかりませんが...

そうしない場合でも、この実装では多くのスタックを使用することになります。スタックオーバーフローを引き起こすのに十分です。すでにソートされている100万個のアイテムで呼び出すとどうなりますか？それらを1つと999,999のアイテムに分割してから、繰り返します。したがって、これを機能させるには100万のスタックフレームが必要です。

これを解決する方法はたくさんあります。たとえば、2つの範囲の小さい方で繰り返し、大きい方で反復する、スタックを自分でヒープデータ構造に実装するなどです。ただし、それよりもさらに優れた方法を実行することをお勧めします。 、深いスタックは、O（n lg n）ソート境界を超えて吹いていることも意味します。

psバグはここにあります：

qsort(a, 0, i-2); 
qsort(a, i, a.length-1);

する必要があります

qsort(a, si, i-2);
qsort(a, i, ei);
于 2013-02-16T05:51:53.373 に答える
0

あなたはこれを試すことができます：

public void sort(int[] A) {
        if (A == null || A.length == 0)
            return;
        quicksort(A, 0, A.length - 1);
    }

    public void quicksort(int[] A, int left, int right) {
        int pivot = A[left + (right - left) / 2];
        int i = left;
        int j = right;
        while (i <= j) {
            while (A[i] < pivot) {
                i++;
            }
            while (A[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchange(i, j);
                i++;
                j--;
            }
        }

        if(left < j)
            quicksort(A,left,j);
        if(i < right)
            quicksort(A,i,right);
    }

    public void exchange(int i, int j){
        int temp=A[i];
        A[i]=A[j];
        A[j]=temp;
    }

    public String toString() {
        String s = "";
        s += "[" + A[0];
        for (int i = 1; i < A.length; i++) {
            s += ", " + A[i];
        }
        s += "]";
        return s;
    }

ソース：コード2学習：クイックソートアルゴリズムチュートリアル

于 2013-02-18T12:36:18.917 に答える
0 
import java.util.Arrays;


public class QuickSort {


    public static int pivot(int[] a, int lo, int hi){
        int mid = (lo+hi)/2;
        int pivot = a[lo] + a[hi] + a[mid] - Math.min(Math.min(a[lo], a[hi]), a[mid]) - Math.max(Math.max(a[lo], a[hi]), a[mid]);

        if(pivot == a[lo])
            return lo;
        else if(pivot == a[hi])
            return hi;
        return mid;
    }

    public static int partition(int[] a, int lo, int hi){

        int k = pivot(a, lo, hi);
        //System.out.println(k);
        swap(a, lo, k);
        //System.out.println(a);
        int j = hi + 1;
        int i = lo;
        while(true){

            while(a[lo] < a[--j])
                if(j==lo)   break;

            while(a[++i] < a[lo])
                if(i==hi) break;

            if(i >= j)  break;
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }

    public static void sort(int[] a, int lo, int hi){
        if(hi<=lo)  return;
        int p = partition(a, lo, hi);
        sort(a, lo, p-1);
        sort(a, p+1, hi);
    }

    public static void swap(int[] a, int b, int c){
        int swap = a[b];
        a[b] = a[c];
        a[c] = swap;
    }

    public static void sort(int[] a){
        sort(a, 0, a.length - 1);
        System.out.print(Arrays.toString(a));
    }

    public static void main(String[] args) {
        int[] arr = {5,8,6,4,2,9,7,5,9,4,7,6,2,8,7,5,6};
        sort(arr);
    }
}

これを試して。それは確かに機能します。

于 2014-03-30T06:28:38.233 に答える
0

//このためのテスタークラスを実装しただけで動作します

public int [] sort（int [] A、int from、int to）{

if(from<to){
    int pivot=partition(A,from,to);
    if(pivot>1)
        sort(A,from, pivot-1);

    if(pivot+1<to)
        sort(A, pivot+1, to);


}

return array;

}

public int partition（int A []、int from、int to）{

while(from < to){
    int pivot=A[from];

    while(A[from]<pivot)
        from++;

    while(A[to]>pivot)
        to--;


    if(from<to)   
        swap(A,to,from);



}
    return to;
}

private void swap(int A[], int i, int j){
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;}
于 2014-04-13T00:20:26.247 に答える
0

これはかなり適切なはずです。この画像を使用した以下のコードは、より理にかなっています。

public void quickSort(long[] a){

  int startingIndex = 0;
  int endingIndex = a.length - 1;
  qsort(a, startingIndex, endingIndex);

}

private void qsort(long[] a, int startingIndex, int endingIndex){

  if (startingIndex < endingIndex){
    int middleIndex = partition(a, startingIndex, endingIndex);
    qsort(a, startingIndex, middleIndex-1);
    qsort(a, middleIndex+1, endingIndex);
  }

}

private int partition(long[] a, int startingIndex, int endingIndex){
  long pivot = a[endingIndex];
  int endWall = endingIndex;
  int wall = 0;

  while (wall < endWall){

    if (a[wall] < pivot){
      wall++;
    }
    else {
      a[endWall] = a[wall];
      a[wall] = a[endWall - 1];
      a[endWall - 1] = pivot;
      endWall--;
    }
  }
  return wall;
}

楽しみ！

于 2018-03-16T18:50:17.210 に答える
0 
public class MyQuickSort {

    private int array[];
    private int length;

    public void sort(int[] inputArr) {

        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.array = inputArr;
        length = inputArr.length;
        quickSort(0, length - 1);
    }

    private void quickSort(int lowerIndex, int higherIndex) {

        int i = lowerIndex;
        int j = higherIndex;
        // calculate pivot number, I am taking pivot as middle index number
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // Divide into two arrays
        while (i <= j) {
            /**
             * In each iteration, we will identify a number from left side which 
             * is greater then the pivot value, and also we will identify a number 
             * from right side which is less then the pivot value. Once the search 
             * is done, then we exchange both numbers.
             */
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }

    private void exchangeNumbers(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String a[]){

        MyQuickSort sorter = new MyQuickSort();
        int[] input = {24,2,45,20,56,75,2,56,99,53,12};
        sorter.sort(input);
        for(int i:input){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}
于 2018-07-10T00:46:36.860 に答える
0 
// the partition function
public static int Sort(int arr[], int start, int end)
{
    int pivot = arr[end];
    int pIndex = start;
    for(int i = start; i< end;i++)
    {
        if(arr[i] <= pivot)
        {
            int temp = arr[i];
            arr[i] = arr[pIndex];
            arr[pIndex] = temp;
            pIndex++;
        }
    }
    int temp = arr[pIndex];
    arr[pIndex] = pivot;
    arr[end] = temp;
    return pIndex;
}
public static void quickSort(int arr[],int start,int end)
{
    if(start>=end)
        return;
    // finding the pivot element
    int pivot = Sort(arr,start,end);
    quickSort(arr,start,pivot-1);
    quickSort(arr,pivot+1,end);
    
}
于 2021-05-14T09:31:03.997 に答える
-1

クイックソートは、たまたま正しい順序である入力にわずかに敏感です。その場合、いくつかのスワップをスキップできます。マージソートにはそのような最適化がないため、クイックソートはマージソートに比べて少し高速になります。

マージソートよりもクイックソートが優れている理由

于 2014-07-24T08:44:53.170 に答える