![boolean ?ag;
do {
! ?ag = false;
! for (int i = 0; i < N - 1; i++) {
! ! if (sort[i] > sort[i + 1]) {
! ! ! ?ag = true;
! ! ! int j = sort[i];
! ! ! sort[i] = sort[i + 1];
! ! ! sort[i + 1] = j;
! ! }
! }
} while (?ag);
13年9月15日日曜日](https://image.slidesharecdn.com/random-130914224034-phpapp02/85/-6-320.jpg)
![boolean ?ag = false;
int k = 0;
do {
for (int i = 0; i < N - 1 - k; i++) {
if (sort[i] > sort[i + 1]) {
?ag = true;
int j = sort[i];
sort[i] = sort[i + 1];
sort[i + 1] = j;
}
}
k++;
} while (?ag);
13年9月15日日曜日](https://image.slidesharecdn.com/random-130914224034-phpapp02/85/-10-320.jpg)
![boolean ?ag = false;
int k = 0;
do {
for (int i = 0; i < N - 1 - k; i++) {
if (sort[i] > sort[i + 1]) {
?ag = true;
int j = sort[i];
sort[i] = sort[i + 1];
sort[i + 1] = j;
}
}
k++;
} while (?ag);
確定部分は対象外
13年9月15日日曜日](https://image.slidesharecdn.com/random-130914224034-phpapp02/85/-11-320.jpg)
バブルソート
- 2. アルゴリズムデータ構造って何？ ? 定番、常識、基礎知識 ? アルゴリズムとは「サーチ」、「ソート」など ? データ構造とは「リスト」、「スタック」など 13年9月15日日曜日
- 4. バブルソート ? ソートとは、あるデータを規則に従って並び 替えること ? 最も単純なソートアルゴリズム ? 先頭から並び替えを行い、最後までたどり着 いたらまた先頭から、というのを並び替えが 発生しなくなるまでやる 13年9月15日日曜日
- 6. boolean ?ag; do { ! ?ag = false; ! for (int i = 0; i < N - 1; i++) { ! ! if (sort[i] > sort[i + 1]) { ! ! ! ?ag = true; ! ! ! int j = sort[i]; ! ! ! sort[i] = sort[i + 1]; ! ! ! sort[i + 1] = j; ! ! } ! } } while (?ag); 13年9月15日日曜日
- 7. メリット ? アルゴリズムが簡単 デメリット ? データ量が多くなると処理速度が劣化する ? データが5個の時は最大でも25回の入れ替 えで済むが、1万個になると1億回近く入れ 替えが発生する 13年9月15日日曜日
- 8. バブルソート改良版 ? バブルソートは「ループが1回終了するごと に、配列の後方要素は確実にソート済みにな っている」という性質がある ? よって、この性質を利用して繰り返し回数を半 分にすることができる ? 一般的にバブルソートとはこちらの方法を指す 13年9月15日日曜日
- 10. boolean ?ag = false; int k = 0; do { for (int i = 0; i < N - 1 - k; i++) { if (sort[i] > sort[i + 1]) { ?ag = true; int j = sort[i]; sort[i] = sort[i + 1]; sort[i + 1] = j; } } k++; } while (?ag); 13年9月15日日曜日
- 11. boolean ?ag = false; int k = 0; do { for (int i = 0; i < N - 1 - k; i++) { if (sort[i] > sort[i + 1]) { ?ag = true; int j = sort[i]; sort[i] = sort[i + 1]; sort[i + 1] = j; } } k++; } while (?ag); 確定部分は対象外 13年9月15日日曜日
- 12. まとめ ? 数十個のデータならバブルソートの性能でも問 題ない ? それ以上のデータであれば、他のソートアルゴ リズムを検討する必要がある ? ちなみにJavaのCollections.sortメソッドのア ルゴリズムはクイックソート変種 13年9月15日日曜日
- 13. おわり 13年9月15日日曜日