728x90
목차
1.정렬(Sort)
2.선택 정렬(Selection Sort)
3.버블 정렬(Bubble Sort)
4.삽입 정렬(Insertion Sort)
5.쉘 정렬(Shell Sort)
6.힙 정렬(Heap Sort)
7.이진 병합 정렬(Binary Merge Sort)
8.버킷 정렬(Bucket Sort)
9.퀵 정렬(Quick Sort)1.정렬(Sort)
1-1. 정렬의 개념
* 여러 자료를 일정한 규칙에 따라 키 값을 기준으로 나열하는 방법
* 정렬은 오름차순과 내림차순으로 구분되며 레코드 단위로 정렬된다
- 오름차순: 키 값이 작은것부터 큰것 순으로 나열
- 내림차순: 키 값이 큰것부터 작은것 순으로 나열
* 정렬은 키 값의 비교 방식에 따라 다양한 종류로 나뉜다1-2. 정렬의 종류와 시간 복잡도
| 정렬 | 평균 | 최악 |
|---|---|---|
| 삽입정렬 | O(n²) | O(n²) |
| 버블정렬 | O(n²) | O(n²) |
| 선택정렬 | O(n²) | O(n²) |
| 쉘 정렬 | O(n¹⋅⁵) | O(n¹⋅⁵) |
| 힙 정렬 | O(nlogn) | O(nlogn) |
| 이진병합정렬 | O(nlogn) | O(nlogn) |
| 퀵 정렬 | O(nlogn) | O(n²) |
| 버킷정렬 | O(dn) | O(dn) |
2.선택 정렬(Selection Sort)
2-1. 선택 정렬의 개념
* 첫 위치와 나머지 위치들을 각각 비교하여 데이터를 교환하는 방식
* 모든 비교 및 교환을 통해 첫 데이터 위치에 가장 작은 값이 존재
* 정렬이 끝난 위치를 제외한 첫 위치와 나머지 위치들로 정렬작업을 반복한다
* 작업을 반복할때 마다 비교 시작 위치가 증가한다
* 시간 복잡도는 O(n²)3.버블 정렬(Bubble Sort)
3-1. 버블 정렬의 개념
* 각 위치와 인접한 오른쪽 값과 비교하여 데이터를 교환하는 방식
* 모든 비교와 교환을 통해 마지막 위치에 가장 큰값이 존재하게 한다
* 정렬이 끝난 마지막 위치를 제외한 위치들의 데이터로 정렬 작업을 반복
* 작업을 반복할때 마다 비교 종료위치가 감소한다
* 시간 복잡도는 O(n²)4.삽입 정렬(Insertion Sort)
4-1. 삽입 정렬의 개념
* 데이터들의 위치를 기준으로 좌측에 이미 정렬된 요소들과 비교하여 자신의 위치를 찾아 삽입하는 방식
* 좌측 데이터와 비교하며 진행되어야 하므로 두번째 위치부터 비교를 시작한다
* 삽입되는 위치 이후의 데이터들은 우측으로 밀려난다
* 시간 복잡도는 O(n²)5.쉘 정렬(Shell Sort)
5-1. 쉘 정렬의 개념
* 삽입 정렬을 보완한 알고리즘
* 많은 양의 데이터의 간격을 정하고 간격을 점차 줄이면서 삽입정렬 진행
* 간격만큼 여러개의 부분 리스트를 생성하여 각각 삽입 정렬한다
* 부분 리스트를 점점 줄여서 최종적으로 하나의 리스트로 만들어 완성6.힙 정렬(Heap Sort)
6-1. 힙 정렬의 개념
* 데이터 리스트를 완전이진트리 형태로 만들어 정렬하는 방법
* 하위노드그룹 으로부터 상위노드그룹 으로 점차 확대하는 방법
* 자식노드가 부모노드보다 큰 경우 자료를 교환
* 최대값, 최소값을 비교적 쉽게 추출할수 있는 방식7.이진 병합 정렬(Binary Merge Sort)
7-1. 이진 병합 정렬의 개념
* 두개의 키 값을 한 쌍으로 하여 정렬하고, 정렬된 두 그룹을 다시 한쌍으로 하여 정렬하는 방식
* 각각의 그룹의 요소를 비교하여 작은 값을 우선 병합하여 정렬8.버킷 정렬(Bucket Sort)
8-1. 버킷 정렬의 개념
* 정렬되지 않은 원소들의 범위를 균등하게 나눈 여러 버킷을 생성하여 정렬하는 방법
* 각각의 버킷은 스탟을 이용하여 정렬한다9.퀵 정렬(Quick Sort)
9-1. 퀵 정렬의 개념
* 키 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정 반복하는 정렬
* 많은 자료 이동 없애고, 하나의 파일을 부분적으로 나누어 가며 정렬참고자료 : 이기적 환상콤비 정보처리기사
728x90
