정렬은 데이터들을 특정 기준에 맞게 오름차순, 또는 내림차순으로 나열하는 것을 말한다.
정렬은 많은 방법들이 있는데, 접하면서 정리되는데로 기록해나갈려고 한다.
정렬은 데이터들을 특정 기준에 맞게 오름차순, 또는 내림차순으로 나열하는 것을 말한다.
정렬은 많은 방법들이 있는데, 접하면서 정리되는데로 기록해나갈려고 한다.
시간 복잡도 O(n2)
선택정렬(Selection Sort)
가장 큰 것을 선택해서 기준 범위의 앞과 스왑(swap)하는 방식(내림차순정렬)
가장 작은 것을 선택해서 기준 범위의 앞과 스왑(swap)하는 방식(오름차순정렬)
예를 들어
6 2 9 8 3 4 7 이 있다면, 이 것을 선택정렬을 사용하여 오름차순으로 정렬해보겠다.
(1) 6 2 9 8 3 4 7 => 2 6 9 8 3 4 7
(2) 2 6 9 8 3 4 7 => 2 3 9 8 6 4 7
(3) 2 3 9 8 6 4 7 => 2 3 4 8 6 9 7
(4) 2 3 4 8 6 9 7 => 2 3 4 6 8 9 7
(5) 2 3 4 6 8 9 7 => 2 3 4 6 7 9 8
(6) 2 3 4 6 7 9 8 => 2 3 4 6 7 8 9
이러한 과정을 거쳐서 정렬이 완성된다.
선택정렬의 특징이 하나 있다. 배열의 원소를 최소로 바꾸면서 정렬하는 방법이다.
삽입정렬(Insertion sort)
삽입정렬과 선택정렬이 헷갈렷는데, 삽입정렬에 대해서는 확실히 알게 되었다.
한 마디로 말하자면 현재의 인덱스에 있는 값이 위치해야 할 자리로 가는 것을 말한다.
예를들어
6 2 9 8 3 4 7 이 있다면
6 2 9 8 3 4 7
2 6 9 8 3 4 7
2 6 9 8 3 4 7
2 6 8 9 3 4 7
2 3 6 8 9 4 7
2 3 4 6 8 9 7
2 3 4 6 7 8 9
이런식으로 범위를 늘려나가면서 해당 숫자의 자리를 찾아주는 코드이다.
버블정렬(Bubble Sort)
문자 그대로 마치 공기방울이 수면 위로 떠오르듯 가장 큰 레코드가 한칸씩 한칸씩 오른쪽으로 떠올라오는 정렬이다.
6 2 9 8 3 4 7
2 6 9 8 3 4 7
2 6 8 9 3 4 7
2 6 8 3 9 4 7
2 6 8 3 4 9 7
2 6 8 3 4 7 9
2 6 8 3 4 7 9
2 6 8 3 4 7 9
2 6 8 3 4 7 9
2 6 3 4 8 7 9
2 6 3 4 7 8 9
2 6 3 4 7 8 9
2 6 3 4 7 8 9
2 3 6 4 7 8 9
2 3 4 6 7 8 9
2 3 4 6 7 8 9
2 3 4 6 7 8 9
2 3 4 6 7 8 9
2 3 4 6 7 8 9
2 3 4 6 7 8 9
2 3 4 6 7 8 9
2 3 4 6 7 8 9
이런과정을 거쳐서 정렬이 된다.
'자료구조' 카테고리의 다른 글
| 트리(Tree) (0) | 2015.07.01 |
|---|---|
| 위상정렬 (0) | 2015.07.01 |
| 자료구조 - 리스트(List) (0) | 2015.06.16 |
| 트리 순회_동적할당소스코드 (0) | 2015.03.31 |
| 트리의 순회 (1) | 2015.03.25 |
