알고리즘 - 정렬 알고리즘

알고리즘 - 정렬 알고리즘

| 정렬 알고리즘 종류

Bubble sort

Insertion sort

Selection sort

• simple, slow

Quick sort

Merge sort

Heap sort

• Fast

Radix sort

• O(N)

| 기본적 정렬 알고리즘

1. Selection sort

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)

• 최선의 경우나, 최악의 경우나, 평균의 경우 시간복잡도가 모두 똑같으므로 따질 필요가 없다.

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)+…+2+1 = O(n^2)

3.Insertion sort

• k-1 개의 데이터가 정렬되어 있는상태에서 k번째 데이터를 어디에 insert 하는지 파악하는 k개 데이터정렬 알고리즘

insertionSort(A[], n) -> 배열 A[1,,n]을 정렬한다.
{
  for i <- 2 to n{--------------------1
    A[1..i]의 적당한 자리에 A[i]를 삽입한다.
  }
}

• 실행시간 :

  1.의 for 루프는 n-1번 반복

  2의 삽입은 최악의 경우 i-1번 반복

• 최악의 경우: T(n)=(n-1)+(n-2)+…+2+1 = O(n^2)