홀짝 정렬
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
홀짝 정렬은 거품 정렬과 유사한 비교 정렬 알고리즘으로, 리스트의 홀수 번째 원소와 짝수 번째 원소를 비교하고 교환하는 단계와 짝수 번째 원소와 홀수 번째 원소를 비교하고 교환하는 단계를 반복한다. 이 과정을 리스트가 정렬될 때까지 반복하며, 병렬 프로세서 환경에서 효율적으로 구현될 수 있다. 홀짝 정렬은 O(n2)의 시간 복잡도를 갖는다.
더 읽어볼만한 페이지
- 안정 정렬 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다. - 안정 정렬 - 삽입 정렬
삽입 정렬은 미정렬 부분의 원소를 정렬된 부분의 올바른 위치에 삽입하여 정렬을 완성하는 간단하고 효율적인 알고리즘이지만, 데이터 세트가 클수록 성능이 저하되어 이를 개선하기 위한 변형 알고리즘이 존재한다. - 비교 정렬 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다. - 비교 정렬 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다. - 정렬 알고리즘 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다. - 정렬 알고리즘 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
| 홀짝 정렬 | |
|---|---|
| 알고리즘 정보 | |
 | |
| 분류 | 정렬 알고리즘 |
| 자료 구조 | 배열 |
| 시간 복잡도 | O(n^2) |
| 최선의 시간 복잡도 | O(n) |
| 공간 복잡도 | O(1) |
| 최적화 여부 | 아니오 |
2. 알고리즘
홀짝 정렬은 리스트의 홀수 번째 원소와 짝수 번째 원소를 비교 및 교환하는 단계와 짝수 번째 원소와 홀수 번째 원소를 비교 및 교환하는 단계를 번갈아 가며 반복하는 알고리즘이다. 이 알고리즘은 거품 정렬과 유사하게 단순하지만, 효율성은 떨어진다. 0부터 시작하는 인덱스를 사용한다고 가정한다.
2. 1. 기본 알고리즘
거품 정렬처럼 이 알고리즘은 단순하지만 매우 효율적이지 않다. 0부터 시작하는 인덱스를 기준으로 설명하면 다음과 같다.홀짝 정렬은 홀수 번째와 그 다음 짝수 번째를 묶음(묶음 1)으로 하여 비교/교환한 후, 짝수 번째와 그 다음 홀수 번째를 묶음(묶음 2)으로 하여 비교/교환하는 것을 반복하는 알고리즘이다.
- 묶음 1: (1번째와 2번째 비교, 3번째와 4번째 비교, 5번째와 6번째 비교, …)
- 묶음 2: (2번째와 3번째 비교, 4번째와 5번째 비교, 6번째와 7번째 비교, …)
이 과정을 정렬이 완료될 때까지 반복한다.
다음은 C 언어와 JavaScript로 구현한 예시이다. C 언어의 경우, 첫 번째 위치를 나타내는 첨자는 0이다.
function oddEvenSort(list) {
function swap(list, i, j) {
var temp = list[i];
list[i] = list[j];
list[j] = temp;
}
var sorted = false;
while (!sorted) {
sorted = true;
for (var i = 1; i < list.length - 1; i += 2) {
if (list[i] > list[i + 1]) {
swap(list, i, i + 1);
sorted = false;
}
}
for (var i = 0; i < list.length - 1; i += 2) {
if (list[i] > list[i + 1]) {
swap(list, i, i + 1);
sorted = false;
}
}
}
}
```c
double data[N] = {값1, 값2, 값3, ..., 값N} ;
bool changed ;
do
{
changed = false ;
for (int i=0 ; i
if (data[i] > data[i+1])
{
swap (&data[i], &data[i+1]) ;
changed = true ;
}
for (int i=1 ; i
if (data[i] > data[i+1])
{
swap (&data[i], &data[i+1]) ;
changed = true ;
}
}
while (changed) ;
2. 2. 알고리즘의 정확성 증명
홀짝 정렬 알고리즘은 0-1 원리에 따라 번의 패스(pass) 안에 데이터가 올바르게 정렬됨이 증명되었다.[6]이 증명은 비교-교환 연산만 포함하고 있으며 무지(oblivious)하기 때문에(비교-교환 연산의 순서는 데이터에 의존하지 않음), 크누스의 0-1 정렬 원리[7][8]에 따라, 각 데이터가 0 또는 1일 때의 정확성을 확인하는 것으로 충분하다. 1이 개 있다고 가정한다.
가장 오른쪽에 있는 1은 짝수 또는 홀수 위치에 있을 수 있으므로, 첫 번째 홀짝 패스에서는 이동하지 않을 수 있다. 그러나 첫 번째 홀짝 패스 이후, 가장 오른쪽에 있는 1은 짝수 위치에 있게 된다. 따라서 나머지 모든 패스에서 오른쪽으로 이동하게 된다. 가장 오른쪽에 있는 1은 보다 크거나 같은 위치에서 시작하므로, 최대 단계만큼 이동해야 한다. 따라서 가장 오른쪽에 있는 1을 올바른 위치로 이동하는 데 최대 번의 패스가 걸린다.
두 번째로 오른쪽에 있는 1을 고려해 보자. 두 번의 패스 후, 그 오른쪽에 있는 1은 적어도 한 단계 오른쪽으로 이동했을 것이다. 따라서 나머지 모든 패스에서, 두 번째로 오른쪽에 있는 1을 가장 오른쪽에 있는 1로 볼 수 있다. 두 번째로 오른쪽에 있는 1은 적어도 위치에서 시작하여 최대 위치로 이동해야 하므로, 최대 단계만큼 이동해야 한다. 최대 2번의 패스 후, 가장 오른쪽에 있는 1은 이미 이동했을 것이므로 두 번째로 오른쪽에 있는 1의 오른쪽에 있는 항목은 0이 된다. 따라서 처음 두 번의 패스 이후의 모든 패스에서, 두 번째로 오른쪽에 있는 1은 오른쪽으로 이동할 것이다. 따라서 두 번째로 오른쪽에 있는 1을 올바른 위치로 이동하는 데 최대 번의 패스가 걸린다.
이와 같은 방식으로, 귀납법에 의해 번째로 오른쪽에 있는 1은 최대 번의 패스만에 올바른 위치로 이동함을 보일 수 있다. 이므로, 번째로 오른쪽에 있는 1은 최대 번의 패스만에 올바른 위치로 이동한다. 따라서 목록은 번의 패스만에 올바르게 정렬된다.
각 패스는 단계를 가지므로, 이 알고리즘은 의 복잡성을 가진다.
3. 프로세서 배열 정렬
홀짝 정렬은 병렬 프로세서 환경에서 효율적으로 작동하도록 설계될 수 있다. 각 프로세서는 하나의 값을 담당하고, 인접 프로세서와 비교-교환 작업을 수행한다. 이 알고리즘은 1972년 하버만에 의해 처음 제시되었으며 이러한 프로세서에서 효율적인 것으로 나타났다.[2]
프로세서당 여러 항목을 처리하는 경우에도 홀짝 정렬은 효율적으로 확장될 수 있다. 각 프로세서는 먼저 자체 하위 목록을 정렬한 후, 인접 프로세서와 병합 작업을 수행한다. 이때 인접 프로세서와의 비교-교환 작업은 홀수-짝수 순서와 짝수-홀수 순서를 번갈아 가며 수행된다.[3]
3. 1. 배처 홀짝 병합 정렬 (Batcher Odd-even Mergesort)
배처 홀짝 병합 정렬은 홀짝 정렬을 기반으로 한 더 효율적인 알고리즘으로, 비교-교환 연산과 완벽 셔플 연산을 사용한다.[4] 배처의 방법은 장거리 연결을 갖는 병렬 프로세서에서 효율적이다.[5]4. 복잡도
5. 동작 예시
와 같은 표기는 비교되는 데이터 쌍을 나타낸다.
초기 데이터:
| 시간 | 교환 전 상태 | 쌍 | 교환 횟수 | 교환 후 상태 |
|---|---|---|---|---|
| 1 | 쌍 1 | 3 | ||
| 2 | 쌍 2 | 3 | ||
| 3 | 쌍 1 | 4 | ||
| 4 | 쌍 2 | 2 | ||
| 5 | 쌍 1 | 3 | ||
| 6 | 쌍 2 | 3 | ||
| 7 | 쌍 1 | 3 | ||
| 8 | 쌍 2 | 1 |
총 교환 횟수는 (버블 정렬)와 같다.
참조
[1]
웹사이트
Array Sorting
http://homepages.ihu[...]
2011-08-03
[2]
간행물
"Parallel Neighbor Sort (or the Glory of the Induction Principle)," CMU Computer Science Report
[3]
논문
Parallel Sorting Algorithms
https://books.google[...]
Academic Press
[4]
서적
Algorithms in Java, Parts 1-4
https://books.google[...]
Addison-Wesley Professional
[5]
서적
Encyclopedia of Computer Science and Technology: Supplement 14
https://books.google[...]
CRC Press
[6]
웹사이트
Five Lectures on CA
http://liinwww.ira.u[...]
2017-07-30
[7]
웹사이트
The 0-1-principle
http://www.inf.hs-fl[...]
2017-07-30
[8]
웹사이트
Distributed Sorting
http://www.net.t-lab[...]
2017-07-30
[9]
웹인용
Array Sorting
http://homepages.ihu[...]
2011-08-03
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com