홀짝 정렬(Odd-Even sort)

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

 

① 홀짝 정렬은 배열을 오름차순으로 정렬하는 병렬 정렬 알고리즘이다.

  ㉠ 홀짝 정렬은 브릭 정렬(brick sort)이라고도 알려져있다.

② 홀짝 정렬은 분할 정복 전략(devide-and-conquer strategy)를 사용하는 병합 정렬을 기반으로 한다.

③ 홀짝 정렬의 기본 원리는 다음과 같다.

  ㉠ 홀수 인덱스의 인접한 두 요소를 비교한다.

  ㉡ 순서가 잘못되어 있으면 순서를 바꾼다.

  ㉢ 짝수 인덱스에 대해서 ㉠ ㉡을 시행한다.

  ㉣ 정렬이 완료될 때까지 ㉠ ㉡ ㉢를 반복한다.

 

1회 시행

2회 시행

3회 시행

4회 시행

 

④ 홀짝 정렬의 의사 코드(psuedo code)는 다음과 같다.

 

	function oddEvenSort(array)
	n = length(array)
	sorted = false
	while not sorted do
	sorted = true
	for i = 1 to n-1 step 2 do
	if array[i] > array[i+1] then
	swap(array[i], array[i+1])
	sorted = false
	end if
	end for
	for i = 0 to n-1 step 2 do
	if array[i] > array[i+1] then
	swap(array[i], array[i+1])
	sorted = false
	end if
	end for
	end while
	return array
	end function

view raw psuedocode.txt hosted with ❤ by GitHub

⑤ 비교적 구현이 매우 간단하지만, 최악의 경우 시간 복잡도가 O(n^2)인 정렬이다.

⑥ 홀짝 정렬의 구현 코드는 다음과 같다.

 

	#include<iostream>
	#include<vector>
	#include<algorithm>
	#include<chrono>
	using namespace std;
	using namespace chrono;
	vector<int>randomVector(int n) {
	vector<int> vec(n);
	srand(time(NULL));
	for (int i = 0; i < n; i++) {
	vec[i] = rand() % 100;
	}
	return vec;
	}
	void oddEvenSort(int n) {
	vector<int>vec = randomVector(n);
	bool sorted = false;
	auto tik = chrono::system_clock::now();
	while (!sorted) {
	sorted = true;
	for (int i = 1; i < n - 1; i += 2) {
	if (vec[i] > vec[i + 1]) {
	swap(vec[i], vec[i + 1]);
	sorted = false;
	}
	}
	for (int i = 0; i < n - 1; i += 2) {
	if (vec[i] > vec[i + 1]) {
	swap(vec[i], vec[i + 1]);
	sorted = false;
	}
	}
	}
	auto tok = chrono::system_clock::now();
	cout << endl;
	cout << n << ":" << chrono::duration_cast<microseconds>(tok - tik).count() << "ms \n";
	}
	int main() {
	oddEvenSort(10);
	oddEvenSort(100);
	oddEvenSort(1000);
	oddEvenSort(10000);
	return 0;
	}

view raw example.cpp hosted with ❤ by GitHub

	10:0ms
	100:7ms
	1000:322ms
	10000:28839ms

view raw terminal hosted with ❤ by GitHub

⑦ 홀짝 정렬은 병렬화가 가능하다.

  ㉠ 여러 개의 하위 스택으로 분할한 뒤 여러 개의 프로세서 또는 쓰레드로 홀짝 정렬을 수행할 수 있다.

 

홀짝 병합 정렬