교차 정렬(Alternate Sort)이란?
교차 정렬은 정수 배열의 요소들을 최댓값과 최솟값이 번갈아 배치되는 형태로 재정렬하는 기법입니다. 구체적인 배치 규칙은 다음과 같습니다.
- 첫 번째 요소 : 배열의 최댓값
- 두 번째 요소 : 배열의 최솟값
- 세 번째 요소 : 두 번째로 작은 값
- 네 번째 요소 : 두 번째로 큰 값
- 이후에도 같은 패턴이 끝까지 반복됩니다.
예시를 통해 개념을 더 쉽게 이해해 보겠습니다.
입력 : 4 1 8 2 9 3 7 출력 : 9 1 8 2 7 3 4 설명 : 배열을 오름차순으로 정렬하면 1 2 3 4 7 8 9가 됩니다. 이제 원하는 형태, 즉 교차 정렬 형태로 재배치해 보겠습니다. 배열에서 가장 큰 요소인 9를 먼저 출력하고, 그다음 가장 작은 요소인 1, 이어서 8, 2, 7, 3, 4 순서로 배치하면 됩니다.
개념을 이해했다면 이제 문제를 해결할 방법을 고민해 볼 차례입니다. 가장 직관적인 접근 방식은 배열을 먼저 오름차순으로 정렬한 뒤, 정렬된 배열의 마지막 요소와 첫 번째 요소를 번갈아 출력하는 것입니다. 이 아이디어를 바탕으로 알고리즘을 만들어 보겠습니다.
알고리즘
1단계 : 배열을 정렬한다. 2단계 : 시작부터 순회할 포인터와 끝부터 순회할 포인터, 두 개를 생성한다. 3단계 : 두 포인터가 가리키는 값을 번갈아 출력하면서 포인터를 이동시킨다.
구현 예제
#include <iostream>
using namespace std;
void alternateSort(int arr[], int n);
void swap(int *xp, int *yp);
void selectionSort(int arr[], int n);
int main(){
int arr[] = { 4,1,8,2,9,3,7};
int n = sizeof(arr)/sizeof(arr[0]);
alternateSort(arr, n);
return 0;
}
void alternateSort(int arr[], int n){
selectionSort(arr, n);
int i = 0, j = n-1;
while (i < j) {
cout << arr[j--] << " ";
cout << arr[i++] << " ";
}
if (n % 2 != 0)
cout << arr[i];
}
void swap(int *xp, int *yp){
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n){
int i, j, min_idx;
for (i = 0; i < n-1; i++){
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]);
}
}
코드 동작 원리
위 코드는 세 부분으로 나누어 볼 수 있습니다.
- selectionSort() : 선택 정렬을 이용해 배열을 오름차순으로 정렬합니다. 매 단계마다 남은 요소 중 최솟값을 찾아 앞쪽 위치와 교환하는 방식입니다.
- alternateSort() : 정렬된 배열의 끝 인덱스(
j)와 시작 인덱스(i)에 포인터를 두고, 뒤쪽 값(큰 값)과 앞쪽 값(작은 값)을 번갈아 출력합니다. - 홀수 길이 처리 : 배열의 길이가 홀수라면 두 포인터가 만나는 가운데 요소가 출력되지 않으므로, 마지막에
arr[i]를 한 번 더 출력해 누락을 방지합니다.
선택 정렬을 사용하기 때문에 이 구현의 시간 복잡도는 O(n²)입니다. 배열의 크기가 클 경우 std::sort() 같은 O(n log n) 정렬로 대체하면 성능을 크게 개선할 수 있습니다.
실행 결과
9 1 8 2 7 3 4