설명 출처 : Introduction to algorithms
code : https://github.com/EomTaeWook/Algorithm/blob/master/Algorithm/Sort/ColumnSort.cs
열 정렬(Column Sort) 알고리즘은 N개의 원소가 있는 직사각형 배열에서 동작한다.
배열은 r개의 행과 s개의 열을 갖고 있으며(그러므로 n = rs이다) 다음 세개의 제약 사항을 가진다.
- r은 짝수여야 한다.
- r은 s로 나누어져야 한다.
- r >= 2s2
열 정렬 n값에 관계 없이 여덟 번의 단계로 수행된다. 홀수 단계들은 모두 각 열을 개별적으로 정렬하는 단계다. 각 짝수 단계들은 정해준 순서가 있다. 다음 단계를 나열한다.
1.각 열을 정렬한다.
2.행렬을 전치한다. 하지만 결과의 여전히 r행과 s열을 가지도록 재구성해야한다. 다시 말해 왼쪽 끝 열을 우에서부터 r/s개의 행에 옮긴다. 순서대로 다음 열을 그 다음 r/s개의 행으로 옮긴다. 순서대로 계속한다.
3.각 열을 정렬한다.
4.2단계에서 수행했던 작업을 반대로 수행한다.
5.각 열을 정렬한다.
6.각 열의 위쪽 절반을 같은 열의 아래쪽 절반으로 만들고 각 열의 아래쪽 절반을 오른쪽으로 한 칸 옮겨 위쪽 절반으로 만든다. 위쪽 절반의 가장 왼쪽 열은 비워놓는다. 마지막 열의 아래쪽 절반은 새로 만들어지는 오른쪽 끝 열의 위쪽 절반이 되도록 하고 이 새열의 아래쪽 절반은 비워놓는다.
7.각 열을 정렬한다.
8.6단계에서 수행한 작업을 반대로 수행한다.
10 |
14 |
5 |
| 4 | 1 | 2 |
| 4 | 8 | 10 |
| 1 | 3 | 6 |
| 1 | 4 | 11 |
| 1 | 4 | 11 |
8 |
7 |
17 |
| 8 | 3 | 5 |
| 12 | 16 | 18 |
| 2 | 5 | 7 |
| 3 | 8 | 14 |
| 2 | 8 | 12 |
12 |
1 |
6 |
| 10 | 7 | 6 |
| 1 | 3 | 7 |
| 4 | 8 | 10 |
| 6 | 10 | 17 |
| 3 | 9 | 14 |
16 |
9 |
11 |
| 12 | 9 | 11 |
| 9 | 14 | 15 |
| 9 | 13 | 15 |
| 2 | 9 | 12 |
| 5 | 10 | 16 |
4 |
15 |
2 |
| 16 | 14 | 13 |
| 2 | 5 | 6 |
| 11 | 14 | 17 |
| 5 | 13 | 16 |
| 6 | 13 | 17 |
18 |
3 |
13 |
| 18 | 15 | 17 |
| 11 | 13 | 17 |
| 12 | 16 | 18 |
| 7 | 15 | 18 |
| 7 | 15 | 18 |
원본 1단계 2단계 3단계 4단계 5단계
5 |
10 |
16 |
|
4 |
10 |
16 |
| 1 | 7 | 13 |
||
6 |
13 |
17 |
|
5 |
11 |
17 |
| 2 | 8 | 14 |
||
7 |
15 |
18 |
|
6 |
12 |
18 |
| 3 | 9 | 15 |
||
1 | 4 |
11 |
|
|
1 |
7 |
13 |
|
| 4 | 10 | 16 |
2 |
8 |
12 |
|
|
2 |
8 |
14 |
|
| 5 | 11 | 17 |
3 |
9 |
14 |
|
|
3 |
9 |
15 |
|
| 6 | 12 | 18 |
6단계 7단계 8단계
행렬 전치와 절반 나누는 단계에 더 좋은 방법이 있을 것 같은데...
namespace Algorithm.Sort
{
class ColumnSort
{
public static int[,] Sort(int[,] unSortList)
{
Sort(ref unSortList);
Transposed(ref unSortList);
Sort(ref unSortList);
ReverseTransposed(ref unSortList);
Sort(ref unSortList);
int[,] transposedMatrix = null;
HalfDivideTransposed(ref unSortList, out transposedMatrix);
ReverseHalfDivideTransposed(ref transposedMatrix, out unSortList);
return unSortList;
}
private static void Sort(ref int[,] unSortList)
{
if (unSortList.Length > 0 && (unSortList.GetLength(0) & 1) == 0)
{
for (int i = 0; i < unSortList.GetLength(1); i++)
{
for (int ii = 0; ii < unSortList.GetLength(0); ii++)
{
for (int iii = 1; iii < unSortList.GetLength(0); iii++)
{
if (unSortList[iii, i] < unSortList[iii - 1, i])
{
Swap(ref unSortList, i, iii, i, iii - 1);
}
}
}
}
}
}
private static void Sort(ref int[,] unSortList, int begin, int end)
{
for (int i = begin; i < end; i++)
{
for(int ii=0; ii< unSortList.GetLength(0); ii++)
{
for (int iii = 1; iii < unSortList.GetLength(0); iii++)
{
if (unSortList[iii, i] < unSortList[iii - 1, i])
{
Swap(ref unSortList, i, iii, i, iii - 1);
}
}
}
}
}
private static void ReverseHalfDivideTransposed(ref int[,] unSortList, out int[,] sortList)
{
sortList = new int[unSortList.GetLength(0), unSortList.GetLength(1) - 1];
int row = unSortList.GetLength(0) / 2;
for (int i = 0; i < row; i++)
{
for (int ii = 0; ii < unSortList.GetLength(1)-1; ii++)
{
sortList[i, ii] = unSortList[i + row, ii];
}
for (int ii = 1; ii < unSortList.GetLength(1); ii++)
{
sortList[row + i, ii - 1] = unSortList[i, ii];
}
}
}
private static void HalfDivideTransposed(ref int[,] unSortList, out int[,] transposedMatrix)
{
transposedMatrix = new int[unSortList.GetLength(0), unSortList.GetLength(1) + 1];
int row = unSortList.GetLength(0) / 2;
for (int i = 0; i < row; i++)
{
for (int ii = 0; ii < unSortList.GetLength(1); ii++)
{
transposedMatrix[row + i, ii] = unSortList[i, ii];
}
for (int ii = 0; ii < unSortList.GetLength(1); ii++)
{
transposedMatrix[i, ii + 1] = unSortList[row + i, ii];
}
}
Sort(ref transposedMatrix, 1, transposedMatrix.GetLength(1) - 1);
}
private static void Transposed(ref int[,] unSortList)
{
var transposedMatrix = new int[unSortList.GetLength(0), unSortList.GetLength(1)];
int row = 0, col = 0;
for (int i = 0; i < unSortList.GetLength(0); i++)
{
if (i != 0 && (i & 1) == 0)
{
row = 0;
col++;
}
for (int ii = 0; ii < unSortList.GetLength(1); ii++)
{
transposedMatrix[i, ii] = unSortList[row++, col];
}
}
Array.Copy(transposedMatrix, unSortList, transposedMatrix.Length);
}
private static void ReverseTransposed(ref int[,] unSortList)
{
var transposedMatrix = new int[unSortList.GetLength(0), unSortList.GetLength(1)];
int row = 0, col = 0;
for (int i = 0; i < unSortList.GetLength(0); i++)
{
if (i != 0 && (i & 1) == 0)
{
row = 0;
col++;
}
for (int ii = 0; ii < unSortList.GetLength(1); ii++)
{
transposedMatrix[row++, col] = unSortList[i, ii];
}
}
Array.Copy(transposedMatrix, unSortList, transposedMatrix.Length);
}
private static void Swap(ref int[,] unSortList, int a_x, int a_y, int b_x, int b_y)
{
var temp = unSortList[a_y, a_x];
unSortList[a_y, a_x] = unSortList[b_y, b_x];
unSortList[b_y, b_x] = temp;
}
}
}
'알고리즘 > 기타' 카테고리의 다른 글
| 기수 정렬(RadixSort) 구현 (0) | 2018.03.22 |
|---|---|
| 계수 정렬(CountingSort) 구현 (0) | 2018.03.20 |
| QuickSort 구현 (0) | 2018.03.10 |
| heap 정렬 및 PriorityQueue (0) | 2018.02.10 |
| 후위 표기법 (0) | 2018.01.04 |