3강. 정렬문제

[ 목차 ]

1. 정렬문제

2. 선택정렬 알고리즘

3. 선택정렬 정확성 증명

4. 선택정렬 성능분석

 

1. 정렬문제

1) 컴퓨터가 이해할 수 있게 입력과 출력으로 명확하게 정의해주어야 함

2) 입력 : n개의 숫자들의 배열

3) 출력 : 입력받은 숫자들을 점점 커지거나(오름차순) 작아지는(내림차순) 순서로 재배열

 

2. 선택정렬 알고리즘

1) 현재 상황에서 가장 작거나 큰 숫자를 선택하여 재배치하는 아이디어

2) 최소값 선택 정렬 : 가장 작은 값을 선택(오름차순)

  1] 정렬되지 않은 숫자 중 가장 작은 숫자를 선택

  2] 선택한 숫자를 정렬되지 않은 숫자들 중 첫 번째 숫자와 자리를 바꾸면 선택된 숫자는 정렬된 것

  3] 모든 숫자를 옮길 때까지 1-2과정을 반복

3) 최대값 선택 정렬 : 가장 큰 값을 선택(내림차순)

 

3. 선택정렬 정확성 증명

1) 수학적 귀납법을 사용

2) n번째 선택한 숫자가 n번째로 작은(or 큰) 숫자인지 증명

 

4. 선택정렬 성능분석

1) 비교횟수 : n(n-1)/2

2) 시간복잡도 :  세타(n제곱)

3) 항상 모든 숫자에 대해 다 비교해야 하기 때문에 최선, 최악의 경우는 존재하지 않음