定式化された問題が与えられる例

(1)

プログラミング言語 I 第 5 回ソート

埼玉大学工学部電気電子システム工学科伊藤和人

アルゴリズムとは

定式化された問題が与えられる例

:

「

1

から

N

までの整数の和を求めよ」

解の求め方:変数iを1からNまで順に1つずつ増やしながら変数wに加算する

問題の解答を得るための方針や考え方を

入力データ

解答

アルゴリズムという

(

算法、

Algorithm) プログラムアルゴリズムアルゴリズムを

実現するプログラム

アルゴリズムとプログラム

問題に対して正しい解答(正答)は1つ

「

1

から

100

までの整数の和」⇒

5050

しかし、正答を得るためのアルゴリズムはさまざま

変数

i

を

1

から

100

まで順に

1

つずつ増やしながら変数wに加算するアルゴリズム1

100

*

(100+1)/2

を計算するアルゴリズム

2

明らかにアルゴリズム2の方が良さそうに思える

アルゴリズムとプログラム

正答を得るためのアルゴリズムはさまざま

アルゴリズムを実装

(implement)

するプログラムもさまざま

アルゴリズム1 アルゴリズム2 アルゴリズム3 定式化された問題

問題の正答

プログラムA プログラムB プログラムC どのプログラムも正答を与える

アルゴリズムとプログラムの良さ

プログラムの良さの評価

解を得るまでの時間(短いほど良い)

必要なメモリ量(少ないほど良い)

同じアルゴリズムを使用しても、

プログラムの書き方で、良さは異なる

ただし、コンパイラの最適化処理によって書き方の差は問題とならない場合もある

使用するアルゴリズムの違いがプログラムの良さを決定する

例えば、100,000個の素数を求める問題では、

アルゴリズムの違いによって1000倍以上の時間差

アルゴリズムの良さの測り方

細かな差異は問題としない

(

意味がない

)

使用する計算機のスピードの違い

コンパイラの最適化処理の有無

使用するプログラミング言語による違い

問題のサイズとともにどのように実行時間、

メモリ使用量が変化するか

「1からNまでの整数の和を求めよ」

「N個のデータを大きい順に並べ替えよ」

「N個の都市を順に訪問するための旅費が最小になる訪問順を求めよ」

(2)

アルゴリズムの評価

問題「

1

から

N

までの整数の和を求めよ」

変数

i

を

1

から

N

まで順に

1

つずつ増やしながら変数

w

に加算するアルゴリズム

1

N

*

(N+1)/2

を計算するアルゴリズム

2

z変数iの増加はN-1回 z加算はN回

Nに比例した実行時間が必要

z加算は1回

z乗算、除算を1回ずつ

Nの値によらず常に同じ実行時間

「オーダー」の考え方

問題サイズnのアルゴリズム実行時間がF(n)

(

f(n)

)

O “f(n)のオーダー”と読む

) ( )

( )

(n F n f n

f β

α ≤ ≤

2つの定数α, β^{が存在して}

が十分大きなnについて常に成り立つならばアルゴリズムの実行時間は

f(n)として、n、n²

、nlognなど

特殊なもの

: O(1) (n

に依存しない

) O(a²+n) (a²

とnに依存

)

「オーダー」とアルゴリズムの良さ

問題「1からNまでの整数の和を求めよ」

変数

i

を

1

から

N

まで順に

1

つずつ増やしながら変数wに加算する

アルゴリズム1

N

*

(N+1)/2

を計算する

アルゴリズム2

加算はN回 O(N)

常に一定 O(1)

オーダーが小さいほど、大きな問題に対する実行時間の増え方が小さいオーダーの小さいものが優れたアルゴリズム

アルゴリズムと「並べ替え」

なぜ「並べ替え」か

アルゴリズムの違いによって実行時間に大きな差が生じる

ごく一般的な処理であり、高速なアルゴリズムを理解しておくことは何かの役に立つこれから、並べ替えのアルゴリズムを説明

並べ替えとは

並べ替え

=

ソート

(sort)

複数個のデータを大きい順

(

降順

)

あるいは小さい順

(

昇順

)

に整列する

以降では昇順の並べ替えのみ考慮

例 inta[7]

a

0 1 2 3 4 5 6

1 2 3 5 6 8 9

昇順に並べ替え a

5 3 8 2 9 1 6

基本ソートアルゴリズム

アイデア

:

先頭に最も小さな値、残りのデータのうち最も小さな値が

2

番目、以下同様

5 3 8 2 9 1 6 1

2

5 3 8 2 9 6 1 5 3 8 9 6

2

1 3 5 8 9 6

(3)

基本ソートのプログラム

voidsort( void) {

inti, j;

for( i=0 ; i<N-1 ; i++ ) for( j=i+1 ; j<N ; j++ )

if( a[i] > a[j] ) swap( i, j );

}

voidswap( inti, intj ) {

intt = a[i]; a[i] = a[j]; a[j] = t;

}

例

要素数Nの配列aを

小さい順にソート

配列aの実際の型に合わせて変更する

C 言語によるプログラム

#defineN 7

inta[N] = {5,3,8,2,9,1,6};

voidswap(inti,intj ) { …/* 省略*/

}

voidsort( void) { …/* 省略*/

}

intmain( void) {

sort();

}

まず最初にmain関数が実行定数を定義

大域変数(配列)

sort関数の中で swap関数呼び出し

swap関数を先(上)に定義(宣言)

C言語の構文: マクロ

プログラム中で共通して使用するものをマクロとして定義すると良い

マクロに値を定義する

プログラム中でマクロ名と同じ文字列が現れると、マクロの値に置き換わる

値はなくてもよい

(

詳細は省略

)

#define

マクロ名値

書式

マクロ: 定数の定義

定数を定義する単純なマクロ

#define N100 ...int a[N];

for( i=0 ; i<N; i++ ){

a[i] = ...

}

例定数マクロの定義

最後に“;”をつけない

マクロ参照

定義内容の100に置き換わる利点 z変更する可能性のある定数と分かる

z変更する場合に1ヶ所だけ直せばよい

C 言語の構文 : 変数のスコープ

関数内で宣言した変数は、その関数の中でのみ有効

⇒関数に局所的

(local)

な変数

変数の有効範囲をスコープ(scope)という

関数内で宣言した変数のスコープは関数内

スコープが終了すると、変数値は失われる

intaccumulate( int x )

{ inti;

i += x;

returni;

}

intk;

k = accumulate( 1 );

k=1+10+5+2とはならない

大域変数 (global 変数 )

あらゆる関数の外で変数を宣言可能

大域変数という

大域変数のスコープはプログラム全体

関数の中から大域変数を参照することが可能 (値の読み出しと変更の両方可能)

利点

プログラムが終了するまで変数値は消えない

⇒プログラム全体の制御変数などに利用可能

関数から複数の結果の受け取りに利用可能

(4)

大域変数の例

#define N 7

inta[N] = {5,3,8,2,9,1,6};

voidswap(inti,intj ) {

intt = a[i]; a[i] = a[j]; a[j] = t;

}

voidsort( void) {

inti, j;

for( i=0 ; i<N-1 ; i++ ) for( j=i+1 ; j<N ; j++ )

if( a[i] > a[j] ) swap( i, j );

}

関数の外で配列aを宣言

⇒大域変数(配列)となる

大域配列aを読み書き

大域配列aを参照

変数のシャドウイング

(shadowing)

大域変数と同じ名前の局所変数を宣言した場合

変数の参照は、局所変数が優先大域変数は見えなくなる⇒シャドウイング

シャドウイングが起きたとき、大域変数は参照できない(参照する方法がない)

intv;

intfunc(intx ) {

intv;

v += x;

returnx;

}

大域変数vを宣言

関数funcの局所変数vを宣言大域変数ではなく局所変数を参照する

プログラム実行

#defineN 7

inta[N] = {5,3,8,2,9,1,6};

voidswap(inti,intj )

…/* 省略*/

voidsort( void)

…/* 省略*/

intmain( void) {

intk;

for( k=0 ; k<N ; k++ ) printf( "%d ", a[k] );

printf( "¥n" );

sort();

for( k=0 ; k<N ; k++ ) printf( "%d ", a[k] );

printf( "¥n" );

}

sort関数を実行

配列を表示

ソート結果を表示

基本ソートプログラム実行時間

2重ループの内側の実行回数

∑

∑ ∑

⁻

=

−

=

− +

=

−

= ²

0 2

0 1

1

) 1 ( 1 ^N

i N

i j

i N

2 ) 2 )(

1 ) (

1

( ² − −

−

= N N

N 2

) 1 ( −

= N N

比較実行回数

2 ) 1

( −

= N N 交換実行回数

4 ) 1

( −

= N N O(N²)

実行時間は

挿入ソートアルゴリズム

アイデア

:

部分的に整列済みのデータの適切な位置に、新たなデータを挿入する

5 3 8 4 6 2 1 3 5 8 4 6 2 1 3 5 8 4 6 2 1 3 4 5 8 6 2 1 3 4 5 6 8 2 1 部分的

整列済み

未整列

挿入ソートのプログラム

voidsort( void) {

inti, j, k;

for( i=1 ; i<N ; i++ ){

for( j=i-1 ; j>=0 ; j--) if( a[j] < a[i] ) break;

for( k=i ; k>j+1 ; k--) swap( k, k-1 );

} }

例

要素数

N

の配列

a

を

小さい順にソート

3 5 8 4 6 2 1ⁱ j

3 5 4 8 6 2 1 3 4 5 8 6 2 1

(5)

挿入ソート : 挿入位置を調べる

for( k=i ; k>j+1 ; k--) swap( k, k-1 );

1 3 5 4 j=1 i=4

このfor文に注目

3 4 5 2 ケース1

ケース2

if文の条件が成立して for文中断(このときj=1)

for文の終了条件により終了(このときj=-1) 8

8

(a[i]より小さい値あり)

(a[i]より小さい値なし)

位置iより左にあり、

a[i]より小さい値を探す

i=4

適切な位置へ挿入

for( k=i ; k>j+1 ; k--) swap( k, k-1 );

i=4

挿入処理ケース1(j=1) ケース2(j=-1)

swap( 4, 3 );

swap( 3, 2 );

3 4 5 2 i=4 8 実際に行う挿入処理

1 3 5 8 4

swap( 4, 3 );

swap( 3, 2 );

swap( 2, 1 );

swap( 1, 0 );

実際に行う挿入処理順に

実行順に

実行 k=4:

k=3: k=4:

k=3:

k=2:

k=1:

挿入ソートプログラム実行時間

比較: 2重ループの内側の最多実行回数

交換

: 2

重ループの内側の最多実行回数

2

) 1 1 ¹ (

1 1

1 1 0

= −

=

∑

∑∑

⁻

=

−

=

−

=

N i N

i i j

平均比較実行回数

4 ) 1

( −

= N N 平均交換実行回数

4 ) 1

( −

= N N

O(N²)

実行時間は

他のアルゴリズムより少ない

2 ) 1 1 ¹ (

1 1

= −

=

∑

∑∑

⁻

=

−

= =

N i N

i i k

挿入ソートの特徴

元のデータがほとんど整列していると、

比較の回数および交換回数が減少

5 3 8 2 9 1 6

5

3 2 8 9

1 6

比較

14回 11回

交換

9回 3回

初期データ1 初期データ2

少ない手数で大雑把な整列を行いその後に厳密な挿入ソートを行う

整列状態

概略挿入ソート

voidsort_1( void) {

inti, j, k;

for( i=w; i<N ; i++ ){

for( j=i-w; j>=0 ; j-=w) if( a[j] < a[i] ) break;

for( k=i ; k>j+w; k -=w) swap( k, k-w);

} } 例

挿入ソートに間隔wを導入

概略 + 厳密挿入ソート

w=3

として概略挿入ソート実行

w=1

として概略ソート、つまり厳密ソート実行

5 3 8 2 9 1 6 比較

4回 2回

交換 2 3 1 5 9 8 6

初期データ

2 3 1 5 9 8 6

比較

10回 5回

交換 1 2 3 5 6 8 9

挿入ソートを直接行う場合に比べて交換回数が低減この手法をシェルソートという

(6)

シェルソートプログラム実行時間

間隔

w

の選び方

系列

: 1, 4, 13, 40, 121, ...

⇒

w_k=3w_k-1+1

データ数Nより小さい最大のw

_k

を定め、

順次

w

の値を小さなものに入れ替えながら概略挿入ソートを繰り返し実行

ほとんど整列済みのデータに

挿入ソートを1回実行すると O(N)

wの値を変えながら挿入ソートを繰り返し

wの値に上の系列を使った場合 O(N^1.25)

シェルソートプログラム

次のw/=3とセットでwの初期値を求める wの系列を逆にたどりながら概略挿入ソートを繰り返す

voidsort( void) {

inti, j, k, w;

for( w=1 ; w<N ; w=3*w+1 );

for( w /= 3 ; w>0 ; w /= 3 ) for( i=w ; i<N ; i++ ){

for( j=i-w ; j>=0 ; j-=w ) if( a[j] < a[i] ) break;

for( k=i ; k>j+w ; k -=w ) swap( k, k-w );

} }

ソート実行時間の理論限界

データ数

n

に対して最短ソート時間の下限

バブルソート、挿入ソート:

O(n²)

シェルソート

_: O(n^1.25)

O(nlogn)

であることが知られている

理論限界に達していない

理論限界を達成するソートアルゴリズム

計算量を減らす工夫

基本的なアイデア

データ数

n

に対して

O(n²)

の処理データを

n/2

個と

n/2

個に分割し、

それぞれに対して

O((n/2)²)

^の処理

kn²

2 2

4 4

kn kn +

⎟⎟⎠

⎜⎜ ⎞

⎝

= ⎛ 2 n2

k

ソートへの応用は

?

計算量を減らすソート

基準値を選び、基準値より小さいデータと基準値より大きいデータに分けてソート

5 3 8 2 9 1 6 初期データ

5 3 8 2 9 1 6 先頭データを

基準値とする

5 3 2 1 8 9 6 基準値以下基準値より大

分割

5 1 2 3 6 8 9 それぞれソート

計算量を減らすソート ( その 2)

それぞれのソート結果を統合する

基準値以下のデータと基準値より大きいデータにうまく分割できると高速化

分割したデータをさらに分割してソート

⇒　さらに高速化

基準値以下基準値より大 5 1 2 3 6 8 9

1 2 3 5 6 8 9 ソート結果

統合

このアルゴリズムをクイックソートという

(7)

再帰的なクイックソート

小さい(lower)データと大きい(higher)データ

分割

統合それぞれソート voidquick_sort( int a[], intnum )

{

intla[N-1], ha[N-1];

inti, j, lnum=0, hnum=0;

intmid = a[0];

for( i=1 ; i<num ; i++ )

if( a[i] <= mid ) la[lnum++] = a[i];

else ha[hnum++] = a[i];

if( lnum > 0 ) quick_sort( la, lnum );

if( hnum > 0 ) quick_sort( ha, hnum );

for( i=0 ; i<lnum ; i++ ) a[i] = la[i];

a[i++] = mid;

for( j=0 ; j<hnum ; j++, i++ ) a[i] = ha[j];

クイックソートのメモリ節約

前ページのプログラムでは、

quick_sort

の呼出しごとに要素数

N-1

の配列を

2

個作成

しかし、全体では半分の要素しか必要ない

⇒ メモリの無駄

元データの配列をうまく利用する

メモリを節約するデータ分割

5 3 8 2 9 6 1 先頭データを

基準値とする

基準値以下? Yes 基準値より大?

5 3 8 2 9 6 1

No No

5 3 1 2 9 6 8 交換

5 3 1 2 9 6 8 Yesなら

右へ進む

Yesなら Yes Yes 左へ進む

5 3 1 2 9 6 8

2つの矢印がぶつかると

メモリを節約したクイックソート

voidquick_sort( int a[], intlow, int high ) {

intmid=a[low], i=low+1, j=high;

for( ; ; ){

while( i<j && a[i] <= mid ) i++;

while( a[j] > mid ) j--;

if( i>j || a[i] == a[j] ) break;

swap( i, j );

}

swap( low, j );

if( low<j-1 ) quick_sort( a, low, j-1 );

if( j+1<high) quick_sort( a, j+1, high );

}

終了条件なし

⇒無限ループ

ループを抜け出す配列の分割

メモリを節約したクイックソート

5 3 1 2 9 6 8

j i 2 3 1 5 9 6 8

10

i j

3 1 2 9 6 8 8 3 1 2 9 6 10

5 3 1 5 5 6 8

i j

次にソート次にソート

次にソート i>j の場合

a[i]==a[j] の場合(i=j。For文終了時にはi<jにならない)

a[i]==a[j] (i<j) の場合

for

文の終了条件

a[j]とmid交換

mid j

j iはさらに右へ移動(大きく)できるので、for文終了時にはi<jでない

メモリを節約したクイックソート

j i

次のソート対象 midがソート対象配列中の最小値 for文の終了時の状態

特殊な場合

:

2 3 10 4 9 6 8 2 3 10 4 9 6 8

ソート対象配列を2個の配列に分割できない

ソート済みの配列にクイックソートを適用するとアルゴリズム終了までに長い時間がかかる

(8)

クイックソートの実行時間

ソートの理論限界を達成

ランダムなデータに対して高速

ほとんど整列しているデータに適用すると実行時間は

O(n²)

に悪化

C言語ではクイックソートの関数が

予め用意されている

O(nlogn)

qsort

関数

詳細は各自調べて欲しい

まとめ

アルゴリズムとは

アルゴリズムの良さの示し方

並べ替え

(

ソート

)

のアルゴリズム

基本ソート

挿入ソート

シェルソート

クイックソート

定式化された問題が与えられる 例

プログラミング言語 I 第 5 回 ソート

アルゴリズムとは

定式化された問題が与えられる 例

「

から

までの整数の和を求めよ」

問題の解答を得るための方針や考え方を

アルゴリズムという

算法、

アルゴリズムとプログラム

問題に対して正しい解答(正答)は1つ

「

から

までの整数の和」⇒

しかし、正答を得るためのアルゴリズムは さまざま

変数

を

から

まで順に

つずつ 増やしながら変数wに加算する アルゴリズム1

*

を計算する アルゴリズム

アルゴリズムとプログラム

正答を得るためのアルゴリズムはさまざま

アルゴリズムを実装

するプロ グラムもさまざま

アルゴリズムとプログラムの良さ

プログラムの良さの評価

同じアルゴリズムを使用しても、

プログラムの書き方で、良さは異なる

使用するアルゴリズムの違いがプログラム の良さを決定する

アルゴリズムの良さの測り方

細かな差異は問題としない

意味がない

問題のサイズとともにどのように実行時間、

メモリ使用量が変化するか

アルゴリズムの評価

問題「

から

までの整数の和を求めよ」

変数

を

から

まで順に

つずつ 増やしながら変数

に加算する アルゴリズム

*

を計算する アルゴリズム

「オーダー」の考え方

問題サイズnのアルゴリズム実行時間がF(n)

(

)

、nlognなど

特殊なもの

に依存しない

とnに依存

「オーダー」とアルゴリズムの良さ

問題「1からNまでの整数の和を求めよ」

変数

を

から

まで順に

つずつ 増やしながら変数wに加算する

*

を計算する

アルゴリズムと「並べ替え」

なぜ「並べ替え」か

アルゴリズムの違いによって実行時間に 大きな差が生じる

ごく一般的な処理であり、高速なアルゴリ ズムを理解しておくことは何かの役に立つ これから、並べ替えのアルゴリズムを説明

並べ替えとは

並べ替え

ソート

複数個のデータを大きい順

降順

あるい は小さい順

昇順

に整列する

以降では昇順の並べ替えのみ考慮

基本ソートアルゴリズム

定式化された問題が与えられる例

プログラミング言語 I 第 5 回ソート

定式化された問題が与えられる例

しかし、正答を得るためのアルゴリズムはさまざま

つずつ増やしながら変数wに加算するアルゴリズム1

を計算するアルゴリズム

するプログラムもさまざま

使用するアルゴリズムの違いがプログラムの良さを決定する

つずつ増やしながら変数

に加算するアルゴリズム

を計算するアルゴリズム

つずつ増やしながら変数wに加算する

アルゴリズムの違いによって実行時間に大きな差が生じる

ごく一般的な処理であり、高速なアルゴリズムを理解しておくことは何かの役に立つこれから、並べ替えのアルゴリズムを説明

あるいは小さい順

先頭に最も小さな値、残りのデータのうち最も小さな値が

プログラム中で共通して使用するものをマクロとして定義すると良い

プログラム中でマクロ名と同じ文字列が現れると、マクロの値に置き換わる

マクロ名値

関数内で宣言した変数は、その関数の中でのみ有効

部分的に整列済みのデータの適切な位置に、新たなデータを挿入する

少ない手数で大雑把な整列を行いその後に厳密な挿入ソートを行う

の値を小さなものに入れ替えながら概略挿入ソートを繰り返し実行