ツールバーの

単純なソートアルゴリズム

泡の位置合わせ

バブルソートは、隣接する2つのデータを比較することによってソートされる.

#include <cstdio>
void BubbleSort(int arr[], int n){
    int temp;
    for(int i = 0; i < n - 1; i++){
    	for(int j = 0; j < (n - i) -1; j++){
            if(arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main(){
    int arr[4] = {3, 2, 4, 1};
    BubbleSort(arr, sizeof(arr) / sizeof(int));
    ....
}

バブルソート性能評価

O(n^2)の性能を持つ.
Nestude砲口では,砲口を1つ回すごとに最後に整列した状態になるので−i演算を行う.

ソートの選択

選択ソートは、ソート順に基づいて選択、移動、ソートを行うアルゴリズムです.改良された選択並べ替えは,空格子点を用いたアルゴリズムを用いた.交換はコアです.

#include <cstdio>

void SelSort(int arr[], int n) {
	int maxIdx;
	int temp;

	for (int i = 0; i < n - 1; i++) {
		maxIdx = i;

		for (int j = i + 1; j < n; j++) { // 최솟값 탐색
			if (arr[j] < arr[maxIdx])
				maxIdx = j;
		}

		temp = arr[i];
		arr[i] = arr[maxIdx];
		arr[maxIdx] = temp;
	}
}
int main() {
	int arr[4] = { 3,4,2,1 };
	SelSort(arr, sizeof(arr) / sizeof(int));
	for (int i = 0; i < 4; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

このアルゴリズムの性能はO(n^2)である.
データ移動の回数から見ると、Bubbleソートは最悪の場合もデータ移動が継続し、選択ソートはデータ移動のコードが砲口の外側にあるため、最悪の場合も最良の場合もO(n)であり、Bubbleソートは最悪の場合はO(n^2)である.最良の場合、データは移動したことがありません.
両アルゴリズムは比較演算においてO(n^2)の性能を有する.
最悪の場合、ソートを選択する上でバブルソートよりもパフォーマンスが向上することが期待できますが、バブルソートは最良の場合にデータ移動が一度も発生せず、データが常に最悪ではないことを考慮すると、両者の優劣を区別することは意味がありません.

整列挿入

ソートの挿入は、ソート対象を2つの部分に分け、ソートされていない部分のデータをソート部分の特定の位置に挿入してソートするアルゴリズムです.
挿入位置を探すプロセスと、挿入のために空間を空けるプロセスを区別する必要はありません.並べ替えが完了した領域の次のデータは、次の並べ替えオブジェクトであるため、交換しながら前にドラッグします.

#include <cstdio>

void InserSort(int arr[], int n) {
	int insData;
	int i, j;
	for (i = 1; i < n; i++) {
		insData = arr[i];
		for (j = i - 1; 0 <= j; j--) {
			if (insData < arr[j]) // 비교대상 한 칸 뒤로 밀기
				arr[j + 1] = arr[j];
			else break; // 삽입 위치 찾았으니 탈출
		}
		arr[j + 1] = insData; // 찾은 위치에 정렬대상 삽입
	}
}

int main(void) {
	int arr[5] = { 5,3,2,4,1 };
	int i;
	InserSort(arr, sizeof(arr) / sizeof(int));
	for (i = 0; i < 5; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

挿入ソートは、ほとんどのソート対象オブジェクトがソートされている場合に非常に速く実行されます.ソートが完全である場合、breakに沿ってデータは移動しません.ただし、最悪の場合を考慮するとbreakは実行されないため、for文の繰り返し回数で比較演算と移動演算が行われる.
従ってO(n^2)の性能を有する.

複雑だが効率的なソートアルゴリズム

連結ソート

これは分けて治める方法で問題を解決するアルゴリズムである.
実際のソートは、分割をマージする過程で行われ、1つのデータしか残っていないまで分割されます.2つのデータだけが残っていてもソートする必要があるので、1つのデータだけが残っていればソートする必要はありません.

#include <cstdio>
#include <cstdlib>
void MergeTwoArea(int arr[], int left, int mid, int right) {
	int fIdx = left;
	int rIdx = mid + 1;
	int i;
    
    // 병합 한 결과를 담을 배열 sortArr의 동적 할당
	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));
	int sIdx = left;
    
    // 병합 할 두 영역의 데이터들을 비교하여, 정렬 순서대로 옮겨 담는다.
	while (fIdx <= mid && rIdx <= right) {
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];
		sIdx++;
	}
    
    // 배열의 앞 부분이 모두 정렬된 상태로 sortArr에 옮겨지면 남은 뒷 부분을 그대로 옮긴다.
	if (fIdx > mid) {
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else {
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
    
	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];
	free(sortArr);
}
void MergeSort(int arr[], int left, int right) {
	int mid;
	if (left < right) {
		mid = (left + right) / 2;
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);
		MergeTwoArea(arr, left, mid, right);
	}
}
int main(void) {
	int arr[7] = { 3,2,4,1,7,6,5 };
	int i;
	MergeSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
	for (i = 0; i < 7; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

MergeTwoAreaの実現が鍵です.
集計ソートのパフォーマンスは、MergeTwoArea関数に基づいて計算する必要があります.比較演算と移動演算は、実際にソートされた対応する関数の周りで行われるからです.

ソート・オブジェクトのデータ数がnの場合、マージ・ステップごとに最大n回の比較演算が行われます.
比較演算の観点からO(nlog(2)n)である.
移動の観点から、一時配列にデータを統合する過程で、
一時的なアレイに格納されているすべてのデータを移動するには、1回だけです.
比較演算と比較して、演算量は比較演算の2倍である.だから、ヴィクトオは同じです.

クイックソート

一番左のデータを高速ソートに必要なピボットとして使用します.
lowは軸心以外で最も左側の点を指し、highは軸心以外で最も右側の点を指す.
lowは軸心より大きい値に右に移動し、highは軸心より小さい値に左に移動します.
移動終了後、その2つのデータの位置を交換します.
交換終了後、元の場所で移動を再開します.
lowとhighの位置が交差すると,軸心とhighが指すデータが互いに交換される.
これがクイックソートのコアです.上記の修行がすべて終わると、軸心は自分の位置に戻ります.すなわち、軸心より小さいものは軸心の左側にあり、軸心より大きいものは軸心の右側にある.
最初のピボットが位置すると、左領域と右領域がマージソートのように、上記の手順に従います.
left>rightの場合、ソート可能なオブジェクトはなくなり、クイックソートが終了します.

#include <cstdio>

void Swap(int arr[], int idx1, int idx2) {
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

int Partition(int arr[], int left, int right) {
	int pivot = arr[left];
	int low = left + 1;
	int high = right;

	while (low <= high) {
		while (arr[low] <= pivot && low <= right) low++;
		while (pivot <= arr[high] && (left + 1) <= high) high--;
		if (low <= high) Swap(arr, low, high);
	}
	Swap(arr, left, high); // 피벗과 high가 가리키는 대상 교환
	return high; // 옮겨진 피벗의 위치정보 반환
}

void QuickSort(int arr[], int left, int right) {
	if (left <= right) {
		int pivot = Partition(arr, left, right); // 둘로 나눠서
		QuickSort(arr, left, pivot - 1);
		QuickSort(arr, pivot + 1, right);
	}
}

int main() {
	int arr[7] = { 3,2,4,1,7,6,5 };
	int len = sizeof(arr) / sizeof(int);
	QuickSort(arr, 0, len - 1);
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
	return 0;
}

比較演算はデータの個数nに相当し,データはO(nlog(2)n)に分裂する.
最悪の場合、n^2は可視であるが、中間に近い軸心を設定する演算を加えると、結果は常に最適に近づき、データの移動は明らかにデータの比較より少ない.余分なメモリスペースは必要ないので、同じbigoを持つ他のソートアルゴリズムでは、平均的に最も速いソート速度を示すアルゴリズムです.