티스토리 뷰
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다.
* 정렬(Sort)
- 순서없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순(Ascending)이나 큰 것부터 작은 것 순서의 내림차순(Descending)으로 재배열하는 것
- 키(Key) : 자료를 정렬하는데 사용하는 기준이 되는 특정 값
* 선택 정렬(Selection Sort)
- 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬 (가장 작거나 큰 원소를 찾음)
* 선택 정렬의 장/단점
[장점]
- 알고리즘이 단순함
- 정렬을 위한 비교 횟수는 많지만, 교환 횟수가 버블 정렬에 비해 적어 많은 교환이 일어나야 하는 자료에서 효율적임
- 다른 메모리 공간 필요하지 않음
[단점]
- 시간복잡도 = O(n^2)
* 버블 정렬(Bubble Sort)
- 인접한 두개의 원소를 비교하여 자리를 교환하는 방식
* 버블 정렬의 장/단점
[장점]
- 알고리즘이 단순함
- 다른 메모리 공간 필요하지 않음
[단점]
- 시간복잡도 = O(n^2)
* 퀵 정렬(Quick Sort)
- 피봇(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
- 평균 속도 O(N*logN)을 자랑하는 매우 빠른 정렬 알고리즘
- 분할 ➡ 정복 ➡ 결합 순서로 진행
- 분할(Divide) : 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할함
- 정복(Conquer) : 부분집합의 원소들 중에서 기준값보다 작은 원소들은 왼쪽 부분집합으로, 기준값보다 큰 원소들은 오른쪽 부분집합으로 정렬함
* 퀵 정렬의 장/단점
[장점]
- 속도가 빠름
- 추가 메모리 공간이 필요하지 않음
[단점]
- 최악의 경우 시간 복잡도 = O(N^2)
ex. 정렬되어 있는 경우를 또 정렬하는 경우
* 삽입 정렬(Insertion Sort)
- 자료 배열의 모든 요소를 앞에서부터 차례대로 비교하면서 자리를 교환하는 방법
* 삽입정렬 장/단점
[장점]
- 알고리즘이 단순함
- 추가적인 메모리 소비가 적음
- 거의 정렬된 경우에는 매우 효율적이고, 최선일 경우 의 시간복잡도를 가짐
- 안정 정렬이 가능함
[단점]
- 비교적 많은 수들의 이동을 포함하며 비교할 수가 많고 크기가 클 경우에 적합하지 않음
- 최악의 경우 의 시간복잡도를 가짐
- 성능 편차가 매우 큼
* 셸 정렬(Shell Sort)
- ‘Donald L. Shell’이라는 사람이 제안한 방법으로, 삽입정렬을 보완한 알고리즘
- 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법
- 전체 원소에 대해 삽입 정렬을 수행하는 것보다 부분집합으로 나누어 정렬하면 비교 연산과 교환 연산 횟수를 줄일 수 있음
[1회전]
- 처음 간격을 (정렬할 값의 수 = 10)/2 = 5로 하고, 다섯 번째 요소를 추출해서 부분 리스트를 만듦
- 만들어진 5개의 부분 리스트를 삽입 정렬로 정렬함
[2회전]
- 다음 간격은 = (5/2:짝수)+1 = 3으로 하고, 1회전 정렬한 리스트에서 세 번째 요소를 추출해서 부분 리스트를 만듦
- 만들어진 3개의 부분 리스트를 삽입 정렬로 정렬함
[3회전]
- 다음 간격은 = (3/2) = 1으로 하고, 간격 k가 1이므로 마지막으로 정렬을 수행함
- 만들어진 1개의 부분 리스트를 삽입 정렬로 정렬함
* 셸 정렬 장/단점
[장점]
- 교환되는 요소들이 삽입 정렬보다는 최종 위치에 있을 가능성이 높아짐
- 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 된다면, 기본적으로 삽입 정렬을 수행하는 것이지만 삽입 정렬보다 더욱 빠르게 수행됨
- 알고리즘이 간단하여 프로그램으로 쉽게 구현할 수 있음
[단점]
- 최악의 경우 의 시간복잡도를 가짐 (평균 = O(N^1.5), 최악의 경우 = O(N^2))
* 병합 정렬(Merge Sort)
- 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법
- 2-way 병합 : 2개의 정렬된 자료의 집합을 결합하여 하나의 잡합으로 만드는 병합 방법 -> 병합 정렬에서 사용
(1) 분할(Divide) : 입력 자료를 같은 크기의 부분집합 2개로 분할함
(2) 정복(Conquer) : 부분집합의 원소들을 정렬함, 부분집합의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용함
(3) 결합(Combine) : 정렬된 부분집합들을 하나의 집합으로 통합함
* 병합 정렬 장/단점
[장점]
- 안정 정렬(Stable Sort)로, 입력 데이터가 무엇이든 시간복잡도 = O(nlogn)
- 항상 동일한 시간이 소요되어 어떤 경우에도 좋은 성능을 보장함 (데이터 분포 영향 덜 받음)
[단점]
- 제자리 정렬이 아니기 때문에 별도의 추가적인 메모리가 필요함
- 데이터가 많은 경우에는 이동 횟수가 많으므로 큰 시간적 낭비를 초래함
* 기수 정렬(Radix Sort)
- 원소의 키를 표현하는 값의 기수(Radix)만큼의 버킷이 필요하고, 키값의 자릿수만큼 기수 정렬을 반복함
* 기수 정렬 장/단점
[장점]
- 키의 길이 가 작다면 의 시간으로 정렬을 할 수 있기 때문에 굉장히 빠른 속도로 정렬을 할 수 있음
- 카운팅 정렬과 같이 비교 연산 없이 정렬을 수행 할 수 있음
[단점]
- 추가적으로 버킷을 사용하기 때문에 데이터 크기에 비례한 메모리가 필요함
- 버킷의 종류 (2진수,10진수,알파벳) 등이 고정적이지 않음
- 정렬 방법의 특수성 때문에 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용하기 힘듦
* 힙 정렬(Heap Sort)
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
- 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조
* 최대 힙 정렬 예시
1) 먼저 이진 탐색트리를 만들며 최대 힙을 구현함
2) 그 후 최대 힙의 최대 루트 노드를 배열의 마지막 자리 원소로 고정하고 트리에서 마지막 노드와 자리를 바꿈
3) 이 과정을 모든 자리가 고정될 때까지 최대 힙을 만들고 루트 노드를 배열의 마지막 자리 원소로 만드는 과정을 반복하며 정렬을 수행함
* 트리 정렬(Tree Sort)
- 이진 탐색 트리를 이용하여 정렬하는 방법
- 힙 정렬과 비슷해 보이지만 정렬될 자료의 각 원소 크기에 따라 부모 노드의 왼쪽 자식/오른쪽 자식이 되는지에 따라 다름
[참고]
- 단순하지만 비효율적인 방법 : 삽입 정렬, 선택 정렬, 버블 정렬
- 복잡하지만 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬
'개인공부 > 자료구조|알고리즘' 카테고리의 다른 글
| [자료구조] 검색(Search) 개념 (0) | 2023.11.22 |
|---|---|
| [자료구조] 그래프(Graph) (0) | 2023.11.22 |
| [자료구조] 트리(Tree) (0) | 2023.11.20 |
| [자료구조] 큐(Queue) (0) | 2023.11.20 |
| [자료구조] 스택(Stack) (0) | 2023.11.20 |