[알고리즘] 3-1. 기본 정렬

 

버블, 삽입, 선택 정렬	간단하지만, 느리다
퀵, 병합, 힙 정렬	빠르다
기수 정렬 (radix)	O(N)

 

정렬

1. 최대 원소 찾기

2. 최대 원소와 맨 오른쪽 원소와 교환

3. 맨 오른쪽 원소 제외

4. 하나의 원소만 남을 때까지 반복

 

//선택정렬

selectionSort (A[], n)
{
 for last <- n downto 2
 A[1...last] 중 가장 큰 수 A[K] 찾기
 A[K] <-> A[last]; A[k]와 A[last] 값 교환
 }
}

 

//버블정렬

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

 

//삽입 정렬

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