1. 버블 정렬(Bubble Sort)
- 자신과 인접한 데이터와 비교하여 정렬하는 방식
예) 10 1 2 60 7 9
1. 10 <> 1 비교 후 치환 ( 1 10 2 60 7 9)
2. 10 <> 2 비교 후 치환 ( 1 2 10 60 7 9)
- 즉 자신과 가장 인접한 데이터를 지속적으로 비교하면서 정렬해가는 방식
ㆍ버블 정렬의 비교 횟수 = (n-1)+(n-2)+(n-3)+...+(n-(n-2))+(n-(n-1)) = (n-1)+(n-2)+(n-3)+...+3+2+1 = n(n-1)/2
-> 즉 O(n^2) 로 n의 값이 증가하면 실행 시간은 기하급수적으로 증가 하게 된다.
2. 삽입 정렬(Insertion Sort)
- 정렬할 새로운 데이터를 뽑아 적당한 새 위치에 삽입하는 알고리즘
예) 3 4 6 2 8 1
1. 3 과 4를 뽑은 후 비교 (4가 더 크므로 변동이 없음)
2. 4 와 6을 뽑은 후 비교 (6이 크므로 변동없음)
3. 6 과 2를 뽑은 후 비교 (6이 더 크므로 2를 뽑아 3앞에 삽입)
- 2 3 4 6 8 1
4. 6 과 8을 뽑은 후 비교 (8이 더 크므로 변동이 없음)
5. 8 과 1을 뽑은 후 비교 (8이 더 크므로 1을 뽑아 2앞에 삽입)
- 1 2 3 4 5 8
- 시간 복잡도는 최선의 경우 O(n)이며 최악은 O(n^2)를 보이며 평균 시간 봅잡도는 O(n^2)
3. 퀵 정렬(Quick Sort)
- 퀵 정렬은 분할 정복에 근거 하며 퀵 정렬은 다른 정렬과 다르게 기준값을 하나 택하고 순회를 돌면서 기준값보다 작은 데이터는 좌측, 기준값보다 큰 값은 위측으로 분할하고 다시 퀵 정렬을 정렬합니다.
- 간단히 말하면 맨처음 기준값을 택해서 기준값보다 작으면 모두 왼쪽, 기준값보다 크면 오른쪽으로 배치한 후 정렬되어 있는 좌측을 또다시 기준값을 기준으로 배치 하는 식이다.
- 퀵 정렬의 평균 복잡도 : O(nLogn)
- 최악의 경우 : O(n2)
'Programming 기본기 > 알고리즘' 카테고리의 다른 글
| 탐색 알고리즘 (0) | 2016.09.10 |
|---|