컴퓨터 알고리즘 초급 (정렬문제)

정렬문제(sorting problem)

 

알고리즘은 4단계에 걸쳐서 설명 할 수있다.

문제정의, 알고리즘 설명, 정확성증명, 성능분석

 

 - 입력 (input)

    n개의 숫자들의 배열 (a1, a2, a3 ......... an)

 

 - 출력 (output)

   입력된 숫자위 배열이 오름차순 조건을 만족하도록 재 배열하는것

 

 

선택정렬 알고리즘

선택정렬(Selection sort)

 

 - 선택하여 정렬하는 알고리즘 

 - 최소값 선택 정렬 (Min-Selection sort)

    가장 작은 값을 선택(오름차순)

 

오름차순 선택정렬

 

 - 최대값 선택 정렬 (Max-Selection sort)

    가장 큰 값을 선택(내림차순)

 

 

 - 정확성 증명

   수학적 귀납법을 이용

   i번쨰 선택한 숫자가 i번째로 작은(혹은 큰) 숫자인지를 증명

 

 - 성능분석

    최선 최악의 경우 수행시간 n^2

    최선 최악의 경우 공간 n