[アルゴリズム]バブルソート
4319 ワード
プログラミングの開始時に通常初めて接触するソートバブルソート
バブルソート
1-1. 最後のインデックスでは、最大の要素がその場所の適切な場所に配置されます. したがって、以降i+1≦i
時間の複雑さ
Bubble Sortを見てみましょう.バブルソート
隣接する要素間の比較は、現在のインデックスを基準とし、次のインデックスの要素が大きい場合は、位置を交換します.
iは2番目のインデックスから始まり、次のインデックスi+1の要素が現在のiより大きい場合に置き換えられます.(0≤i絵をかく
時間の複雑さ
(n−1)+(n−2)+…dots…+1=n(n+1)2frac{n(n+1)}{2}2 n(n+1)であるため,時間的複雑度はO(n 2)O({n}^2})O(n 2)である.並べ替えの有無にかかわらず同じ論理が実行されるため,最適,平均,最悪の論理はO(n 2)O({n}^{2})O(n 2)である.
ソース template<typename T>
class BubbleSort
{
public:
static void sort(vector<T>& arr)
{
if(arr.size() <= 1) return;
for(int i = 0; i < arr.size(); ++i)
{
for(int j = 1; j < arr.size() - i; ++j)
{
if(arr[j] < arr[j - 1])
swap(arr[j], arr[j - 1]);
}
}
}
};
template<typename T>
class BubbleSort
{
public:
static void sort(vector<T>& arr)
{
if(arr.size() <= 1) return;
for(int i = 0; i < arr.size(); ++i)
{
for(int j = 1; j < arr.size() - i; ++j)
{
if(arr[j] < arr[j - 1])
swap(arr[j], arr[j - 1]);
}
}
}
};Reference
この問題について([アルゴリズム]バブルソート), 我々は、より多くの情報をここで見つけました https://velog.io/@redgem92/알고리즘-거품-정렬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol