기본적 정렬

1. Selection Sort

1) 개념

각 루프마다 

- 최대의 원소를 찾는다. 

- 최대의 원소와 맨 오른쪽 원소를 교환한다. 

- 맨 오른쪽 원소를 제외한다. 

하나의 원소만 남을 때 까지 위의 루프를 반복한다.

[출처: 권오흠, 영리한 프로그래밍을 위한 알고리즘 강좌]

2) Pseudocode

selectionSort(A[ ], n){   ▷배열 A[1...n]을 정렬한다.

for last ← n downto  2 {        -------------------------------①

A[1...last] 중 가장 큰 수 A[k]를 찾는다     -----------------------②

A[k] ↔ A[last]  ▷ A[k]와 A[last]의 값을 교환    -------------------------③

}

}

3) 수행시간

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

②에서 가장 큰 수를 찾기 위한 비교횟수: n-1, n-2, ..., 2, 1

③의 교환은 상수시간 작업

4) 시간복잡도

2. Bubble Sort

1) 개념

두 인접한 원소를 검사하여 정렬하는 방법이다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

다른 숫자와 비교하여 제일 큰 수를 뒤로 보내는 작업은 Selection Sort와 비슷하다.

2) Pseudocode

bubbleSort(A[ ], n) { ▷배열 A[1...n]을 정렬한다.

for last ← n downto  2 {        -------------------------------①

for i ← 1 to last-1    -----------------------②

if(A[i]>A[i+1]) then A[i] ↔ A[i+1]  ▷ 교환 -------------------------③

}

}

3) 수행시간

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

②의 for 루프는 각각 n-1, n-2, ..., 2, 1번 반복

③의 교환은 상수시간 작업

4) 시간복잡도

3. Insertion Sort (삽입 정렬)

1) 개념

자료 배열의 모든 요소를 앞에서 부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

2) Pseudocode

insertionSort(A[ ], n){ ▷배열 A[1...n]을 정렬한다.

for i ← 1 to { -------------------------------① 

A[1...i]의 적당한 자리에 A[i]를 삽입한다. -------------------②

}

}

3) 수행시간

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

②의 삽입은 최악의 경우 i-1번 비교

4) 시간복잡도 - 최악의 경우