ソートアルゴリズムの選択

4599 ワード
algorithm computer science テキストリンク
選択ソートについて議論しましょう.

整列選択(Selection Sort)


0からlength-1まで簡単に、対応するインデックスに適切な要素を加えてソートすると理解します.昇順を基準に、
  • iは、2番目のインデックスから始まり、i+1をチェックし続け、가장 작은 원소のインデックスを検索します.
  • iは、2番目の要素가장 작은 원소가 위치한 인덱스と交換される.
    2-1. これによりi第2の要素が位置を決定する.length - 1までこの操作を繰り返すと、ソートが完了します.

    • 絵をかく



    特長


    選択ソートSelection Sort度発泡ソートBubble Sortと同様に、O(n 2)O(n^{2})O(n 2)である.バブルソートとは異なり、交換回数が少ない(インデックスを作成して交換する)ことは、バブルソートよりも効果的です.
    さらに、追加のアレイIn-placeを必要としないという特徴もある.ただし、場合によっては、正しい位置にある要素も交換されます.これもソートです.

    ソース

    
template<typename T>
class SelectionSort
{
public:
	static void sort(vector<T>& arr)	
	{
		if(arr.size() <= 1)	return;

		int minIndex = 0;
		for(int i = 0; i < arr.size() - 1; ++i)
		{
			minIndex = i;
			for(int j = i + 1; j < arr.size(); ++j)
			{
				if(arr[j] < arr[minIndex])
					minIndex = j;
			}
			swap(arr[i], arr[minIndex]);
		}
	}
};
    TIL 11|外部ファイルへの接続
    帆ソフトの異なる位置で異なる位置コントロールを取得し、コントロールの一般的な方法