A[i+1]

平成28年度前期
データ構造とアルゴリズムⅠ
第8回
岩田一樹
連絡先： [email protected]
http://www.tfu.ac.jp/kenkyushitsu/iwata/
復習：整列アルゴリズム
ソートとは?
複数の要素からなるデータ列を、ある特定の規則に従って並
べ替えること。日本語では整列。
具体には、数値を大きい順(小さい順)で並べ替えたり、文字
列を五十音順で並べ替えること。
また、
小さい順に並べることを「昇順」(Non-decreasing Order)
A[0]<A[1]<A[2] <・・・<A[i] <A[i+1]< ・・・<A[n]
大きい順に並べることを「降順」(Non-increasing Order)
A[0]>A[1]>A[2]>・・・>A[i]>A[i+1]>・・・>A[n]
と呼ぶ。
整列済みの必要十分条件
全ての i (i≧0) に対して、
A[i]＜A[i+1] （ A[i]＞A[i+1] ）
を満たす状態になっていれば、
昇順
昇順（降順）
に整列済み
A[0]
A[1]
A[2]
A[3]
A[4]
1
2
5
8
9
A[0]
A[1]
A[2]
A[3]
A[4]
9
8
5
2
1
降順
選択ソート(Selection Sort)
選択ソート（Selection Sort）
問題：ソート対象データを昇順にならべる
ソート対象データ数 - 1
未ソートの範囲内で最小
値を選出
最小値と
ソート済みでない最大
Suffixの配列値を交換
選択ソート（Selection Sort）
問題：ソート対象データを昇順にならべる
ソート対象データ数 - 1
未ソートの範囲内で最
小値を選出
最小値と
ソート済みでない最大
Suffixの配列値を交換
i = 未ソート・データ数
Min > A[i]
Yes
Min = A[i], s = i
Buf=A[j]
A[j]=min
A[s]=Buf
No
選択ソートのハンドシュミレーション
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
ソート対象データ
A[0]
A[1]
A[2]
A[3]
A[4]
5
2
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
5
2
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
1
2
8
9
5
A[0]
A[1]
A[2]
A[3]
A[4]
1
2
8
9
5
A[0]
A[1]
A[2]
A[3]
A[4]
1
2
5
9
8
A[0]
A[1]
A[2]
A[3]
A[4]
1
2
5
8
9
配列値を見る
A[4]が最小値
A[0]⇔A[4]
配列値を見る
A[1]が最小値
A[1]⇔A[1]
配列値を見る
A[4]が最小値
A[2]⇔A[4]
配列値を見る
A[4]が最小値
A[3]⇔A[4]
選択ソート（Selection Sort）
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
Selection Sortの手順をフローチャートで示そ
う
ポイント
i=1, j=0
j：決定している配列番号を指すパラ
buf=0, min=A[0],s=0
メータ
j=ソート対象データ数 - 1
i：比較している相手を指すパラメータ
i = 未ソート・データ数
e.g. in c
Min > A[i]
Yes
Min = A[i], s = i
i = i+1
Buf=A[j]
A[j]=min
A[s]=Buf
j = j+1
i = j+1, s=j
No
for(j=0; j=4; j++){
min=A[j]; s=j;
for(i=j+1; i=5; i++){
if(min>A[i]){
min=A[i]; s=i ; }
buf=A[j];
A[j]=A[s];
A[s]=buf ; } }
j=0
A[0]
i=1
A[1]
i=2
A[2]
i=3
A[3]
i=4
A[4]
5
2
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
5
2
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
1
2
8
9
5
i=3
A[3]
i=4
A[4]
9
5
i=4
A[4]
8
j=1
A[0]
A[1]
i=2
A[2]
1
2
8
j=2
A[0]
A[1]
A[2]
i=3
A[3]
1
2
5
9
j=3
A[0]
A[1]
A[2]
A[3]
i=4
A[4]
1
2
5
8
9
iを1から4まで振る
A[4]が最小値
A[0]⇔A[4]
iを2から4まで振る
A[1]が最小値
A[1]⇔A[1]
iを3から4まで振る
A[4]が最小値
A[2]⇔A[4]
iを4から4まで振る
A[4]が最小値
A[3]⇔A[4]
選択ソート（Selection Sort）
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
Selection Sortの手順をフローチャートで示そ
う
ポイント
i=0, j=0
j：決定している配列番号を指すパラ
buf=0, min=A[0],s=0
メータ
j=ソート対象データ数 - 1
i：比較している相手を指すパラメータ
i = 未ソート・データ数
e.g. in c
Min > A[i]
Yes
Min = A[i], s = i
i = i+1
Buf=A[j]
A[j]=min
A[s]=Buf
j = j+1
i = j+1, s=j
No
for(j=0; j=4; j++){
min=A[j]; s=j;
for(i=j+1; i=5; i++){
if(min>A[i]){
min=A[i]; s=i ; }
buf=A[j];
A[j]=A[s];
A[s]=buf ; } }
バブル・ソート（Bubble Sort）
バブル・ソート（Bubble Sort）
問題：ソート対象データを昇順にならべる
ソート対象データ数 - 1
未ソート範囲において、
A[i]>A[i+1]
Yes
A[i]とA[i+1]を交換
を繰り返す
No
バブル・ソート（Bubble Sort）
問題：ソート対象データを昇順にならべる
ソート対象データ数 - 1
未ソート範囲において、
i = 未ソート・データ数
A[i]>A[i+1]
A[i]>A[i+1]
Yes
A[i]とA[i+1]を交換
を繰り返す
No
Yes
Buf=A[i]
A[i]=A[i+1]
A[i+1]=Buf
No
バブル・ソートのハンドシュミレー
ション
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
ソート対象データ
A[0]
A[1]
A[2]
A[3]
A[4]
5
2
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
1
9
Already Sorted
i=0
A[0] > A[1]
A[0]⇔A[1]
i=1
A[1] < A[2]
何もしない
i=2
A[2] < A[3]
何もしない
i=3
A[3] > A[4]
A[3]⇔A[4]
バブル・ソートのハンドシュミレー
ション
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にな
らべる
ソート対象データ
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
1
9
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
1
9
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
1
9
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
1
8
9
Already Sorted
i=0
A[0] < A[1]
何もしない
i=1
A[1] < A[2]
何もしない
i=2
A[2] > A[3]
A[2]⇔A[3]
バブル・ソートのハンドシュミレー
ション
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にな
らべる
ソート対象データ
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
1
8
9
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
1
8
9
A[0]
A[1]
A[2]
A[3]
A[4]
2
1
5
8
9
Already Sorted
i=0
A[0] < A[1]
何もしない
i=1
A[1] > A[2]
A[1]⇔A[2]
バブル・ソート（Bubble Sort）
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
Selection Sortの手順をフローチャートで示そ
う
i=0, j=データ数-1
ポイント
j：決定している配列番号を指すパラ
buf=0
メータ
j=0
i：比較している場所を指すパラメータ
i = 未ソート・データ数=j
A[i]>A[i+1]
Yes
Buf=A[i]
A[i]=A[i+1]
A[i+1]=Buf
i = i+1
j = j-1
i=0
No
e.g. in c
for(j=4; j=1; j--){
for(i=0; i=j; i++) {
if(A[i]>A[i+1]) {
buf=A[i];
A[i]=A[i+1];
A[i+1]=buf ;} } }
バブル・ソートのハンドシュミレー
ション
i=0
A[0]
i=1
A[1]
i=2
A[2]
i=3
A[3]
j=4
i=4
A[4]
5
2
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
9
1
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
1
9
Already Sorted
i=0
A[0] > A[1]
A[0]⇔A[1]
i=1
A[1] < A[2]
何もしない
i=2
A[2] < A[3]
何もしない
i=3
A[3] > A[4]
A[3]⇔A[4]
バブル・ソートのハンドシュミレー
ション
i=0
A[0]
i=1
A[1]
i=2
A[2]
j=3
i=3
A[3]
2
5
8
1
9
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
1
9
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
8
1
9
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
1
8
9
A[4]
Already Sorted
i=0
A[0] < A[1]
何もしない
i=1
A[1] < A[2]
何もしない
i=2
A[2] > A[3]
A[2]⇔A[3]
バブル・ソートのハンドシュミレー
ション
i=0
A[0]
i=1
A[1]
j=2
i=2
A[2]
2
5
1
8
9
A[0]
A[1]
A[2]
A[3]
A[4]
2
5
1
8
9
A[0]
A[1]
A[2]
A[3]
A[4]
2
1
5
8
9
A[3]
A[4]
Already Sorted
i=0
A[0] < A[1]
何もしない
i=1
A[1] > A[2]
A[1]⇔A[2]
バブル・ソートのハンドシュミレー
ション
i=0
A[0]
j=1
i=1
A[1]
A[2]
A[3]
A[4]
2
1
5
8
9
A[0]
A[1]
A[2]
A[3]
A[4]
1
2
5
8
9
Already Sorted
i=0
A[0] < A[1]
A[0]⇔A[1]
オシマイ
本日の講義内容
• 挿入ソート（Insertion Sort）
おまけ
– シェーカソート
– シェルソート
• バケットソート（Bucket Sort）
※これからの講義の問題においては、データ内で重
複はないものとする
＝要するに、同じ値は2つ以上ないってこと
挿入ソート（Insertion Sort）
日々の生活に最も即した
アルゴリズム
挿入ソート（Insertion Sort）
Insertion = 挿入
アルゴリズムの思想（昇順整列を考える）
整列済みのデータD[]（D[0], D[1],
D[2]・・・D[n]:D[0]<D[1]<D[2] <・・・
<D[n-1]<D[n]）があった時に、i=nから
decrementしていき、初めて、挿入対象デー
タA[j]がA[j]>D[i]を満たした場所に、A[j]を
挿入する。
挿入ソートのハンドシュミレーション
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
ソート対象データ
A[0]
A[1]
A[2]
A[3]
A[4]
5
2
8
9
1
D[2]
D[3]
D[4]
D[2]
D[3]
D[4]
Not Sort yet
D[0]
D[1]
5
Already Sorted
A[1] < D[0]
D[0]
D[1]
2
5
A[2] > D[0], A[2] > D[1]
D[0]
D[1]
D[2]
2
5
8
D[3]
D[4]
挿入ソートのハンドシュミレーション
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
ソート対象データ
A[0]
A[1]
A[2]
A[3]
A[4]
5
2
8
9
1
D[4]
Not Sort yet
A[3] > D[0], A[3] > D[1], A[3] > D[2]
D[0]
D[1]
D[2]
D[3]
2
5
8
9
Already Sorted
A[4] < D[0]
D[0]
D[1]
D[2]
D[3]
D[4]
1
2
5
8
9
Already Sorted
オシマイ
挿入ソートのポイント
• 挿入処理をどう表現するか？
– 挿入が得意な、リスト構造を使う
– 挿入位置を決めたら、それ以降すべてのデータ
をずらしてから入れる
– 交換の繰返しで、挿入位置まで動かす
挿入ソートのハンドシュミレーション
A[0]
A[1]
A[2]
A[3]
A[4]
5
2
8
9
1
i=0
A[0]
j=1
i=1
A[1]
A[2]
A[3]
A[4]
5
2
8
9
1
D[3]
D[4]
9
1
i=2
D[2]
j=3
i=3
D[3]
D[4]
8
9
1
Already Sorted
A[0] >A[1]
Not Sort yet
i=0
D[0]
i=1
D[1]
j=2
i=2
D[2]
2
5
8
i=0
D[0]
i=1
D[1]
2
5
A[1] < A[2]
挿入ソートのハンドシュミレーション
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にな
らべる
ソート対象データ
A[0]
A[1]
A[2]
A[3]
A[4]
5
2
8
9
1
i=3
A[3]
j=4
i=4
A[4]
Not Sort yet
i=0
A[0]
i=1
A[1]
i=2
A[2]
2
5
8
A[2]<A[3]
9
Already Sorted
A[0] > A[1]
i=0
A[0]
i=1
A[1]
i=2
A[2]
i=3
A[3]
i=4
A[4]
1
2
5
8
9
Already Sorted
オシマイ
j=5
i=5
挿入ソート（Insertion Sort）
の流れ図
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
挿入ソートの手順をフローチャートで示そう
初期化
ランニングパラメータ i, j
Buffer変数 Buf
繰返す処理①
A[i]とA[i-1]を比較していきA[i-1]>A[i]ならA[i-1]⇔A[i]をする
ループ条件
iをdecrementしていき、i=1となる
繰返す処理②（挿入）
繰返す処理①
ループ条件
ソート対象データ数
挿入ソート（Insertion Sort）
の流れ図
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
Insertion Sortの手順をフローチャートで示そう
A[0]=5, A[1]=2, A[2]=8, A[3]=9, A[4]=1
開始
i=j=1
繰返し②
繰返し①
buf=0
j=5
No
i=0
No
A[i-1] > A[i]
Yes
buf=A[i]
A[i]=A[i-1]
A[i-1]=buf
i= i-1
Yes
オシマイ
Yes
j=j+1
No
i=j
ポイント
j：ソート済みの範囲を示すパラメータ
（j-1の配列値までソート済み）
i：比較している場所を指すパラメータ
e.g. in c
for(j=1; j=5; j++){
for(i=j; i=1; i--){
if(A[i-1]>A[i]) {
buf=A[i];
A[i]=A[i-1];
A[i-1]=buf ;} } }
挿入ソート（Insertion Sort）
の流れ図
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
Insertion Sortの手順をフローチャートで示そう
A[0]=5, A[1]=2, A[2]=8, A[3]=9, A[4]=1
開始
i=j=1
繰返し②
繰返し①
buf=0
j=5
No
i=0
No
A[i-1] > A[i]
Yes
buf=A[i]
A[i]=A[i-1]
A[i-1]=buf
i= i-1
Yes
オシマイ
Yes
j=j+1
No
i=j
ポイント
j：ソート済みの範囲を示すパラメータ
（j-1の配列値までソート済み）
i：比較している場所を指すパラメータ
e.g. in c
for(j=1; j=5; j++){
for(i=j; i=0; i--){
if(A[i-1]>A[i]) {
buf=A[i];
A[i]=A[i-1];
A[i]=buf ;} } }
まだ改善できる
宿題：上記の流れ図を改善するには、どうしたらよいか?
挿入ソート（Insertion Sort）が活躍する場面
普通、1から（全データ）の整列に挿入ソート
は使用しない。
挿入ソートは「ソート済みデータ」に新しく、
ソート対象データを付加する場合に使う
A[0]
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[7]
1
2
5
8
9
7
3
4
Already Sorted
Added Data
おまけ
・シェーカソート（Shaker Sort）
・シェルソート（Shell Sort）
それぞれ、
・バブル・ソート
・挿入ソート
の改良型
バブル・ソートの改良
バブル・ソート
基本、Sweep 1回に付き1ヶ所、配列値が決定
※ Sweep中、ランニングパラメータの終わり
から数えて、交換がない場所はソート済
ソート済みの範囲を上手に省くことで、
比較数を減らし、整列速度の向上が可能
改良版バブル・ソートのF. C.
ポイント
・交換がないことをどう表現するか？
j=データ数-1
buf=0
j=0
j=データ数-1
buf=0
j=0
k=i=0
i=j
A[i]>A[i+1]
Yes
buf=A[i]
A[i]=A[i+1]
A[i+1]=buf
k=i
i = i+1
No
i=0
i=j
A[i]>A[i+1]
Yes
buf=A[i]
A[i]=A[i+1]
A[i+1]=buf
i = i+1
j=k
j = j-1
No
シェーカ・ソート（Shaker Sort）
ポイント
整列を速くする
＝比較と交換の回数を減らす
改良版バブルからさらに、比較と交換の回数
を減らすために・・・
Sweepの方向を → だけでなく、←も使う
バブル・ソート
シェーカー・ソート
シェーカとバブルの比較2：良い例
シェーカ・ソート
[2, 3, 1, 4, 7, 8, 5, 6]
[2, 1, 3, 4, 7, 5, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
交換回数
19回 VS 22回
バブル・ソート
3回 [2, 3, 1, 4, 7, 8, 5, 6] 3回
2回 [2, 1, 3, 4, 7, 5, 6, 8] 3回
1回 [1, 2, 3, 4, 5, 6, 7, 8] 0回
0回
シェーカとバブルの比較2：悪い例
シェーカ・ソート
[8, 4, 3, 7, 6, 5, 2, 1]
[4, 3, 7, 6, 5, 2, 1, 8]
[1, 4, 3, 7, 6, 5, 2, 8]
[1, 3, 4, 6, 5, 2, 7, 8]
[1, 2, 3, 4, 6, 5, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
交換回数
19回 VS 22回
バブル・ソート
7回
6回
4回
4回
4回
[8, 4, 3, 7, 6, 5, 2, 1]
[4, 3, 7, 6, 5, 2, 1, 8]
[3, 4, 6, 5, 2, 1, 7, 8]
[3, 4, 5, 2, 1, 6, 7, 8]
[3, 4, 2, 1, 5, 6, 7, 8]
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
7回
5回
3回
2回
2回
2回
1回
シェル・ソート
（挿入ソートの改良）
挿入ソート
データが“整列状態に近い程”高速
データを、大まかに整列させて、その後、
挿入ソートを行うことで高速化？
この思想の下で構築されたアルゴリズム
を「シェル・ソート」（Shell Sort）と呼ぶ
シェル・ソート
（挿入ソートの改良版）
動作例比較間隔を4 ∗ 1⁄2 𝑘𝑘 とする場合
シェルと挿入の比較
シェル・ソート
挿入・ソート
[8, 4, 3, 7, 6, 5, 2, 1]
[8, 4, 3, 7, 6, 5, 2, 1]
[6, 4, 2, 1, 8, 5, 3, 7] 3回 [4, 8, 3, 7, 6, 5, 2, 1]
[2, 1, 3, 4, 6, 5, 8, 7] 4回 [3, 4, 8, 7, 6, 5, 2, 1]
[1, 2, 3, 4, 5, 6, 7, 8] 3回 [3, 4, 7, 8, 6, 5, 2, 1]
[3,
4,
6,
7,
8,
5,
2,
1]
交換回数
[3, 4, 5, 6, 7, 8, 2, 1]
10回 VS 22回
＝劇的に少ない
[2, 3, 4, 5, 6, 7, 8, 1]
→Q.S.が見つかるまで最速
の汎用整列アルゴリズム [1, 2, 3, 4, 5, 6, 7, 8]
1回
2回
1回
2回
3回
6回
7回
バケット・ソート (Bucket Sort)
これまでの3つは比較と交換によって、
整列させる。
バケット・ソートはこれらを用いない
特殊な整列アルゴリズム
特定の条件を満たせば、最速
バケット・ソート（Bucket Sort）
Bucket = バケツ
単純な整列アルゴリズム
（考え方はちょっと特殊）
アルゴリズムの思想
1. 「ソート対象のデータ」の「取り得る範囲
分」のBucketを準備する
2. Bucketにソート対象のデータを入れる
3. データの入っているBucketから背番号の小
さい（大きい）順に取り出し並べる
バケット・ソート（Bucket Sort）
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
ソート対象データ
A[0]
A[1]
A[2]
A[3]
A[4]
5
2
8
9
1
初期化されたBucketデータ
B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
0
0
0
0
0
0
0
0
0
0
ソート対象データ入りBucketデータ
B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
0
1
1
0
0
1
0
0
1
1
ソート対象データ入りBucketデータで1の入っている添え字を小さい順に並べる
A’[0]
A’[1]
A’[2]
A’[3]
A’[4]
1
2
5
8
9
バケット・ソート（Bucket Sort）
問題：ソート対象データを5, 2, 8, 9, 1とし、昇順にならべる
Bucket Sortの手順をフローチャートで示
そう
初期化
結果を表す配列 A’[]（人によってはA[]に入れる人も
いる）
ランニングパラメータ i
添え字のパラメータ j
Bucketを表す配列 B[]
繰返す処理①
ソート対象データの数値と同じ添え字のB[]に1を加える
ループ条件
ソート対象データ数
繰返す処理②
B[i]=1の場合に、A[]にiを代入する
ループ条件
準備したBucketの配列長
Bucket Sortは繰返し処理が2つあるアルゴリズム
e.g. in c
バケットソート（Bucket
Sort）
for (i=0;i<10;i++){B[i]=0;}
問題：ソート対象データを5, 2, 8, for(i=0;i<10;i++){B[A[i]]=1;}
9, 1とし、昇順にならべる
Bucket Sortの手順をフローチャートで示
for(i=0;i<10;i++){
そう
A[0]=5, A[1]=2, A[2]=8, A[3]=9, A[4]=1
if(B[i]>0){A’[ｊ]=i;j++;}}
開始
i=0, j=0
i = 10
A’[], B[]
B[]の初期化
No
i = 10
Bucketに値を
放り込む
i=5
i=0
Yes
No
B[A[i]] = B[A[i]]+1
i=i+1
A’[j] = i
j=j+1
B[i] = 0
i= i+1
繰返し①
Yes
Yes
B[i] > 0
i=0
i=i+1
Yes
オシマイ
No
繰返し②
Bucketに値が入ってい
るもの昇順に並べる
Bucket Sortの特徴
長所
• 処理速度が非常に速い（最速）
短所
• 記憶領域を必要以上に使用する
e.g.
情報が、32bit数字だけだと、43億個のバケツが必要
制限なし文字列では、バケツの準備すら不可能
シェル・ソートのF. C.
Gap=4
i=j=Gap
ポイント
・Gapの変化をどう表現するか
Gap≧1:True
j<データ数:True
i ＞０:True
A[i-1]>A[i]
Yes
buf=A[i]
A[i]=A[i-1]
A[i-1]=buf
i = i-Gap
i=j=j+Gap
Gap=Gap/2
i=j=Gap
No

Download Report