ベースソートアルゴリズムまとめ(7種類のソートアルゴリズム)

ソートは最も基礎的なアルゴリズムです.ソートされたオブジェクトは、主に内部ソートと外部ソートに分けられます.内部ソートは主にメモリ内のデータをソートし、外部ソートはハードディスク(HDD)、光ディスクなどの外部ストレージのデータをソートします.内部ソートは、主に、挿入ソート(直接挿入ソート、ヒルソート)、選択ソート(単純選択ソート、スタックソート)、交換ソート(バブルソート、高速ソート)、集計ソート、基数ソートに分けられます.
1.ソートの直接挿入
その基本原理は、並べ替えられる集合から要素を選択し続け、並べ替えられる集合のすべての要素を取り出すまで、秩序ある集合に1つずつ挿入することである.私たちが日常的にトランプをしているように、テーブルからトランプをしながら、抽出したトランプを手に適当な位置に挿入します.実は現代コードは以下の通りです.

/**
* insertSort
* @author liebert
* @param int arr[]      
* @param int len     
*/
void insertSort (int arr[], int len) 
{
	int i, j, key;
	
	for (i = 1; i < len; i++) {
		key = arr[i];
		j = i - 1;
		while (j >= 0 && key <= arr[j]) {
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = key;
	}
}

2.単純選択ソート
その基本的な動作原理は、左の右から集合をスキャンすることであり、集合の左部分は秩序化された集合であり、集合の右は順序付けされる集合に分けられず、順序付けされる集合の中から最大のものを選択するたびに、右側の順序付けされる集合要素が空になるまで、左側の秩序化された集合の中に入れることである.実は現代コードは以下の通りです.

/**
* selectSort
* @author liebert
* @param int arr[]      
* @param int len     
*/
void selectSort (int arr[], int len) 
{
	int i, j, k, temp;
	
	for (i = 0; i < len-1; i++) {
		k = i;
		for (j = i + 1; j < len; j++) {
			if (arr[j] < arr[k]){
				k = j;
			}
		}
		if (i != k){
			temp   = arr[i];
			arr[i] = arr[k];
			arr[k] = temp;
		}
	}
}

3.泡立ちソート
基本的な動作原理は、ソートされたセットを巡回し、左から右にかけて要素ごとにスキャンし、左側の要素が右側より大きい場合(昇順)は、ソートされるセットの最後まで2つの要素を交換し、このとき交換によって最大の要素が得られる.右側の整列集合境界を左に1つ調整します.実は現代コードは以下の通りです.

/**
* bubbleSort
* @author liebert
* @param int arr[]      
* @param int len     
*/
void bubbleSort (int arr[], int len) 
{
	int i, j, temp, flag;
	
	for (i = 0; i < len-1; i++) {
		flag = 0;
		for (j = 0; j < len-i-1; j++) {
			if(arr[j] > arr[j+1]){
				temp     = arr[j];
				arr[j]   = arr[j+1];
				arr[j+1] = temp; 
				flag = 1;
			}
		}
		if (0 == flag) {
			return;
		}
	}
}

4.クイックソート
その基本原理は、並べ替えられる集合を中間要素によって2つのサブ集合に分割し、中間要素が左側の集合の各要素より大きく、右側の集合の各要素より小さいようにする分治思想を採用することである.上記のプロシージャ・アドバイザのサブセットを繰り返す要素の数は1です.実は現代コードは以下の通りです.

/**
* quickSort
* @author liebert
* @param int arr[]      
* @param int l    
* @param int r    
*/
void quickSort (int arr[], int l, int r) 
{
	int mid;
	if(l < r){
		mid = partition(arr, l, r);
		quickSort(arr, l, mid-1);
		quickSort(arr, mid+1, r);
	}
}

/**
* partition
* @author liebert
* @param int arr[]      
* @param int l    
* @param int r    
*/
int partition (int arr[], int l, int r) 
{
	int i, j, mid, temp;
	
	for (i = l-1, j = l; j < r; j++){
		if (arr[r] > arr[j]) {
			i++;
			if (i != j){
				temp   = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
	}
	i++;
	temp   = arr[r];
	arr[r] = arr[i];
	arr[i] = temp;
	return i;
}

5.集計ソート
集計ソートも分治思想を採用したソート方法である.各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化し、既存のシーケンスのサブシーケンスを結合して、完全に秩序化されたシーケンスを得る.その処理フロー:まずソート集合を区分し、2つの比較的小さい非集合に区分する.a[i]とb[j]のサイズを比較し、a[i]≦b[j]の場合、最初の秩序テーブルの要素a[i]をr[k]にコピーし、iとkにそれぞれ1を加算する.そうでなければ、2番目の秩序テーブルの要素b[j]をr[k]にコピーし、jとkにそれぞれ1を加え、そのうちの1つの秩序テーブルが終わるまでループします.次に、別の順序テーブルの残りの要素を、rの下付きkから下付きtのユニットにコピーする.集計ソートのアルゴリズムは通常再帰的に実現され,まずソート対象区間[s,t]を中点二分し,次に左サブ区間をソートし,右サブ区間をソートし,最後に左区間と右区間を一次集計操作で秩序ある区間[s,t]に統合する.実は現代コードは以下の通りです.

/**
* mergeSort
* @author liebert
* @param int arr[]      
* @param int l    
* @param int r    
*/
void mergeSort(int arr[], int result[], int l, int r)
{
	int i, j, mid, m;
	
	if (l < r) {
		mid = (l + r) / 2; //     
		mergeSort(arr, result, l, mid);
		mergeSort(arr, result , mid+1, r);
		//   arr[l, mid] arr[mid+1, r]
		i = l;
		j = mid+1;
		m = l;
		while (i<=mid && j<=r) {
			if (arr[i] < arr[j]) {
				result[m++] = arr[i++];
			} else {
				result[m++] = arr[j++];
			}
		}
		while (i<=mid) {
			result[m++] = arr[i++];
		}
		while (j<=r) {
			result[m++] = arr[j++];
		}
		for(i=l; i<=r; i++) {
			arr[i] = result[i];
		}
	}
}

6.ヒルソート
ヒルソートは直接挿入ソートの改良であり,まず分治の考え方を用いてソート集合の規模を縮小し,すなわちソート対象集合をグループ化し,その後グループ化後の集合を挿入法でソートし,グループ数を絶えず縮小してからグループが1になるまでソートすることで,すべてのソートプロセスを完了した.

/**
* shellSort
* @author liebert
* @param int arr[]      
* @param int len     
*/
void shellSort(int arr[], int len)
{
	int i, j, dk, temp;
	
	//   
	for (dk = len / 2; dk > 0; dk /=2) {
		//     
		for (i = dk; i < len; i++) {
			temp = arr[i];
			j = i - dk;
			while (j >= 0 && temp < arr[j]) {
				arr[j+dk] = arr[j];
				j -= dk;
			}
			arr[j+dk] = temp;
		}
	}
}

7.ヒープソート
スタックは配列であり、論理的には近似的な完全二叉木であり、ツリー上の各ノードは配列内の要素に対応し、配列のインデックスはツリー内のノードのシーケンス番号として使用される.シーケンス番号iのノードの場合、左リーフノードは2 i、右リーフノードは奇数2 i+1、親ノードはi/2である.
スタック・ソートの基本的な考え方は、次のとおりです.
①初期配列R[1..n]を最初の無秩序領域である大きなルートスタックとする.
②さらにキーワード最大のレコードR[1](すなわちスタックトップ)と無秩序領域の最後のレコードR[n]を交換ことにより、新たな無秩序領域R[1..n-1]と秩序領域R[n]とが得られ、R[1..n-1]を満たす.keys≤R[n].key;
③交換後の新たなルートR[1]はスタックの性質に反する可能性があるので、現在の無秩序領域R[1..n-1]をスタックに調整する.そして、R[1.n-1]におけるキーワードが最も大きいレコードR[1]とその区間の最後のレコードR[n-1]とを再び交換ことにより、新たな無秩序領域R[1.n-2]と秩序領域R[n-1.n]とが得られ、関係R[1.n-2]を満たす.keys≤R[n-1..n].keys,同様にR[1..n-2]をスタックに調整する.

void swap(int *a, int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
/**
* heapAdjust
* @description    
* @author liebert
* @param int arr[]      
* @param int len     
* @param int index       
*/
void heapAdjust(int arr[], int len, int index)
{
	int left  = index*2+1; //        
	int right = index*2+2; //        
	int large = index; //       

	if (left < len && arr[large] < arr[left]) {
		large = left;
	}
 	if (right < len && arr[large] < arr[right]) {
		large = right;
	}
	if (large != index){
		swap(&arr[index], &arr[large]);
		heapAdjust(arr, len, large);
	}
}

/**
* heapBuild
* @description    
* @author liebert
* @param int arr[]      
* @param int len     
*/
void heapBuild(int arr[], int len)
{
	int i;
	
	for (i = len / 2 - 1; i >= 0 ; i--) {
		heapAdjust(arr, len, i);
	}
}

/**
* heapSort
* @author liebert
* @param int arr[]      
* @param int len     
*/
void heapSort(int arr[], int len)
{
	int i ;
	//   
	heapBuild(arr, len);
	//   
	for (i = len; i > 1; i--) {
		swap(&arr[0], &arr[i]);
		//    
		heapAdjust(arr, i-1, 0);
	}
	
}

ぶんせき
(1)時間複雑度O(N)のソートアルゴリズム:
時間複雑度O(N)のアルゴリズムには主に基数ソート,カウントソートがあるが,この2つのアルゴリズムはいずれも配列中の要素の範囲を事前に知り,バケツの数を確立する必要があるため,この問題を解決するのに適していない.
(2)時間的複雑度O(N 2)に対するソートアルゴリズム:
時間複雑度O(N 2)は、主に泡立ち、選択、挿入があり、テーマに関連する基本秩序があり、挿入ソートが第一選択であり、各要素の移動距離はKを超えないため、挿入ソートでは各要素が前に移動する距離もKを超えないため、その際に挿入ソートの時間複雑度はO(N*K)であるため、挿入ソートは考慮に入れることができる.
(3)時間複雑度O(N*logN)のソートアルゴリズム
時間複雑度O(N*logN)は,配列要素の初期順序とは無関係であるため,主に高速並べ替え,集計並べ替え,スタック並べ替えが用いられる.一方,スタックソートは,最良,最悪,平均で時間複雑度がO(N*logn)であった.