정렬 알고리즘

• simple, slow
  • Bublle sort
  • Insertion sort
  • Selection sort
• fast
  • Quick sort
  • Merge sort
  • Heap sort
• O(N)
  • Radix sort

    Selection sort

• 데이터를 오름차순으로 정렬
• 가장 큰 값을 찾아서 제일 뒤쪽의 수와 교환한다.
• 그리고 잊어버린다.
• 위 과정을 마지막 2개가 남을때 까지 반복
• 하나의 값이 남으면 종료.
• 스도코드

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

• 실행시간
  • 1의 for 루프는 n-1번 반복
  • 2에서 가장 큰 수를 찾기 위한 비교횟수 : n-1, n-2, … , 2, 1
  • 3의 교환은 상수시간 작업
• 시간복잡도 T(n)=(n-1)+(n-2)+ … + 2 + 1 = O(n^2)
  • 모든 경우의 시간복잡도가 n^2이다. (최악, 최선, 평균)

Bubble Sort

• 실행시간: (n-1)+(n-2)+ … + 2 + 1 = O(n^2)
• 첫번째 값을 다음값과 비교해서 크면 자리이동을 하고 작으면 비교한 값으로 계속 비교 해나간다.
• 스도코드

    bubbleSort(A[], n) {    // 배열 A[1 ... 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)+ … + 2 + 1 = O(n^2)

삽입 정렬(Insertion Sort)

• 앞에서부터 비교를 하게 되면 모든 데이터를 한번씩 봐야한다.
• 뒤에서 부터 비교한다면 뒤로 한칸씩 물리면서 비교한다.(그럼 자기보다 작은 앞의 데이터는 볼 필요가 없다.)
• 스도코드

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

  • A[1 … i-1]은 이미 정렬되어있고 i번째에 숫자를 집어넣는다.
  • 수행시간:
    • 1의 for 루프는 n-1번 반복
    • 2의 삽입은 최악의 경우 i-1번 비교
  • 최악의 경우 : 시간복잡도 T(n)=(n-1)+(n-2)+ … + 2 + 1 = O(n^2)
  • 최선의 경우 Bubble이나 Selection보다 빠를수 있다.
  • 하지만 앞쪽에 정렬이 안되어있는 경우 자기보다 작은 수를 만나면 어떻게 되는가?