[C++][구현] 순차,선택 정렬 (Sequence ,Selection Sort)

⭐ Sequence, Selection Sort

 

오름차순 정렬을 한다고 하였을 때, 가장 작은 수를 찾아서 교환해주는 정렬입니다.

 

첫번째, for문은 정렬 할 자리수 k를 정해주고 (오름차순이면 k가 0부터 length까지)

 

그 다음 두번째 for문 부터 k + 1 부터 length까지 nums[k]와 비교를 해가며 작으면 스왑해줍니다.

 

#include <iostream>
using namespace std;
// O(n^2) unstable


void sequenceSort(int nums[], int length) {
	for (int i = 0; i < length; i++) {
		for (int j = i + 1; j < length; j++) {
			if (nums[i] > nums[j]) {  // Compare 조건
				// Swap
				int tmp = nums[i];
				nums[i] = nums[j];
				nums[j] = tmp;
			}	
		}
	}
}

 

즉 0번째 인덱스부터 length인덱스까지 가장 최솟값들을 자리수별로 비교해가며 스왑해주는 정렬입니다.

 

시간복잡도는 O(n^2) 이고, UnStable한 정렬입니다.