クイックソートの実装：ランダムピボットを使用するとほとんどソートされます

Question

私はクイックソルトを少しの練習として実装しています。現在のところ、これは単純な整数配列の単なる実装です。これが正常に機能した後、私はそれを一般的にする予定です。

以下に記載している内容には、それでも私が追跡できなかったわずかな不具合があります。私はもともとピボットとして左インデックスを使用するように書いたが、すべてうまくいきました。しかし、いったん私はそれを書き終え、ランダムなピボットを使用するように切り替えると、物事はもう正しくはありません。私のテスト配列はほぼソートされていますが、いくつかの要素はまだ2〜3つのインデックスから離れています。ここで

はこの介して実行時に不正な動作を実証し、私のテストケースのほんの一部です：

6, 5, 1, 3, 8, 4, 7, 9, 2

1, 2, 3, 4, 5

5, 4, 3, 2, 1

/** 
* Sort an integer array using quicksort 
* 
* @param a Array to sort 
*/ 
public static void quicksort(int[] a) { 
    partition(0, a.length - 1, a); 
} 

/** 
* Partition a section of an integer array around a randomly selected pivot within that section 
* 
* @param left Lower-bound index of section (inclusive) 
* @param right Upper-bound index of section (inclusive) 
* @param a Array to perform partitioning within 
*/ 
private static void partition(int left, int right, int[] a) { 
    // Exit if partition is only a single element 
    if (right - left < 1) { return; } 

    // Select a pivot at random 
    int pivot = ThreadLocalRandom.current().nextInt(left, right + 1); 

    // Move pivot to left-most position (get out of the way) 
    swap(left, pivot, a); 

    // Perform partitioning 
    int cur = left + 1; 
    for (int i = left + 1; i <= right; i++) { 
     if (a[i] < a[pivot]) { 
      swap(i, cur, a); 
      cur++; 
     } 
    } 

    // Put pivot back where it belongs 
    swap(left, cur - 1, a); 

    // Partition the two new partitions 
    partition(left, cur - 2, a); 
    partition(cur, right, a); 
} 

/** 
* Swaps two elements in an array of integers 
* 
* @param i Index of first element to swap 
* @param j Index of second element to swap 
* @param a Integer array to perform swap on 
*/ 
private static void swap(int i, int j, int[] a) { 
    int temp = a[i]; 
    a[i] = a[j]; 
    a[j] = temp; 
} 

Answer 1

答えに私のコメントを変換：しかし、あなたが持っていない

// Select a pivot at random 
int pivot = ThreadLocalRandom.current().nextInt(left, right + 1); 

// Move pivot to left-most position (get out of the way) 
swap(left, pivot, a); 

：あなたは左端の要素をピボット要素を交換している、コードのこの部分で

ピボット要素のインデックスを実際に変更しました。私は新しいjava.util.Randomの（ - 左右+ 1）を実行したとき

for (int i = left + 1; i <= right; i++) { 
    if (a[i] < a[pivot]) { 
     swap(i, cur, a); 
     cur++; 
    } 
} 

Answer 2

[OK]を、左使用して代わりにしてみてくださいピボット。リストの種類を逆にします。

if (a[i] > a[left]) { 
      swap(i, cur, a); 
      cur++; 
} 

あなたは変更を考慮しませんでした。

私は、ピボットを右側にするのに慣れています。あなたの実装を小さくしました。私の問題は、最初の権利が左になければならず、パーティションのクイックソート（左、cur-1、a）が必要である可能性が高いということでした。

スワップ位置も既にソートされているはずです。しかし、これは正しい方法に基づいています。

partition(left, cur -1 , a); 
partition(cur + 1, right, a); 

あなたは私のコードが地面にコーディングで動作Wikipedia

で実装上に読むことができます。

public class HelloWorld{ 

    int[] a = null; 



    /** 
* Sort an integer array using quicksort 
* 
* @param a Array to sort 
*/ 
public void quicksort() { 
    partition(0, a.length - 1, a); 
} 

/** 
* Partition a section of an integer array around a randomly selected pivot within that section 
* 
* @param left Lower-bound index of section (inclusive) 
* @param right Upper-bound index of section (inclusive) 
* @param a Array to perform partitioning within 
*/ 
private void partition(int left, int right, int[] a) { 
    // Exit if partition is only a single element 
    if (right <= left || right - left == 0) { return; } 

    // Select a pivot at random 
    int pivot = left + new java.util.Random().nextInt(right - left); 
    pivot = right; 

    // Move pivot to left-most position (get out of the way) 
    swap(right, pivot, a); 

    // Perform partitioning 
    int cur = left; 
    for (int i = left; i < right; i++) { 
     if (a[i] <= a[right]) { 
      swap(i, cur, a); 
      cur++; 
     } 
    } 

    // Put pivot back where it belongs 
    swap(cur, right , a); 

    // Partition the two new partitions 
    partition(left, cur -1 , a); 
    partition(cur + 1, right, a); 
} 

/** 
* Swaps two elements in an array of integers 
* 
* @param i Index of first element to swap 
* @param j Index of second element to swap 
* @param a Integer array to perform swap on 
*/ 
private void swap(int i, int j, int[] a) { 
    int temp = a[i]; 
    a[i] = a[j]; 
    a[j] = temp; 
} 


    public static void main(String []args){ 
     int[] arr = new int[]{0,4,2,3,9,11,20,100,50,32,45,27,13,2,1,4,99,1,4}; 
     HelloWorld hw = new HelloWorld(); 
     hw.a = arr; 
     hw.quicksort(); 
     for(int i = 0;i< arr.length;i++){ 
      System.out.println(arr[i]); 
     } 
    } 
} 

ここには左にピボットが付いたコードがあります。

public class HelloWorld{ 

    int[] a = null; 



    /** 
* Sort an integer array using quicksort 
* 
* @param a Array to sort 
*/ 
public void quicksort() { 
    partition(0, a.length - 1, a); 
} 

/** 
* Partition a section of an integer array around a randomly selected pivot within that section 
* 
* @param left Lower-bound index of section (inclusive) 
* @param right Upper-bound index of section (inclusive) 
* @param a Array to perform partitioning within 
*/ 
private void partition(int left, int right, int[] a) { 
    // Exit if partition is only a single element 
    if (right <= left || right - left == 0) { return; } 

    // Select a pivot at random 
    int pivot = left + new java.util.Random().nextInt(right - left); 


    // Move pivot to left-most position (get out of the way) 
    swap(left, pivot, a); 

    // Perform partitioning 
    int cur = left + 1; 
    for (int i = left +1 ; i <= right; i++) { 
     if (a[i] < a[left]) { 
      swap(i, cur, a); 
      cur++; 
     } 
    } 


    // Put pivot back where it belongs 
    swap(cur - 1 , left , a); 

    // Partition the two new partitions 
    partition(left, cur - 2 , a); 
    partition(cur , right, a); 
} 

/** 
* Swaps two elements in an array of integers 
* 
* @param i Index of first element to swap 
* @param j Index of second element to swap 
* @param a Integer array to perform swap on 
*/ 
private void swap(int i, int j, int[] a) { 
    int temp = a[i]; 
    a[i] = a[j]; 
    a[j] = temp; 
} 


    public static void main(String []args){ 
     int[] arr = new int[]{6, 5, 1, 3, 8, 4, 7, 9, 2}; 
     HelloWorld hw = new HelloWorld(); 
     hw.a = arr; 
     hw.quicksort(); 
     for(int i = 0;i< arr.length;i++){ 
      System.out.println(arr[i]); 
     } 
    } 
}