2019.09.06
クイックソート
はじめに
クイックソートは最も高速であるといわれているソート法です。
この方法は、並び替える値の中から基準の値を決め、その基準値より小さい値を集めたグループ、大きい値を集めたグループを作成していき、さらに、各グループの中の値から基準値を決めて同様の方法でグループを分割していきます。分割の結果、グループ内の値が一つになったとき、その値が確定されます。
クイックソートの考え方
それでは、具体的な値でクイックソートの動きをみていきましょう。
以下は、並び替える前のデータです。
この中から基準値を決めます。
ここでは、配列に格納されているほぼ中心の値を基準値とします。
この操作を、前方からの検索位置sが後方からの検索位置eと同じになるか、超えるまで行います。これを満たす条件は、s>=e。
検索位置s=6、検索位置e=5となり、s>=e条件を満たしました。この時点で、配列の中の基準値12の前方に格納されている数字は12以下、後方に格納されている数字は12以上であることが確認できます。
次に検索位置s=6、検索位置e=5でグループを分割します。ここでの分割は、２つの新しい配列を作成するのではなく、ここまでの処理を添え字0～5、添え字6～9の２つの範囲で行うことを意味しています。（下図）
この処理では、１つのグループの値の並びで、基準値の前方の値が全て基準値未満で、後方の値が基準値より大きい場合、検索位置sと検索位置eが同じ状態で処理を終了します。この場合、検索位置sに１を足してグループを分割します。
最後にグループ内の値の数が２個以下になった場合について説明します。
グループ内の値の数が１個の場合は、その値で確定です。グループ内の値の数が２個の場合は、その２つの値を比較して、前方の値が後方の値より大きければ値を入れ替えて値を確定します。２個の場合は基準値は使いません。
以上が、クイックソートの考えかたです。
Javaソースコード
QuickSort.java
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099
public class QuickSort { // クイックソート（再帰用） static void quick_sort( int[] a, int start, int end ) { int pivot; // 基準の値 int w; // 値の交換用 int s, e; // 添え字の位置 // 配列の添え字startがend以下であれば、処理しない if ( start >= end ) return; // 配列の添え字startとendの差が1の同じ場合（隣どうし） if ( 1 == ( end - start ) ) { if ( a[ start ] > a[ end ] ) { // 値の入れ替え w = a[ start ]; a[ start ] = a[ end ]; a[ end ] = w; } return; } // 基準値を代入 pivot = a[ ( start + end ) / 2 ]; // 基準値で値の並び替え s = start - 1; e = end + 1; for ( ; ; ) { // sをインクリメントし、pivot以上の値を探す for ( ; ; ) { ++ s; if ( a[ s ] >= pivot ) break; } // eをデクリメントし、pivot以下の値を探す for ( ; ; ) { -- e; if ( a[ e ] <= pivot ) break; } // sがe以上であれば終了 if ( s >= e ) break; // 値の入れ替え w = a[ s ]; a[ s ] = a[ e ]; a[ e ] = w; } // sとeが同じであればsをインクリメント if ( s == e ) ++ s; // ブロックの分割 quick_sort( a, start, e ); quick_sort( a, s, end ); } // クイックソート static void quick_sort( int[] a ) { // 配列の要素数が1以下の場合、処理をしない if ( 1 >= a.length ) return; // クイックソート実行 quick_sort( a, 0, a.length - 1 ); } // メイン public static void main( String[] args ) { // 配列aを宣言 int[] a; // 要素数10を設定 a = new int[ 10 ]; // 値を代入 a[ 0 ] = 4; a[ 1 ] = 20; a[ 2 ] = 15; a[ 3 ] = 0; a[ 4 ] = 12; a[ 5 ] = 10; a[ 6 ] = 7; a[ 7 ] = 13; a[ 8 ] = 8; a[ 9 ] = 9; // 昇順ソート quick_sort( a ); // 結果の表示 for ( int i = 0; i < a.length; ++ i ) System.out.println( a[ i ] ); } }
コンパイル ソースコードが「ANSI」の場合
C:\talavax\javasample>javac -encoding sjis QuickSort.java
コンパイル ソースコードが「UTF-8」の場合
C:\talavax\javasample>javac QuickSort.java
実行
C:\talavax\javasample>java QuickSort
QuickSortの出力結果
0 4 7 8 9 10 12 13 15 20
出力結果から、元の配列の値が昇順に並び替わっていることが確認できます。
Javaソースコードの解説
それでは、ここからソースコードを解説していきます。
001
public class QuickSort {
クラス名を、QuickSortとしています。
002 003
// クイックソート（再帰用） static void quick_sort( int[] a, int start, int end )
005 006 007
int pivot; // 基準の値 int w; // 値の交換用 int s, e; // 添え字の位置
クイックソートで使う変数を宣言しています。
009 010
// 配列の添え字startがend以下であれば、処理しない
if ( start >= end ) return;
012 013 014 015 016 017 018 019 020 021
// 配列の添え字startとendの差が1の同じ場合（隣どうし） if ( 1 == ( end - start ) ) { if ( a[ start ] > a[ end ] ) { // 値の入れ替え w = a[ start ]; a[ start ] = a[ end ]; a[ end ] = w; } return; }
ifの条件式( 1 == ( end - start ) )は、startとendが隣同士の関係であることを表し、これにより値が2個であることがわかります。
023 024
// 基準値を代入
pivot = a[ ( start + end ) / 2 ];
027 028 029
// 基準値で値の並び替え
s = start - 1;
e = end + 1;
基準値との比較位置の初期値を変数sとeに代入しています。変数sにstart-1を代入しているのは、基準値の前方の値を比較する処理が、先に変数sをインクリメントした後で配列の値を比較するようにしているためです。変数eにend+1を代入している理由も同様に、先に変数eをデクリメントしているからです。
030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050
for ( ; ; ) { // sをインクリメントし、pivot以上の値を探す for ( ; ; ) { ++ s; if ( a[ s ] >= pivot ) break; } // eをデクリメントし、pivot以下の値を探す for ( ; ; ) { -- e; if ( a[ e ] <= pivot ) break; } // sがe以上であれば終了 if ( s >= e ) break; // 値の入れ替え w = a[ s ]; a[ s ] = a[ e ]; a[ e ] = w; }
そのループの中で、a[s]>=pivotになるsと、a[e]<=pibotになるeを求めています。
sがe未満のときは、a[s]とa[e]の値を入れ替えます。
052 053
// sとeが同じであればsをインクリメント
if ( s == e ) ++ s;
055 056 057
// ブロックの分割
quick_sort( a, start, e );
quick_sort( a, s, end );
範囲を２つに分けて処理を行います。その範囲はstart～eとs～endの２つで、quick_sortメソッドにそれらの範囲を渡し再帰的に処理をしていきます。
061 062 063 064 065 066 067 068 069
// クイックソート static void quick_sort( int[] a ) { // 配列の要素数が1以下の場合、処理をしない if ( 1 >= a.length ) return; // クイックソート実行 quick_sort( a, 0, a.length - 1 ); }
与えられたint型の配列aの個数が1個以下であれば処理をせずメソッドをreturn文で抜けます。2個以上の場合、処理範囲を引数として渡せる再帰処理用のquick_sortメソッドに、処理範囲0～a.length-1を渡してソートを実行します。
以上です。
関連コンテンツ
広告
