1. 선택 정렬

문제 : 1, 10, 5, 8, 7, 6, 4, 3, 2, 9의 숫자가 있다. 이를 오름차순으로 정렬해라.

1. 배열 0번째부터 시작

2. 0~10까지의 숫자 중 가장 작은 수를 탐색 후 그 위치를 index에 기억(선택, 탐색)

3. 가장 앞에 가장 작은 수 array[index]를 넣는다.(swap)

#include<stdio.h>
#include<stdlib.h>

void main() {
	int i, j, min, index, temp;
	int array[10] = { 1,10,5,8,7,6,4,3,2,9 };
	for (i = 0; i < 10; i++) {
		//탐색
        min = 9999;
		for (j = i; j < 10; j++) {
			if (min > array[j]) {
				min = array[j];
				index = j;
			}
		}
		//스왑
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}
    	//출력
	for (i = 0; i < 10; i++) {
		printf("%d", array[i]);
	}

	return 0;
}

 

시간 복잡도

10개 수를 탐색 시

첫번째 탐색 10번 루프

두번째 정렬 9

...

...

마지막 탐색 1번

즉, 10 + 9 + ... + 2 + 1

n/2 * (n + 1) -> n*n의 시간 복잡도를 가진다.

--시간 복잡도 계산 시 나누기나 더하기는 무시한다.

 

<본 글은 유튜버 동빈나님의 강의를 듣고 작성되었습니다.>