알고리즘...9

선택 정렬

모든 정렬 알고리즘 중 가장 간단한 알고리즘으로 배열 A [1... n]에서 가장 큰 원소를 찾아 A [n]과 자리를 바꾸고 [1... n-1]에 대해 이전 과정을 반복하여 정렬을 마무리한다.

 

선택 정렬 알고리즘

SelectionSort(A[], n)
{
    for last ← n downto 2
    {
        A[1...last] 중 가장 큰 수 A[k]를 찾는다.
        A[k] ↔ A[last]
    }
}

 

이 알고리즘의 수행 시간은 for 루프에 비례하는데 이 루프는 n ~ 2까지 반복하므로 총 비교 회수는 n(n-1)/2 이므로 Θ(n²)이 된다.

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘