선택 정렬 알고리즘

삽입정렬 알고리즘은 배열을 n번 원소를 기준으로 순차적으로 비교를 한다.

그러다 그리고 가장 작은 원소의 인덱스를 저장하고 n번 원소와 교환을 한다.

이 작업을 반복하다 보면 정렬이 되는 알고리즘이다.

 

0 회전 : [ 5, 6, 3, 1 ]  ◀ 초기 배열

1 회전 : [ 1, 6, 3, 5 ]

2 회전 : [ 1, 3, 6, 5 ]

4 회전 : [ 1, 2, 5, 6 ]  ◀ 정렬 완료

 

n 개의 원소가 있으면 다음 노드와의 비교를 n - 1번 하고 최솟값을 찾은 다음 교환 

이 작업을 n - 1번 반복한다.

 

 

Code

#include <stdio.h>

void selectSort(int arr[], int length);

int main() {
	int arr[] = { 5, 7, 1, 2, 8, 9, 10 };

	// 실행
	selectSort(arr, 7);

	// 결과 출력
	printf("정렬된 결과: [");

	for (int i = 0; i < 7; i++) {
		printf("%d ", arr[i]);
		printf(" ");
	}

	printf("]");
	return 0;
}

void selectSort(int arr[], int length) {
	int temp, i, j, minIndex;

	for (i = 0; i < length -1; i++) {
		minIndex = i;

		for (j = i + 1; j < length; j++) {
			if (arr[minIndex] > arr[j]) {
				minIndex = j;
			}
		}

		temp = arr[minIndex];
		arr[minIndex] = arr[i];
		arr[i] = temp;
	}
}

  

선택정렬은 버블정렬과 마찬가지로 시간복잡도 O(n^2)을 가지고 있어 효율적인 알고리즘은 아니다..

같은 O(n^2)이지만 버블정렬보다 조금 더 성능이 좋은 정렬방법이다.