[Algorithm] 선택정렬과 삽입정렬

다음 알고리즘은 정수 배열을 정렬하는 알고리즘이다.

선택정렬

선택 정렬은 모든 i에 대해 A[i....N-1]에서 가장 작은 원소를 찾은 뒤, 이것을 A[i]에 넣는것을 반복한다. 즉

가 된다. 따라서 시간복잡도는  이며 빅오는  가 된다.

삽입정렬

삽입 정렬에서는 A[0....i]까지는 정렬이 되어 있다고 본다. 즉 i = 4 라면

3

5

7

8

9(i)

13

1

2

A[3]과 비교 했을 때 A[4] > A[3] 이기 때문에 while()문을 빠져 나오게 된다. 하지만 i = 6 이라면 while()문으

로 들어가서 swap()을 실시하는데 이 경우 A[4]...A[3]........A[0] 까지 다 실시하게 된다.

즉 삽입 정렬은 정수 배열이 이미 정렬이 되어 있다면 번 실시한다. 하지만 최악의 경우(역순 정렬)일 경우

는번 실행하게 된다.

그럼 선택 정렬과 삽입 정렬을 비교해 본자.

선택정렬은 어떤 정수 배열이 오던지 번 실행한다. 

삽입 정렬은 최소 번 최대 번 실행한다. 

그렇기 때문에 일반적으로 정렬을 할 때는 삽입 정렬이 더 빠르다.