PhysicalMouse (토론 | 기여) 잔글편집 요약 없음 |
잔글 (봇: 자동으로 텍스트 교체 (-\[\[([^]]*)_([^]]*)\]\] +\1 \2)) |
||
(사용자 5명의 중간 판 21개는 보이지 않습니다) | |||
1번째 줄: | 1번째 줄: | ||
[[ | 자료들을 정리하기 위한 [[알고리즘]]이다. 여러 가지 알고리즘이 있지만, 시간 복잡도가 가장 작은 알고리즘을 쓰는 것이 좋다. 정렬할 데이터가 얼마 없으면 상관이 없으나, 정렬할 데이터가 많아질 수록 처리 성능보다는 알고리즘이 더 중요해진다. | ||
예시로, 1초에 100만 회의 작업을 할 수 있는 [[컴퓨터]]1이, n개를 정렬하는데 n<sup>2</sup>의 시간이 소요되는 알고리즘을 이용해서 정렬을 한다고 하고, (상대적으로 성능이 떨어지는) 1초에 1만 회의 작업을 할 수 있는 컴퓨터2는, n개를 정렬하는데 nlog<sub>2</sub>n의 시간이 소요되는 알고리즘을 이용해서 정렬을 한다고 하자. | |||
{|class="wikitable" | |||
| | |||
|colspan="2"| 처리 소요시간 | |||
|- | |||
|n | |||
|컴퓨터1 (n<sup>2</sup>) | |||
|컴퓨터2 (nlog<sub>2</sub>n) | |||
|- | |||
|100 | |||
|10ms | |||
|66.4ms | |||
|- | |||
|1,000 | |||
|1000ms | |||
|997ms | |||
|- | |||
|10,000 | |||
|1분 40초 | |||
|13.3초 | |||
|- | |||
|100,000 | |||
|2시간 46분 40초 | |||
|2분 46초 | |||
|- | |||
|1,000,000 | |||
|11일 13시간 46분 40초 | |||
|33분 13초 | |||
|} | |||
컴퓨터1이 컴퓨터 2보다 처리속도가 100배나 빠르지만, 데이터가 커지면 커질수록 더 느린 결과를 보여준다. | |||
시간 복잡도의 상한값은 Big-O 표기법으로 표시되고 (가장 느릴 경우), 그 크기는 O(1) < O(n) < O(nlogn) < O(n<sup>2</sup>) < 2<sup>O(n)</sup> < O(n!) 순이며, 가능한 시간복잡도가 작은 알고리즘을 쓰는 것이 좋다. | |||
== 종류 == | == 종류 == | ||
* Bubble sort | {{유튜브|kPRA0W1kECg}} | ||
* [[거품 정렬]](Bubble sort): 가장 단순한 알고리즘이다. 이중 루프문으로 구현하며, 단순한 만큼 효율은 좋지 않다. 한 루프 내에서 가장 큰 값이나 작은 값이 발견되면 뒤로 보낸다. 즉시 뒤에 삽입되는게 아니라 처음부터 끝까지 훑고 지나가면서 비교문을 돌린다. 시간복잡도는 O(n<sup>2</sup>). 여러 정렬 알고리즘 중에 효율이 매우 나쁜 편이라서 교육용으로만 배우는 알고리즘이다. | |||
* Insertion sort | ** [[칵테일 정렬]], 양방향 거품 정렬(bidirectional bubble sort) | ||
* Quick sort | **: [[파일:Sorting shaker sort anim.gif]]<br/>작은 수를 앞으로 보냈다 큰 수를 뒤로 보냈다 하면서 정렬한다. | ||
* Merge sort | ** [[빗질 정렬]](comb sort) | ||
**: [[파일:Comb sort demo.gif]]<br/> 오름차순 정렬에서 배열 끝 근처의 작은 값들은 '거북이'라고 하는데 거품 정렬에서 거북이로 인해 속도가 느려지는 현상을 개선한다. | |||
* [[삽입 정렬]](Insertion sort): 배열의 첫 부분부터 뒤에 있는 값을 하나씩 앞으로 삽입하는 정렬. 이미 정렬된 구간을 탐색해서 알맞는 구간을 찾아 삽입한다. | |||
*: 예제 | |||
*: <syntaxhighlight lang="c++"> | |||
void insertionSort(int a[], int n) { //a = 배열 n = 배열의 크기 | |||
for (int i = 1; i <= n; i++) { // 2번째 부터 n까지 | |||
int locate = i-1; // 첫 번째 | |||
int newitem = a[i]; // 2번째 값 (끼워넣어지는 수) | |||
while (locate >= 0 && newitem < a[locate]) { | |||
a[locate + 1] = a[locate], locate--; // 끼워 넣을 자리를 만든다. | |||
} | |||
a[locate+1] = newitem; // 끼워넣기 | |||
} | |||
}</syntaxhighlight> | |||
*: [{1, 3, 5, 6, 7} << 4, 8, 2] -> [{1, 3, 4, 5, 6, 7} << 8, 2] -> [{1, 3, 4, 5, 6, 7, 8} << 2] -> [{1, 2, 3, 4, 5, 6, 7, 8}] | |||
* [[선택 정렬]](Selection sort): 가장 큰 수 또는 가장 작은 수를 찾아서 A의 x번째 값(x는 루프문에서 하나씩 커지거나 작아진다.)과 그 자리의 값을 교환하여 정렬한다. 이때 A는 이미 정렬된 부분이다. | |||
*: [[파일:Selection-Sort-Animation.gif]] | |||
* [[퀵 정렬]](Quick sort) | |||
* [[병합 정렬]](Merge sort) | |||
* [[힙 정렬]](Heap Sort): 힙이라는 자료구조를 이용해서 정렬을 수행한다. | |||
더 많은 정렬 알고리즘은 [[wikipedia:Template:Sorting]] 참고. | |||
{{유튜브|8MsTNqK3o_w|캡션=<del>알고리즘 대장정</del>}} | |||
== 관련 문서 == | |||
* [[자료 구조]] | |||
{{각주}} | |||
[[분류:알고리즘]] |
2022년 8월 30일 (화) 16:39 기준 최신판
자료들을 정리하기 위한 알고리즘이다. 여러 가지 알고리즘이 있지만, 시간 복잡도가 가장 작은 알고리즘을 쓰는 것이 좋다. 정렬할 데이터가 얼마 없으면 상관이 없으나, 정렬할 데이터가 많아질 수록 처리 성능보다는 알고리즘이 더 중요해진다.
예시로, 1초에 100만 회의 작업을 할 수 있는 컴퓨터1이, n개를 정렬하는데 n2의 시간이 소요되는 알고리즘을 이용해서 정렬을 한다고 하고, (상대적으로 성능이 떨어지는) 1초에 1만 회의 작업을 할 수 있는 컴퓨터2는, n개를 정렬하는데 nlog2n의 시간이 소요되는 알고리즘을 이용해서 정렬을 한다고 하자.
처리 소요시간 | ||
n | 컴퓨터1 (n2) | 컴퓨터2 (nlog2n) |
100 | 10ms | 66.4ms |
1,000 | 1000ms | 997ms |
10,000 | 1분 40초 | 13.3초 |
100,000 | 2시간 46분 40초 | 2분 46초 |
1,000,000 | 11일 13시간 46분 40초 | 33분 13초 |
컴퓨터1이 컴퓨터 2보다 처리속도가 100배나 빠르지만, 데이터가 커지면 커질수록 더 느린 결과를 보여준다.
시간 복잡도의 상한값은 Big-O 표기법으로 표시되고 (가장 느릴 경우), 그 크기는 O(1) < O(n) < O(nlogn) < O(n2) < 2O(n) < O(n!) 순이며, 가능한 시간복잡도가 작은 알고리즘을 쓰는 것이 좋다.
종류[편집 | 원본 편집]
- 거품 정렬(Bubble sort): 가장 단순한 알고리즘이다. 이중 루프문으로 구현하며, 단순한 만큼 효율은 좋지 않다. 한 루프 내에서 가장 큰 값이나 작은 값이 발견되면 뒤로 보낸다. 즉시 뒤에 삽입되는게 아니라 처음부터 끝까지 훑고 지나가면서 비교문을 돌린다. 시간복잡도는 O(n2). 여러 정렬 알고리즘 중에 효율이 매우 나쁜 편이라서 교육용으로만 배우는 알고리즘이다.
- 삽입 정렬(Insertion sort): 배열의 첫 부분부터 뒤에 있는 값을 하나씩 앞으로 삽입하는 정렬. 이미 정렬된 구간을 탐색해서 알맞는 구간을 찾아 삽입한다.
- 예제
void insertionSort(int a[], int n) { //a = 배열 n = 배열의 크기 for (int i = 1; i <= n; i++) { // 2번째 부터 n까지 int locate = i-1; // 첫 번째 int newitem = a[i]; // 2번째 값 (끼워넣어지는 수) while (locate >= 0 && newitem < a[locate]) { a[locate + 1] = a[locate], locate--; // 끼워 넣을 자리를 만든다. } a[locate+1] = newitem; // 끼워넣기 } }
- [{1, 3, 5, 6, 7} << 4, 8, 2] -> [{1, 3, 4, 5, 6, 7} << 8, 2] -> [{1, 3, 4, 5, 6, 7, 8} << 2] -> [{1, 2, 3, 4, 5, 6, 7, 8}]
- 선택 정렬(Selection sort): 가장 큰 수 또는 가장 작은 수를 찾아서 A의 x번째 값(x는 루프문에서 하나씩 커지거나 작아진다.)과 그 자리의 값을 교환하여 정렬한다. 이때 A는 이미 정렬된 부분이다.
- 퀵 정렬(Quick sort)
- 병합 정렬(Merge sort)
- 힙 정렬(Heap Sort): 힙이라는 자료구조를 이용해서 정렬을 수행한다.
더 많은 정렬 알고리즘은 wikipedia:Template:Sorting 참고.
알고리즘 대장정