アルゴリズム｜クイックソート

補助クラスのソート

import java.util.Arrays;
import java.util.Random;

public class SortHelper {

    //     arr
    public static void printArray(int[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    //        -->           ，         
    public static void exchange(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    //        0-bound，    n     
    public static int[] getRandomArray(int n, int bound) {
        Random random = new Random();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = random.nextInt(bound);
        }
        return arr;
    }
    
    //         
    public static boolean isOrdered(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) return false;
        }
        return true;
    }

}

1.考え方
配列arr[q]によって配列arr[p...r]が2つのサブ配列arr[p...(q-1)]、arr[(q+1)...r]に分割され、前のサブ配列はすべての要素<=arr[q]、後のサブ配列はすべての要素>=arr[q]に分割される.同様にサブ配列を再帰的に分割し,最後の配列arrを並べ替えた.この過程において、下付きq、すなわち、分割分子配列(partition)の計算は、高速並べ替えの最も重要な部分である.
①区分
1つのx=arr[r]を主元(pivot element)として選択して分子配列を分割し、pから配列を遍歴し、<=xの配列要素はiと下付きの配列要素と交換され、iはp-1から記録され、jはpから記録される.
2.時間の複雑さO(n•lgn)
3.コード

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

//   
public static void quickSort(int[] arr, int p, int r) {
    if (p >= r) return;
    int q = partition(arr, p, r);
    quickSort(arr, p, q - 1);
    quickSort(arr, q + 1, r);
}

//      ，    q
public static int partition(int[] arr, int p, int r) {
    int x = arr[r];
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (arr[j] <= x) {
            SortHelper.exchange(arr, ++i, j);
        }
    }
    SortHelper.exchange(arr, i + 1, r);
    return i + 1;
}

4.考える
①arr[p]を主元として、どのように区分しますか?

//     
public static int partition(int[] arr, int p, int r) {
    int x = arr[p];
    int i = r + 1;
    for (int j = r; j > p; j--) {
        if (arr[j] > x) {
            SortHelper.exchange(arr, --i, j);
        }
    }
    SortHelper.exchange(arr, --i, p);
    return i;
}

//     
public static int partition(int[] arr, int p, int r) {
    int x = arr[p];
    int i = p;
    // p   ，     r
    for (int j = p + 1; j <= r; j++) {
        if (arr[j] <= x) {
            SortHelper.exchange(arr, j, ++i);
        }
    }
    SortHelper.exchange(arr, i, p);
    return i;
}

②partitionの配列arr={2,8,7,1,3,5,6,4}での動作手順を説明します.
[初期]
i
p, j
r(メタx)
2
8
7
1
3
5
6
4
[分割]
p, i
j
r(メタx)
2
8
7
1
3
5
6
4
p, i
j
r(メタx)
2
8
7
1
3
5
6
4
p, i
j
r(メタx)
2
8
7
1
3
5
6
4
p
i
j
r(メタx)
2
1
7
8
3
5
6
4
p
i
j
r(メタx)
2
1
3
8
7
5
6
4
p
i
j
r(メタx)
2
1
3
8
7
5
6
4
p
i + 1
j
r
2
1
3
4
7
5
6
8
5.性能O(n•lgn)は、最良の場合に並ぶ時間の複雑さにすぎない.配列が本来秩序化されている場合、速い配列を使用する時間の複雑さはO(n²)に達する.あるいは、分割のたびに選択されたメタは、配列を1つのサブ配列に分割するしかなく、分割のたびに複雑度はO(n-1)であり、最終的には時間複雑度もO(n²)レベルである.
高速配列アルゴリズムにランダム性(ランダム分割)を導入することによって,アルゴリズムがすべての入力に対して良好な所望性能を得ることができる.

import java.util.Random;

public static void randomQuickSort(int[] arr) {
    randomQuickSort(arr, 0, arr.length - 1);
}

public static void randomQuickSort(int[] arr, int p, int r) {
    if (p >= r) return;
    int q = randomPartition(arr, p, r);
    randomQuickSort(arr, p, q - 1);
    randomQuickSort(arr, q + 1, r);
}

public static int randomPartition(int[] arr, int p, int r) {
    // arr[r]   
    int i = getRandom(p, r);
    SortHelper.exchange(arr, r, i);
    return partition(arr, p, r);
}

//     p r    
public static int getRandom(int p, int r) {
    Random random = new Random();
    int i = random.nextInt(r - p + 1);
    return p + i;
}

public static int partition(int[] arr, int p, int r) {
    int x = arr[p];
    int i = p;
    for (int j = p + 1; j <= r; j++) {
        if (arr[j] <= x) {
            SortHelper.exchange(arr, j, ++i);
        }
    }
    SortHelper.exchange(arr, i, p);
    return i;
}