Sort(2)-Bubble Sort(泡の位置合わせ)

バブルソート(Bubble Sort)

:(昇順)隣のデータと比較して、小さな値を前に送信します.
Selection Sortの場合と同じ例をあげましょう
7 1 5 4 2このように5つの数字を昇順に並べます
7 1 5 4 2
1番目の要素7を次の要素1と比較して、より小さな値1を前方に送信します.
7 1 5 4 2
1 7 5 4 2
2番目の要素7を次の要素5と比較して、より小さな値5を前に送信します.
1 7 5 4 2
1 5 7 4 2
上記の操作をデータの末尾に繰り返すと、次のような形になります.
1 5 4 2 7
最初のループが終了し、2番目の要素から、次の要素との比較が再開されます.
1 5 4 2 7
これで最後の一周に回ると並べ替えが完了します.
1 2 4 5 7

コード#コード#

Bubble_Sort(int arr[], int n) {
	for(int i = 0; i < n - 1; i++) {
    		for(int j = i + 1; j < (n - 1) - i; j++) {
            		//arr[j]와 arr[j + 1]를 비교
                    	//arr[j]가 크기가 더 크다면 둘의 위치를 변경
            	}
    	}
}

時間の複雑さ

N個のデータの場合、ダブルfor文でN回+N-1回+…+1回実行するので、N(N+1)/2回比較演算を実行する.したがって,時間的複雑度OはO(N^2)に従う.しかし、比較演算を継続すると、同じO(n^2)選択よりもソートが遅いソートと考えられる.