Algorithm Study (정렬)
이전내용 링크
3. 정렬
데이터를 정렬 하는 방법이다.
비교정렬, 제자리 정렬, 온라인 정렬 로 구분된다.
- 비교정렬 : 원소들을 정렬할 때 원소들의 순서에만 의존하는 알고리즘들을 일컫는다.
- 제자리 정렬 : 원소의 개수에 비해 충분히 무시할 만한 저장공간을 더 사용하는 정렬 알고리즘을 의미한다.
- 온라인 정렬 : 모든 원소들이 처음부터 주어지지 않고 차례대로 들어오는 경우도 처리할 수 있는 정렬 알고리즘을 의미한다.
아래에는 여러 정렬 기법에 대해 위키백과를 참조하여 설명한다. 설명은 오름차순을 기준으로 한다.
3-1. 삽입 정렬 O(n^2)
3-2. 선택 정렬 O(n^2)
- 주어진 배열 중에 최소값을 찾는다.
- 최소값을 첫번째 요소의 값과 바꾼다.
- 처음 요소를 제외하고 나머지 배열에 대해 1~3 을 반복한다.
- 비교할 요소가 없다면 정렬 완료
메모리가 제한적인 경우 사용시 성능 상의 이점이 있다.
3-3. 거품 정렬 O(n^2)
- 첫번째 요소와 두번째 요소를 비교하여 정렬한다.
- 두번째 요소화 세번째 요소를 비교하여 정렬한다.
- 위와 같은 방식으로 n-1번째 요소와 n번째 요소를 비교하여 정렬한다.
- 마지막 요소를 제외하고 첫번째 요소부터 1~4를 다시 진행한다.
- 비교할 요소가 없다면 정렬 완료
- 각 루프마다 맨 마지막 요소는 가장 큰 값이다.
3-4. 합병 정렬 O(nlogn)
합병 정렬, 병합 정렬(merge sort) 라고 부른다.
비교 기반 정렬 알고리즘으로 일반적인 방법으로 구현 시 안정 정렬에 속한다.
- 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다.
- 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
- 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
- 결합(combine) : 두 부분 리스트를 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시 배열에 저장된다.
- 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.
3-5. 셸 정렬 / 평균 O(n^1.5), 최악 O(n^2)
삽입 정렬이 어느정도 정렬된 배열에서 효율적인 점에서 착안한 정렬 기법
- 배열을 일정 간격(gap)으로 나눠 부분 리스트를 만든다.
- 각 부분 리스트를 삽입 정렬을 이용하여 정렬
- 모든 부분 리스트를 정렬 한 후 전체 리스트를 저 작은 간격으로 나눠 알고리즘 반복
- 간격이 1이 될때까지 진행
전체 데이터의 개수 N이 존재 할때 일반적으로 간격을 N/2로 초기화 하여 설명하지만 N/3 +1 이 더 빠르다고 한다(위키백과)
3-6. 힙 정렬 O(nlogn)
- N개의 노드에 대한 완전 이진트리 구성
- 최대 힙을 구성한다(최대 힙은 부모 노드가 자식노드보다 큰 트리를 말한다)
- 요소를 힙에서 꺼내 배열의 맨 뒤부터 저장한다.
3-7. 퀵 정렬 / 평균 O(nlogn), 최악 O(n^2)
비교 정렬에 속한다.
대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계 되어있다
(메모리 참조가 지역화 되어 있어 CPU 캐시의 히트율이 높기 때문)
알고리즘 설계에서 n^2 시간이 걸리지 않도록 할 수 있다.
일반 적인 경우 다른 O(nlogn) 알고리즘에 비해 훨씬 빠르게 동작한다.
같은 값을 가지는 원소의 경우 순서가 바뀔 수 있어서 불안정 정렬에 속한다.
- 배열의 가운데서 하나의 원소를 고른다. 이를 피벗이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 요소들이 피벗 뒤에는 피벗보다 큰 요소들이 오도록 리스트를 둘로 나눈다.
- 분할된 두개의 배열에 대해 재귀적으로 과정을 반복한다.
- 크기가 0 또는 1이 될때까지 반복한다.
-출처 링크(위키백과) -