기본적인 정렬 알고리즘

Selection Sort

• 각 루프마다
  • 최대 원소를 찾는다
  • 최대 원소와 맨 오른쪽 원소를 교환한다
  • 맨 오른쪽 원소를 제외한다
• 하나의 원소만 남을 때까지 위의 루프를 반복한다

selectionSort(A[], n) {
    for last <- n downto  2 {  // 1
        A[1...last] 중 가장 큰 수 A[k]를 찾는다  // 2
        A[k]와 A[last]의 값을 교환 // 3
    }
}

수행시간:

• 1의 for 루프는 n-1번 반복
• 2에서 가장 큰 수를 찾기 위한 비교횟수: n-1, n-2, ..., 2, 1
• 3의 교환은 상수시간 작업

시간복잡도 T(n)=(n-1)+(n-2)+(n-3)+...+2+1 = O(n^2)

Bubble Sort

bubbleSort(A[], n) {
    for last <-n downto 2 {  //1
        for i <-1 to last-1  //2
            if (A[i]>A[i+1]) then  A[i] <-> A[i+1]; 교환 //3
}

수행시간:

• 1의 for 루프는 n-1번 반복
• 2의 for 루프는 각각 n-1, n-2, ..., 2, 1번 반복
• 3의 교환은 상수시간 작업

시간복잡도 T(n)=(n-1)+(n-2)+(n-3)+...+2+1 = O(n^2)

Insertion Sort

insertionSort(A[], n) {
    for i <- 2 to n {  // 1
        A[1...i]의 적당한 자리에 A[i]를 삽압한다  //2
    }
}

수행시간:

• 1의 for 루프는 n-1번 반복
• 2의 삽입은 최악의 경우 i-1번 비교

최악의 경우 시작복잡도: T(n)=(n-1)+(n-2)+(n-3)+...+2+1 = O(n^2)