Algorithm. Sort Algorithm
[Visual Studio과 C#으로 구현/삽입,버블,쉘,힙 정렬]
Algorithm Sort Algorithm Coding // Week11
20211119_20615034
[정렬 코드모음]
using System;
namespace week11
{
class Program
{
static int N = 10;
static int[] a = new int[N];
static void Main(string[] args)
{
Random r = new Random();
for (int i = 0; i < N; i++)
a[i] = r.Next(4000);
PrintArray("버블 정렬 '전'입니다. ", a);
var watch = System.Diagnostics.Stopwatch.StartNew();
BubbleSort(a);
watch.Stop();
PrintArray("버블 정렬 '후'입니다. ", a);
Console.WriteLine("버블 정렬 '실행시간'입니다. " +
watch.ElapsedMilliseconds + "ms");
Console.WriteLine();
//n^2
for (int i = 0; i < N; i++)
a[i] = r.Next(4000);
PrintArray("힙 정렬 '전'입니다. ", a);
watch = System.Diagnostics.Stopwatch.StartNew();
HeapSort(a);
watch.Stop();
PrintArray("힙 정렬 '후'입니다. ", a);
Console.WriteLine("힙 정렬 '실행시간'입니다. " +
watch.ElapsedMilliseconds + "ms");
Console.WriteLine();
//nlogn
for (int i = 0; i < N; i++)
a[i] = r.Next(4000);
PrintArray("큌 정렬 '전'입니다. ", a);
watch = System.Diagnostics.Stopwatch.StartNew();
QuickSort(a, 0, N - 1);
watch.Stop();
PrintArray("큌 정렬 '후'입니다. ", a);
Console.WriteLine("큌 정렬 '실행시간'입니다. " +
watch.ElapsedMilliseconds + "ms");
Console.WriteLine();
//nlogn (+ 합병정렬까지)
for (int i = 0; i < N; i++)
a[i] = r.Next(4000);
PrintArray("선택 정렬 '전'입니다. ", a);
watch = System.Diagnostics.Stopwatch.StartNew();
SelectionSort(a);
watch.Stop();
PrintArray("선택 정렬 '후'입니다. ", a);
Console.WriteLine("선택 정렬 '실행시간'입니다. " +
watch.ElapsedMilliseconds + "ms");
Console.WriteLine();
//n^2
for (int i = 0; i < N; i++)
a[i] = r.Next(4000);
PrintArray("삽입 정렬 '전'입니다. ", a);
watch = System.Diagnostics.Stopwatch.StartNew();
InsertionSort(a);
watch.Stop();
PrintArray("삽입 정렬 '후'입니다. ", a);
Console.WriteLine("삽입 정렬 '실행시간'입니다. " +
watch.ElapsedMilliseconds + "ms");
Console.WriteLine();
//n^2
for (int i = 0; i < N; i++)
a[i] = r.Next(4000);
PrintArray("쉘 정렬 '전'입니다. ", a);
watch = System.Diagnostics.Stopwatch.StartNew();
ShellSort(a);
watch.Stop();
PrintArray("쉘 정렬 '후'입니다. ", a);
Console.WriteLine("쉘 정렬 '실행시간'입니다. " +
watch.ElapsedMilliseconds + "ms");
Console.WriteLine();
//n^2 (평균적으로는 1.5)
}
private static void ShellSort(int[] a)
{
int[] h = { 0, 1, 4, 10, 23, 57, 132, 301, 701, 1750 };
int index = 0;
while (h[index] < N / 2)
index++;
int gap = h[index];
while (gap > 0)
{
Console.WriteLine("gap = {0}", gap);
for (int i = gap; i < N; i++)
{
int current = a[i];
int j = i;
while (j >= gap && a[j - gap] > current)
{
a[j] = a[j - gap];
j = j - gap;
}
a[j] = current;
}
gap = h[--index];
}
}
private static void InsertionSort(int[] a)
{
for (int i = 0; i < N; i++)
{
int current = a[i];
int j = i - 1;
while (j >= 0 && a[j] > current)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = current;
}
}
private static void SelectionSort(int[] a)
{
for (int i = 0; i < N - 1; i++)
{
int min = i;
for (int j = i + 1; j < N; j++)
if (a[min] > a[j])
min = j;
Swap(i, min);
}
}
private static void QuickSort(int[] arr, int left, int right)
{
if (left < right)
{
int pivot = Partition(arr, left, right);
if (pivot > 1)
{
QuickSort(arr, left, pivot - 1);
}
if (pivot + 1 < right)
{
QuickSort(arr, pivot + 1, right);
}
}
}
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[left];
while (true)
{
while (arr[left] < pivot)
{
left++;
}
while (arr[right] > pivot)
{
right--;
}
if (left < right)
{
if (arr[left] == arr[right])
return right;
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
else
{
return right;
}
}
}
private static void HeapSort(int[] a)
{
for (int i = N / 2 - 1; i >= 0; i--)
DownHeap(a, N, i);
for (int i = N - 1; i >= 0; i--)
{
int t = a[0];
a[0] = a[i];
a[i] = t;
DownHeap(a, i, 0);
}
}
private static void PrintArray()
{
foreach (var i in a)
Console.Write(i + " ");
Console.WriteLine();
}
private static void DownHeap(int[] a, int n, int i)
{
int largest = i;
int left = 2 * i;
int right = 2 * i + 1;
if (left < n && a[left] > a[largest])
largest = left;
if (right < n && a[right] > a[largest])
largest = right;
if (largest != i)
{
Swap(i, largest);
DownHeap(a, n, largest);
}
}
private static void Swap(int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void BubbleSort(int[] a)
{
for (int i = N - 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (a[j] > a[j + 1])
{
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
}
private static void PrintArray(String s, int[] a)
{
Console.Write(s + '\n' + "현 상황 배열 : ");
for (int i = 0; i < a.Length; i++)
Console.Write(a[i] + ", ");
Console.WriteLine();
}
}
}
>>직접 짠 코드이므로 주석을 첨부하지 않겠습니다.
>> 큌/선택 정렬의 경우 연습하려고 해본 것이며 이후 진도입니다.
[내부 정렬]
내부 정렬은 입력의 크기가 주기억 장치의 공간보다 크지 않은 경우에 수행되는 정렬한다.
버블 정렬, 선택 정렬, 삽입 정렬
합병 정렬, 퀵 정렬, 힙 정렬, 쉘 정렬
기수 정렬(입력이 제한된 크기 이내에 숫자로 구성되어 있을 때)
[외부 정렬]
입력의 크기가 주기억 장치 공간보다 큰 경우에는 보조 기억 장치에 있는 입력을 여러 번에 나누어 주기억 장치에 읽어 들인 후, 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복한다.
다방향 합병(p-way Merge), 다단계 합병(Polyphase Merge)
[삽입 정렬]
Insertion Sort
배열을 정렬된 부분 (앞부분)과 정렬 안 된 부분 (뒷부분)으로 나누고, 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복한다.
정렬 안 된 부분의 숫자 하나가 정렬된 부분에 삽입됨으로써, 정렬된 부분의 원소 수가 1개 늘어나고, 동시에 정렬이 안 된 부분의 원소 수는 1개 줄어든다.
이를 반복하여 수행하면, 마지막엔 정렬이 안 된 부분엔 아무 원소도 남지 않고, 정렬된 부분에 모든 원소가 있게 된다.
단, 정렬은 배열의 첫 번째 원소만이 정렬된 부분에 있는 상태에서 정렬을 시작한다.
>>
입력: 크기가 n인 배열 A
출력: 정렬된 배열 A
1. for i = 1 to n-1 {
2. CurrentElement = A[i] // 정렬 안된 부분의 가장 왼쪽원소
3. j ← i – 1 // 정렬된 부분의 가장 오른쪽 원소로부터 왼쪽 방향으로 삽입할 곳을 탐색하기 위하여
4. while (j >= 0) and (A[j] > CurrentElement) {
5. A[j+1] = A[j] // 자리 이동
6. j ← j -1
}
7. A [j+1] ← CurrentElement
}
8. return A
>>
삽입 정렬은 정렬된 부분에는 A[0]만이 있는 상태에서 정렬이 시작된다.
- Line 1
CurrentElement의 배열 인덱스 i를 위해 for-루프를 이용하여 1(n-1)까지 변한다.
- Line 2
정렬 안 된 부분의 가장 왼쪽에 있는 원소인 A[i]를 CurrentElement로 놓는다.
- Line 3
‘j=i-1’은 j가 정렬된 부분의 가장 오른쪽 원소의 인덱스가 되어 왼쪽 방향으로 삽입할 곳을 탐색하기 위함이다.
- Line 4~6
CurrentElement가 삽입될 곳을 찾는다.
while-루프의 조건 (j >= 0)은 배열 인덱스로 사용되는 j가 배열의 범위를 벗어나는 것을 방지하기 위함이고,
2번째 조건 (A[j] > CurrentElement)는 A[j]가 CurrentElement보다 크면 A[j]를 오른쪽으로 1칸 이동시키기 위함이다.
이러한 자리이동은 line 5에서 수행된다.
Line 6에서는 j를 1 감소시켜 바로 왼쪽 원소에 대해 while-루프를 반복적으로 수행함
- Line 7
A[j+1]에 CurrentElement를 저장한다.
이는 while-루프가 끝난 직후에는 A[j]가 CurrentElement보다 크지 않으므로 A[j]의 오른쪽 (즉, A[j+1])에 CurrentElement를 삽입해야 하기 때문이다.
[버블 정렬]
Bubbble Sort
이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복하여 정렬하는 알고리즘이다.
오름차순으로 정렬한다면, 작은 수는 배열의 앞부분으로 이동하는데, 배열을 좌우가 아니라 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 ‘거품’처럼 위로 올라가는 것을 연상케 한다.
입력을 전체적으로 1번 처리하는 것을 패스 (pass) 라고 한다.
1번째 pass 결과를 살펴보면, 작은 수는 버블처럼 위로 1칸씩 올라갔다.
‘무거운’ 수 (즉, 큰 수)의 측면에서 관찰해보면, 가장 큰 수인 90이 ‘바닥’ (즉, 배열의 가장 마지막 원소)에 위치하게 된다.
2 번째 패스의 수행 과정
이웃하는 원소간의 비교를 통해 40-50은 그대로 그 자리에 있고, 50과 10이 서로의 자리를 바꾸었다.
두 번째로 큰 수인 50이 가장 큰 수인 90의 위로 “가라앉았다.”
마지막 패스의 수행 과정
이웃하는 원소간의 비교를 통해 40과 10이 서로 자리를 바꾸었다.
세 번째로 큰 수인 40이 두 번째로 큰 수인 50의 위로 “가라앉았다.”
n개의 원소가 있으면 (n-1)번의 패스가 수행된다.
>>
BubbleSort
입력: 크기가 n인 배열 A
출력: 정렬된 배열 A
1. for pass = 1 to n-1
2. for i = 1 to n-pass
3. if (A[i-1] > A[i]) // 위의 원소가 아래의 원소보다 크면
4. A[i-1] ↔ A[i] // 서로 자리를 바꾼다.
5. return 배열 A
Line 1
for-루프가 (n-1)번의 패스를 수행한다.
Line 2의 for-루프
배열의 이웃하는 원소를 A[0]부터 A[n-pass]까지 비교하기 위함이다.
배열 인덱스 (n-pass)는 pass=1이면 A[n-1]까지 비교하고, pass=2이면 A[n-2]까지 비교하는데, 이는 pass=1이 수행되고 나면 가장 큰 숫자가 A[n-1]에 저장되므로 A[n-2]까지만 비교하기 위한 것이다.
마찬가지로 pass=3이면, 2번째로 큰 숫자가 A[n-2]에 저장되어있기 때문에 A[n-3]까지만 비교한다.
Line 3~4
if-조건인 (A[i-1] > A[i])가 ‘참’이면, 즉, 위의 원소가 아래의 원소보다 크면, A[i-1]과 A[i]를 서로 바꾼다.
만일 if-조건이 ‘거짓’이면 아무 일도 하지 않고 다음 i값에 대해 알고리즘이 진행된다.
>>
버블 정렬은 for-루프 속에서 for-루프가 수행되는데,
pass=1이면 (n-1)번 비교하고,
pass=2이면 (n-2)번 비교하고, ⋯
pass=n-1이면 1번 비교한다.
총 비교 횟수: (n-1) + (n-2) + ⋯ + 1 = n(n-1)/2
안쪽 for-루프의 if-조건이 ‘참’일 때의 자리바꿈은 O(1)
시간복잡도
n(n-1)/2 x O(1) = O(n2) x O(1) = O(n2)
[쉘 정렬]
Shell sort
버블 정렬이나 삽입 정렬이 수행되는 과정
이웃하는 원소끼리의 자리 이동으로 원소들이 정렬된다.
버블 정렬이 오름차순으로 정렬하는 과정
작은 (가벼운) 숫자가 배열의 앞부분으로 매우 느리게 이동한다.
삽입 정렬의 경우 만일 배열의 마지막 원소가 입력에서 가장 작은 숫자일 경우
그 숫자가 배열의 맨 앞으로 이동해야 하므로, 모든 다른 숫자들이 1칸 씩 오른쪽으로 이동해야 한다.
이러한 단점을 보완하기 위해서 삽입 정렬을 이용하여
배열 뒷부분의 작은 숫자를 앞부분으로 ‘빠르게' 이동시키고,
동시에 앞부분의 큰 숫자는 뒷부분으로 이동시키고,
가장 마지막에는 삽입 정렬을 수행하는 알고리즘이다.
>>
쉘 정렬은 간격 [ h0 > h1 > ⋯ > hk=1]이 미리 정해져야 한다.
가장 큰 간격 h0부터 차례로 간격에 따른 삽입 정렬이 line 2~8에서 수행된다.
마지막 간격 hk는 반드시 1이어야 한다.
이는 간격에 대해서 그룹별로 삽입 정렬을 수행하였기 때문에, 아직 비교 되지 않은 다른 그룹의 숫자가 있을 수 있기 때문이다.
- Line 2~8
for-루프에서는 간격 h에 대하여 삽입 정렬이 수행되는데, 그룹 별로 삽입 정렬을 수행하지만 자리바꿈을 위한 원소간의 비교는 다음과 같은 순서로 진행된다.
즉, line 2의 for-루프가 i를 h부터 1씩 증가시켜서 CurrentElement A[i]를 자신의 그룹에 속한 원소끼리 비교하도록 조절한다.
- Line 5~7
while-루프에서 CurrentElement를 정렬이 되도록 앞부분에 삽입한다.
while-루프의 첫 번째 조건 (j>=h)는 j가 h보다 작으면 배열 인덱스 (j-h)가 음수가 되어, 배열의 범위를 벗어나는 것을 검사하기 위한 것이다.
2번째 조건인 (A[j-h] > CurrentElement)는 (j-h)가 음수가 아니면 CurrentElement를 자신의 그룹 원소인 A[j-h]와 비교하여 크면 line 6에서 A[j-h]를 h만큼 뒤로 이동 (즉, A[j]=A[j-h])시킨다.
- Line 8
while-루프의 조건이 ‘거짓’이 되면 line 8에서 CurrentElement를 A[j]에 저장한다. 여기서 while-루프의 조건이 ‘거짓’이 될 때
첫 번째 경우는 (j-h)가 음수인 경우인데, 이는 A[j] 앞에 같은 그룹의 원소가 없다는 뜻이다.
두 번째 경우는 A[j-h]가 CurrentElement과 같거나 작은 경우이다.
따라서 두 경우 모두 line 8에서 CurrentElement를 A[j]에 저장하면 알맞게 삽입된다.
[힙 정렬]
heap sort
힙 조건을 만족하는 완전 이진트리 (Complete Binary Tree)이다.
힙 조건이란 각 노드의 값이 자식 노드의 값보다 커야 한다는 것을 말한다.
노드의 값은 우선순위 (priority)라고 일컫는다.
힙의 루트에는 가장 높은 우선순위 (가장 큰 값)가 저장되어 있다.
값이 작을수록 우선순위가 높은 경우에는 가장 작은 값이 루트에 저장된다.
n개의 노드를 가진 힙
완전 이진트리이므로, 힙의 높이가 log2n이며, 노드들을 빈 공간 없이 배열에 저장할 수 있다.
배열 A에 힙을 저장한다면, A[0]은 비워 두고, A[1] A[n]까지에 힙 노드들을 트리의 층별로 좌우로 저장한다.
루트의 90이 A[1]에 저장되고,
그 다음 층의 60과 80이 각각 A[2]와 A[3]에 저장되며,
그 다음 층의 50, 30, 70, 10이 A[4]에서 A[7]에 각각 저장되고,
마지막으로 20과 40이 A[8]과 A[9]에 저장된다.
힙에서 부모 노드와 자식노드의 관계
A[i]의 부모 노드= A[i/2]
단, i가 홀수일 때, i/2에서 정수 부분만을 취한다. 예를 들어, A[7]의 부모 노드는 A[7/2] = A[3]이다.
A[i]의 왼쪽 자식 노드 = A[2i]
A[4]의 왼쪽 자식 노드는 A[2i] = A[2x4] = A[8]
A[i]의 오른쪽 자식 노드= A[2i+1]
오른쪽 자식 노드는 A[2i+1] = A[2x4+1] =A[9]
>>
힙 정렬(Heap Sort)
힙 자료 구조를 이용하는 정렬 알고리즘이다.
오름차순의 정렬을 위해 최대힙(maximum heap) 구성한다.
힙의 루트에는 가장 큰 수가 저장되므로, 루트의 숫자를 힙의 가장 마지막 노드에 있는 숫자와 바꾼다.
즉, 가장 큰 수를 배열의 가장 끝으로 이동시킨 것이다.
그리고 루트에 새로 저장된 숫자로 인해 위배된 힙 조건을 해결하여 힙 조건을 만족시키고, 힙 크기를 1개 줄인다.
그리고 이 과정을 반복하여 나머지 숫자를 정렬한다.
입력: 입력이 A[1]부터 A[n]까지 저장된 배열 A
출력: 정렬된 배열 A
1. 배열 A의 숫자에 대해서 힙 자료 구조를 만든다.
2. heapSize = n // 힙의 크기를 조절하는 변수
3. for i = 1 to n-1
4. A[1] ↔ A[heapSize] // 루트와 힙의 마지막 노드 교환
5. heapSize = heapSize -1 // 힙의 크기를 1 감소
6. DownHeap() // 위배된 힙 조건을 만족시킨다.
7. return 배열 A
- Line 1
배열 A[1..n]을 힙으로 만든다.
- Line 2
현재의 힙의 크기를 나타내는 변수인 heapSize를 n으로 초기화시킨다.
- Line 3~6
for-루프는 (n-1)번 수행되는데, 이는 루프가 종료된 후에는 루트인 A[1] 홀로 힙을 구성하고 있고, 또 가장 작은 수이므로 루프를 수행할 필요가 없기 때문이다.
- Line 4
루트와 힙의 마지막 노드와 교환한다.
즉, 현재의 힙에서 가장 큰 수와 현재 힙의 맨 마지막 노드에 있는 숫자와 교환하는 것이다.
- Line 5
힙의 크기를 1 줄인다.
- Line 6
위반된 힙 조건을 DownHeap을 수행시켜서 해결한다.
Line 4에서 힙의 마지막 노드와 힙의 루트를 바꾸어 놓았기 때문에 새로이 루트에 저장된 값이 루트의 자식 노드의 값보다 작아서 힙 조건이 위배되기 때문
- DownHeap
루트가 r을 가지고 있다고 가정하자.
먼저 루트의 r과 자식 노드들 중에서 큰 것을 비교하여 큰 것과 r을 바꾼다.
다시 r을 자식 노드들 중에서 큰 것과 비교하여 힙 조건이 위배되면, 앞서 수행한 대로 큰 것과 r을 교환한다.
힙 조건이 만족될 때까지 이 과정을 반복한다.
댓글 없음:
댓글 쓰기