ゆるゆるプログラミング

・クイックソート

クイックソートは最も高速であるといわれているソート法です。

この方法は、並び替える値の中から基準の値を決め、その基準値より小さい値を集めたグループ、大きい値を集めたグループを作成していき、さらに、各グループの中の値から基準値を決めて同様の方法でグループを分割していきます。分割の結果、グループ内の値が一つになったとき、その値が確定されます。

それでは、具体的な値でクイックソートの動きをみていきましょう。

以下は、並び替える前のデータです。

クイックソート 元データ

この中から基準値を決めます。ここでは、配列に格納されているほぼ中心の値を基準値とします。

クイックソート 基準値

データ数が10なので、配列添え字は0~9です。ここでは、添え字最大値9を2で割った整数部の4(左から5番目)に格納されている値12を基準値としています。

次に、配列の先頭(添え字:0)から後方に向けて基準値以上の値を探します。その後、配列の最後(添え字:9)から前方に向けて基準値以下の値を探します。

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

この例では、配列の2番目(添え字:1)の値20が基準値12以上、配列の10番目(添え字:9)の値9が基準値12以下の値が見つかりました。この処理で値が見つかった場合、その2つの値を入れ替えます。

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

この操作を、前方からの検索位置sが後方からの検索位置eと同じになるか、超えるまで行います。これを満たす条件は、s>=e

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

検索位置s=6、検索位置e=5となり、s>=e条件を満たしました。この時点で、配列の中の基準値12の前方に格納されている数字は12以下、後方に格納されている数字は12以上であることが確認できます。

次に検索位置s=6、検索位置e=5でグループを分割します。ここでの分割は、2つの新しい配列を作成するのではなく、ここまでの処理を添え字0~5、添え字6~9の2つの範囲で行うことを意味しています。(下図)

このように分割処理を繰り返していき、グループの値の数が1つになればその値を確定します。また、グループの値の数が2つの場合、2つの値の大小を比較して小さいほうから並べて値を確定します。

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

この処理では、1つのグループの値の並びで、基準値の前方の値が全て基準値未満で、後方の値が基準値より大きい場合、検索位置sと検索位置eが同じ状態で処理を終了します。この場合、検索位置sに1を足してグループを分割します。

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

最後にグループ内の値の数が2個以下になった場合について説明します。

グループ内の値の数が1個の場合は、その値で確定です。グループ内の値の数が2個の場合は、その2つの値を比較して、前方の値が後方の値より大きければ値を入れ替えて値を確定します。2個の場合は基準値は使いません。

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

以上が、クイックソートの考えかたです。

以下は、クイックソートJavaソースコード例です。

QuickSort.java ← クリックしてダウンロードページに移動
001:    public class QuickSort {
002:    	// クイックソート(再帰用)
003:    	static void quick_sort( int[] a, int start, int end )
004:    	{
005:    		int pivot;	// 基準の値
006:    		int w;		// 値の交換用
007:    		int s, e;	// 添え字の位置
008:    	
009:    		// 配列の添え字startがend以下であれば、処理しない
010:    		if ( start >= end ) return;
011:    
012:    		// 配列の添え字startとendの差が1の同じ場合(隣どうし)
013:    		if ( 1 == ( end - start ) ) {
014:    			if ( a[ start ] > a[ end ] ) {
015:    				// 値の入れ替え
016:    				w = a[ start ];
017:    				a[ start ] = a[ end ];
018:    				a[ end ] = w;
019:    			}
020:    			return;
021:    		}
022:    
023:    		// 基準値を代入
024:    		pivot = a[ ( start + end ) / 2  ];
025:    
026:    
027:    		// 基準値で値の並び替え
028:    		s = start - 1;
029:    		e = end + 1;
030:    		for ( ; ; ) {
031:    			// sをインクリメントし、pivot以上の値を探す
032:    			for ( ; ; ) {
033:    				++ s;
034:    				if ( a[ s ] >= pivot ) break;
035:    			}
036:    
037:    			// eをデクリメントし、pivot以下の値を探す
038:    			for ( ; ; ) {
039:    				-- e;
040:    				if ( a[ e ] <= pivot ) break;
041:    			}
042:    
043:    			// sがe以上であれば終了
044:    			if ( s >= e ) break;
045:    
046:    			// 値の入れ替え
047:    			w = a[ s ];
048:    			a[ s ] = a[ e ];
049:    			a[ e ] = w;
050:    		}
051:    
052:    		// sとeが同じであればsをインクリメント
053:    		if ( s == e ) ++ s;
054:    
055:    		// ブロックの分割
056:    		quick_sort( a, start, e );
057:    		quick_sort( a, s, end );
058:    	}
059:    
060:    
061:    	// クイックソート
062:    	static void quick_sort( int[] a )
063:    	{
064:    		// 配列の要素数が1以下の場合、処理をしない
065:    		if ( 1 >= a.length ) return;
066:    
067:    		// クイックソート実行
068:    		quick_sort( a, 0, a.length - 1 );
069:    	}
070:    
071:    
072:    	// メイン
073:    	public static void main( String[] args ) {
074:    		// 配列aを宣言
075:    		int[] a;
076:    
077:    		// 要素数10を設定
078:    		a = new int[ 10 ];
079:    
080:    		// 値を代入
081:    		a[ 0 ] =  4;
082:    		a[ 1 ] = 20;
083:    		a[ 2 ] = 15;
084:    		a[ 3 ] =  0;
085:    		a[ 4 ] = 12;
086:    		a[ 5 ] = 10;
087:    		a[ 6 ] =  7;
088:    		a[ 7 ] = 13;
089:    		a[ 8 ] =  8;
090:    		a[ 9 ] =  9;
091:    
092:    		// 昇順ソート
093:    		quick_sort( a );
094:    
095:    		// 結果の表示
096:    		for ( int i = 0; i < a.length; ++ i )
097:    			System.out.println( a[ i ] );
098:    	}
099:    }

QuickSortの出力結果

0
4
7
8
9
10
12
13
15
20

出力結果から、元の配列の値が昇順に並び替わっていることが確認できます。

それでは、ここからソースコードを解説していきます。

001:    public class QuickSort {

クラス名を、QuickSortとしています。

002:    	// クイックソート(再帰用)
003:    	static void quick_sort( int[] a, int start, int end )

クイックソート行うquick_sortメソッドです。int型配列aとint型変数startとendに処理する範囲の添え字を指定してソートを実行します。

005:    		int pivot;	// 基準の値
006:    		int w;		// 値の交換用
007:    		int s, e;	// 添え字の位置

クイックソートで使う変数を宣言しています。

009:    		// 配列の添え字startがend以下であれば、処理しない
010:    		if ( start >= end ) return;

変数startの値がendの値以上であればreturn文でメソッドを抜けます。

012:    		// 配列の添え字startとendの差が1の同じ場合(隣どうし)
013:    		if ( 1 == ( end - start ) ) {
014:    			if ( a[ start ] > a[ end ] ) {
015:    				// 値の入れ替え
016:    				w = a[ start ];
017:    				a[ start ] = a[ end ];
018:    				a[ end ] = w;
019:    			}
020:    			return;
021:    		}

処理範囲の値の数が2個の場合、単純な値の比較による値の入れ替え処理を行い、return文でメソッドを抜けます。

ifの条件式( 1 == ( end - start ) )は、startとendが隣同士の関係であることを表し、これにより値が2個であることがわかります。

023:    		// 基準値を代入
024:    		pivot = a[ ( start + end ) / 2  ];

変数startとendを足して2で割った位置の配列の値を基準値を格納する変数pivotに代入しています。

027:    		// 基準値で値の並び替え
028:    		s = start - 1;
029:    		e = end + 1;

基準値との比較位置の初期値を変数sとeに代入しています。変数sにstart-1を代入しているのは、基準値の前方の値を比較する処理が、先に変数sをインクリメントした後で配列の値を比較するようにしているためです。変数eにend+1を代入している理由も同様に、先に変数eをデクリメントしているからです。

030:    		for ( ; ; ) {
031:    			// sをインクリメントし、pivot以上の値を探す
032:    			for ( ; ; ) {
033:    				++ s;
034:    				if ( a[ s ] >= pivot ) break;
035:    			}
036:    
037:    			// eをデクリメントし、pivot以下の値を探す
038:    			for ( ; ; ) {
039:    				-- e;
040:    				if ( a[ e ] <= pivot ) break;
041:    			}
042:    
043:    			// sがe以上であれば終了
044:    			if ( s >= e ) break;
045:    
046:    			// 値の入れ替え
047:    			w = a[ s ];
048:    			a[ s ] = a[ e ];
049:    			a[ e ] = w;
050:    		}

for文無限ループ作成しています。

そのループの中で、a[s]>=pivotになるsと、a[e]<=pibotになるeを求めています。

sとeを求めた結果、sがe以上になったときにbreak文ループを終了するようにしています。

sがe未満のときは、a[s]とa[e]の値を入れ替えます。

052:    		// sとeが同じであればsをインクリメント
053:    		if ( s == e ) ++ s;

for文を抜けたときのsとeが同じとき、sをインクリメントします。

055:    		// ブロックの分割
056:    		quick_sort( a, start, e );
057:    		quick_sort( a, s, end );

範囲を2つに分けて処理を行います。その範囲はstart~eとs~endの2つで、quick_sortメソッドにそれらの範囲を渡し再帰的に処理をしていきます。

061:    	// クイックソート
062:    	static void quick_sort( int[] a )
063:    	{
064:    		// 配列の要素数が1以下の場合、処理をしない
065:    		if ( 1 >= a.length ) return;
066:    
067:    		// クイックソート実行
068:    		quick_sort( a, 0, a.length - 1 );
069:    	}

処理範囲を引数として渡さないクイックソートメソッドです。

与えられたint型配列aの個数が1個以下であれば処理をせずメソッドをreturn文で抜けます。2個以上の場合、処理範囲を引数として渡せる再帰処理用のquick_sortメソッドに、処理範囲0~a.length-1を渡してソートを実行します。

■関連コンテンツ

配列のソート 配列を昇順・降順に並び替える方法を解説
配列 同じ型の変数をまとめた配列について解説
for文 繰り返し処理に使用するfor文について解説
変数値の交換 2つの変数値を交換する方法を解説

■新着情報

2020.05.07 サイコロの出目確率 サイコロの目のでる確率は?
2020.04.22 現在日時をミリ秒で取得 現在日時をミリ秒数で取得
2020.04.22 日時 日時の操作について
2020.04.22 時間の単位変換 1日、1時間は何ミリ秒?

■広告

法人向けのETC専用カード

~約8,000名の受講生と80社以上の導入実績~ 企業向けプログラミング研修ならCodeCamp

日本最大級ショッピングサイト!お買い物なら楽天市場

 

 

 

 

 

 

 

 

 

Topへ