C++の基礎 - ソート - 版の履歴

Wiki: /* 単純挿入法 (挿入ソート) */

2025-01-20T02:54:11Z

単純挿入法 (挿入ソート)

@@ 238行目: / 238行目: @@
   ステップ 6: 11 12 22 25 34 64 90 50  # 90は既にソート済み部分の要素より大きいため、位置は変わらない
   ステップ 7: 11 12 22 25 34 50 64 90  # 50を64と90の間の適切な位置に挿入する
   ソート後の配列: 11 12 22 25 34 50 64 90

Wiki: /* バブルソート */

2025-01-20T01:27:35Z

バブルソート

← 古い版		2025年1月20日 (月) 10:27時点における版
4行目:		4行目:

	== バブルソート ==		== バブルソート ==
	バブルソートは、隣接する要素を順次比較して、必要に応じて交換を行うソートアルゴリズムである。		バブルソートは、隣接する要素を順次比較して、必要に応じて交換を行うソートアルゴリズムである。<br>
	大きな値が徐々に右側に移動していく様子が、泡が水面に浮かび上がっていく様子に似ていることから、この名前が付けられた。		大きな値が徐々に右側に移動していく様子が、泡が水面に浮かび上がっていく様子に似ていることから、この名前が付けられた。<br>
			<br>
	# 配列の先頭から順に隣接する要素を比較して、左の要素が右の要素より大きい場合に交換を行う。		# 配列の先頭から順に隣接する要素を比較して、左の要素が右の要素より大きい場合に交換を行う。
	# この操作を1回行うと、最も大きな要素が配列の最後尾に移動する。		# この操作を1回行うと、最も大きな要素が配列の最後尾に移動する。
	# 次の走査では、最後尾を除いた範囲で同様の操作を行い、これを繰り返す。		# 次の走査では、最後尾を除いた範囲で同様の操作を行い、これを繰り返す。
	<br>		<br>
	バブルソートの実装は簡単であるが、計算量は <math>O(n^2)</math> となる。		バブルソートの実装は簡単であるが、計算量は <math>O(n^2)</math> となる。<br>
	安定なソートであるため、追加のメモリをほぼ必要としないというメリットがある。		安定なソートであるため、追加のメモリをほぼ必要としないというメリットがある。<br>
	<br>		<br>
	<syntaxhighlight lang="c++">		<syntaxhighlight lang="c++">

Wiki: /* 概要 */

2025-01-20T01:13:40Z

概要

← 古い版		2025年1月20日 (月) 10:13時点における版
1行目:		1行目:
	== 概要 ==		== 概要 ==

			<br><br>

			== バブルソート ==
			バブルソートは、隣接する要素を順次比較して、必要に応じて交換を行うソートアルゴリズムである。
			大きな値が徐々に右側に移動していく様子が、泡が水面に浮かび上がっていく様子に似ていることから、この名前が付けられた。

			# 配列の先頭から順に隣接する要素を比較して、左の要素が右の要素より大きい場合に交換を行う。
			# この操作を1回行うと、最も大きな要素が配列の最後尾に移動する。
			# 次の走査では、最後尾を除いた範囲で同様の操作を行い、これを繰り返す。
			<br>
			バブルソートの実装は簡単であるが、計算量は <math>O(n^2)</math> となる。
			安定なソートであるため、追加のメモリをほぼ必要としないというメリットがある。
			<br>
			<syntaxhighlight lang="c++">
			#include <iostream>

			using namespace std;

			int main()
			{
			int arr[8] = {64, 34, 25, 12, 22, 11, 90, 50};
			int n = 8; // 配列のサイズ

			cout << "ソート前の配列: ";
			for (int i = 0; i < n; i++) {
			cout << arr[i] << " ";
			}
			cout << endl;

			// バブルソートのアルゴリズム
			for (int i = 0; i < n - 1; i++) {
			bool swapped = false; // 交換が発生したかを記録

			for (int j = 0; j < n - 1 - i; j++) {
			// 隣接要素を比較し、必要に応じて交換
			if (arr[j] > arr[j + 1]) {
			int temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
			swapped = true;
			}
			}

			// 各ステップでの配列の状態を表示
			cout << "ステップ " << i + 1 << ": ";
			for (int k = 0; k < n; k++) {
			cout << arr[k] << " ";
			}
			cout << endl;

			// 交換が発生しなければソート完了
			if (!swapped) {
			break;
			}
			}

			cout << "ソート後の配列: ";
			for (int i = 0; i < n; i++) {
			cout << arr[i] << " ";
			}
			cout << endl;

			return 0;
			}
			</syntaxhighlight>
			<br>
			# 出力例:

			ソート前の配列: 64 34 25 12 22 11 90 50

			ステップ 1: 34 25 12 22 11 64 50 90
			ステップ 2: 25 12 22 11 34 50 64 90
			ステップ 3: 12 22 11 25 34 50 64 90
			ステップ 4: 12 11 22 25 34 50 64 90
			ステップ 5: 11 12 22 25 34 50 64 90

			ソート後の配列: 11 12 22 25 34 50 64 90
	<br><br>		<br><br>

Wiki: /* 単純挿入法 (挿入ソート) */

2025-01-20T01:01:22Z

単純挿入法 (挿入ソート)

@@ 149行目: / 149行目: @@
+  }
   </syntaxhighlight>
 <br><br>

Wiki: /* 単純選択法 (選択ソート) */

2025-01-20T00:51:52Z

単純選択法 (選択ソート)

@@ 17行目: / 17行目: @@
 単純選択法のアルゴリズムの特徴として、データの並びに関係なく常に一定の比較回数が必要となるため、効率は悪い。<br>
 配列の長さをnとすると、計算量は <math>O(n^2)</math> となる。<br>
 また、既にある程度ソートされているデータに対しても、完全にランダムなデータと同じ処理時間が掛かるという特徴がある。<br>
 ただし、必要な追加のメモリ容量が少ないというメリットがある。<br>
@@ 84行目: / 85行目: @@
   ソート後の配列: 11 12 22 25 34 50 64 90
 <br><br>

Wiki: ページの作成:「== 概要 ==

== 単純選択法 (選択ソート) == 単純選択法 (選択ソート) は、未ソートの部分から最小値 (または最大値) を見つけて、それを適切な位置に配置していくアルゴリズムである。

# まず、データ列の先頭から順に、その位置以降で最小の要素を探索する。 # 最小の要素が見つかった場合、探索を開始した位置の要素と交換する。 #…」

2025-01-20T00:29:58Z

ページの作成:「== 概要 == == 単純選択法 (選択ソート) == 単純選択法 (選択ソート) は、未ソートの部分から最小値 (または最大値) を見つけて、それを適切な位置に配置していくアルゴリズムである。 # まず、データ列の先頭から順に、その位置以降で最小の要素を探索する。 # 最小の要素が見つかった場合、探索を開始した位置の要素と交換する。 #…」

新規ページ

== 概要 ==

 

== 単純選択法 (選択ソート) ==
単純選択法 (選択ソート) は、未ソートの部分から最小値 (または最大値) を見つけて、それを適切な位置に配置していくアルゴリズムである。 
 
# まず、データ列の先頭から順に、その位置以降で最小の要素を探索する。
# 最小の要素が見つかった場合、探索を開始した位置の要素と交換する。
# この操作を、配列の最後の要素の手前まで繰り返すことにより、データを昇順 (または降順) に整列することができる。
 
例えば、{5, 3, 1, 4, 2}という配列をソートする場合、 
まず最初の位置から開始して、全体から最小値 (この場合では1) を見つけて、最初の位置 (この場合では5) と交換する。 
次に、2番目の位置 (この場合では3) から開始して残りの要素から次の最小値の2を見つけて、3と交換する。 
この処理を順々に繰り返す。 
 
単純選択法のアルゴリズムの特徴として、データの並びに関係なく常に一定の比較回数が必要となるため、効率は悪い。 
配列の長さをnとすると、計算量は <math>O(n^2)</math> となる。 
また、既にある程度ソートされているデータに対しても、完全にランダムなデータと同じ処理時間が掛かるという特徴がある。 
ただし、必要な追加のメモリ容量が少ないというメリットがある。 
 
<syntaxhighlight lang="c++">
#include <iostream>

using namespace std;

int main()
{
// 配列 (要素数8) を初期化
int arr[8] = {64, 34, 25, 12, 22, 11, 90, 50};
int n = 8; // 配列のサイズ

cout << "ソート前の配列: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;

// 選択ソートのアルゴリズム
for (int i = 0; i < n - 1; i++) {
// 未ソート部分から最小値を探す
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}

// 最小値を見つけたら、現在の位置と交換
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}

// 各ステップでの配列の状態を表示
cout << "ステップ " << i+1 << ": ";
for (int k = 0; k < n; k++) {
cout << arr[k] << " ";
}
cout << endl;
}

cout << "ソート後の配列: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;

return 0;
}
</syntaxhighlight>
 
# 出力例:
ソート前の配列: 64 34 25 12 22 11 90 50

ステップ 1: 11 34 25 12 22 64 90 50
ステップ 2: 11 12 25 34 22 64 90 50
ステップ 3: 11 12 22 34 25 64 90 50
ステップ 4: 11 12 22 25 34 64 90 50
ステップ 5: 11 12 22 25 34 64 90 50
ステップ 6: 11 12 22 25 34 50 90 64
ステップ 7: 11 12 22 25 34 50 64 90

ソート後の配列: 11 12 22 25 34 50 64 90
 

{{#seo:
|title={{PAGENAME}} : Exploring Electronics and SUSE Linux | MochiuWiki
|keywords=MochiuWiki,Mochiu,Wiki,Mochiu Wiki,Electric Circuit,Electric,pcb,Mathematics,AVR,TI,STMicro,AVR,ATmega,MSP430,STM,Arduino,Xilinx,FPGA,Verilog,HDL,PinePhone,Pine Phone,Raspberry,Raspberry Pi,C,C++,C#,Qt,Qml,MFC,Shell,Bash,Zsh,Fish,SUSE,SLE,Suse Enterprise,Suse Linux,openSUSE,open SUSE,Leap,Linux,uCLnux,Podman,電気回路,電子回路,基板,プリント基板
|description={{PAGENAME}} - 電子回路とSUSE Linuxに関する情報 | This page is {{PAGENAME}} in our wiki about electronic circuits and SUSE Linux
|image=/resources/assets/MochiuLogo_Single_Blue.png
}}

__FORCETOC__
[[カテゴリ:C++]]