정렬 알고리즘(sorting algorithm)은 수열을 정렬하는 알고리즘입니다.
시간 복잡도란?
- 알고리즘이 문제를 해결하는 시간을 나타냅니다.
좌측부터 실행 속도가 빠릅니다.O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(2^N) > O(N!)
정렬 알고리즘의 시간 복잡도
1. 버블 정렬(bubble sort)
개념
- 서로 인접한 두 원소를 검사하여 오름차순으로 나열합니다.
- 주로 정렬에 대한 교육용으로 사용됩니다.
원리
① 0번과 1번 인덱스(6, 3)의 데이터를 비교합니다.
② 큰 데이터(6)는 뒤로 배치합니다.
③ 1번과 2번 인덱스(6, 1)의 데이터를 비교합니다.
④ 큰 데이터(6)를 다시 뒤로 배치합니다.
⑤ 반복하면 데이터가 가장 큰 인덱스(9)가 배열의 마지막으로 이동합니다.
9는 정렬을 끝낸 것으로 간주하고 처음부터 다시 실행합니다.
코드로 구현
using System;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
int[] array = new int[] { 6, 3, 1, 7, 9, 2, 4, 5, 8 };
int temp;
for (int i = 0; i < array.Length - 1; i++)
{
for (int j = 0; j < array.Length - 1 - i; j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
for (int i = 0; i < array.Length; i++)
{
Console.WriteLine(array[i]);
}
}
}
}- 내부 for문 조건식에서 i를 감소시켜 중복 실행을 방지합니다.
- if문 구현부는 j 인덱스가 j+1 인덱스보다 클 때 두 인덱스를 스왑하는 역할을 합니다.
- if문 조건식에서 부등호 방향을 바꾸면 내림차순으로 정렬이 됩니다.
특징
장점
- 구현하기 쉽고 정밀한 비교가 가능합니다.
단점
- 모든 인덱스를 비교하므로 연산시간과 성능이 불규칙적이고 배열이 클수록 비효율 적입니다.
2. 선택 정렬(selection sort)
개념
- 원소를 삽입할 위치를 정해두고 어떤 원소를 삽입할지 선택합니다.
- 배열의 최소값을 찾고 맨 앞의 인덱스와 교체하여 오름차순으로 나열합니다.
- 알고리즘 관련 시험과 면접에 자주 나오는 정렬입니다.
원리
① 배열을 순차적으로 탐색합니다.
② 최소값(1)을 찾습니다.
③ 최소값(1)을 0번 인덱스(6)의 데이터와 교체하고 0번 인덱스(1)는 정렬을 마친 것으로 간주합니다.
④ 처음부터 다시 실행합니다.
코드로 구현
using System;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
int[] array = new int[] { 6, 3, 1, 7, 9, 2, 4, 5, 8 };
int temp;
int min;
for (int i = 0; i < array.Length - 1; i++)
{
min = i;
for (int j = i + 1; j < array.Length; j++)
{
if (array[j] < array[min])
{
min = j;
}
}
temp = array[min];
array[min] = array[i];
array[i] = temp;
}
for (int i = 0; i < array.Length; i++)
{
Console.WriteLine(array[i]);
}
}
}
}- min 변수는 인덱스를 비교하는 과정에서 작은 인덱스의 데이터를 저장할 변수입니다.
- if문 조건식에서 부등호 방향을 바꾸면 내림차순으로 정렬이 됩니다.
- 처음 실행했을 때 외부 for문의 i와 min은 0이며, 내부 for문의 j값은 1이 됩니다.
배열의 0번 인덱스가 1번 인덱스보다 크다면 min에 j를 저장합니다. (j는 1이었으니 min은 1이 됩니다.)
특징
장점
- 구현하기 쉬우며 별다른 메모리 공간이 필요없는 제자리 정렬(in-place)입니다.
단점
- 다른 정렬에 비해 비효율적이며 불안정 정렬입니다.
불안정 정렬(unstable sort)이란?
불안정 정렬은 정렬의 방법이 아닌 정렬의 특성입니다.
의미는 무엇일까요. 한가지 예를 들어보겠습니다.
1,2,3,1 배열이 있습니다. 이 배열을 선택 정렬하면 아래와 같이 두가지의 결과가 존재합니다.
빨간색 1과 초록색 1은 데이터가 같지만 위치가 다릅니다. 그렇기에 어느 것이 맞는 정렬인지 보장되지 않습니다.
이것이 불안정 정렬입니다. 오직 같은 숫자만으로 정렬되기 때문에 실행을 할때마다 위치가 뒤바낄 수 있습니다.
반대로, 빨간색 1이 초록색 1의 인덱스를 침범하지 못하게 설계된 정렬을 안정 정렬이라고 합니다.
(플레잉카드의 안정 정렬 예시)
이 특성을 모를 경우 정렬을 했을 때 원하는 결과를 얻지 못할 수 있습니다.
그렇기에 정렬의 안정적 특성을 고려하여 알고리즘을 선택하는 것이 중요합니다.
3. 삽입 정렬(insertion sort)
개념
- 자료 배열의 모든 요소를 앞에서부터 차례대로, 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬입니다.
원리
① 두 번째에 위치한 데이터(3)부터 탐색을 시작합니다. 이 때 기준점을 잡는 인덱스를 키(key)라고 정정하겠습니다.
② key(3)와 key앞의 데이터(6)를 비교하여, key(3)의 크기가 작다면 서로의 위치를 변경을 진행합니다.
key가 배열의 가장 앞에 도착할 때까지 이 작업을 반복하는데, 만약 key보다 데이터가 작으면 변경하지 않고 다음 인덱스를 기준으로 다시 정렬을 실행합니다.
지금은 key(3) 보다 더 이상 앞의 인덱스를 찾을 수 없으니 다음 인덱스로 넘어갑니다.
③ 2번 인덱스(1)가 key가 됩니다.
key와 정렬이 완료된 앞의 인덱스(6)를 비교합니다.
④ 앞에 아직 인덱스가 존재하니 이번에는 다시 0번 인덱스(3)와 교체합니다.
동일한 작업을 모든 원소가 정렬을 마칠 때까지 반복합니다.
코드로 구현
using System;
namespace ConsoleApp1
{
class Program
{
static int[] array = new int[] { 6, 3, 1, 7, 9, 2, 4, 5, 8 };
//결과 출력 함수
static void Print()
{
Console.Write(string.Join(", ", array));
}
static void Main(string[] args)
{
int key;
int j;
for (int i = 1; i < array.Length; i++)
{
//외부 for문이 작동할 때마다 key값을 갱신합니다.
key = array[i];
for (j = i - 1; j >= 0; j--)
{
if (array[j] < key) break; //배열의 인덱스[j]가 key 데이터의 크기보다 작으면 for문 멈춥니다.
array[j + 1] = array[j]; //그렇지 않다면 key 앞의 인덱스를 key 자리에 삽입합니다.
}
array[j + 1] = key; //그리고 키 값을 교체합니다.
}
Print();
}
}
}- 변수 key는 인덱스간 비교를 담당하며 동시에 임시변수(temp)의 역할도 합니다.
- 변수 j를 전역변수로 설정합니다. 내부 for문의 j값을 외부 for문에서 사용하기 위함입니다.
- 내부 for문은 key의 인덱스보다 앞에 위치한 인덱스를 비교합니다. 반복실행하기 위해 증감식에 감소연산자를 사용합니다.
특징
장점
- 알고리즘이 간단하므로 데이터의 크기가 작을수록 복잡하게 구현된 정렬보다 빠릅니다.
단점
- 데이터의 크기가 커질수록 효율이 떨어집니다.
3.5. 트리 구조란?
개념
- 트리 구조란 나무(tree)의 가지처럼 뻗어나가는 특징을 가지고 있습니다. 데이터가 서로 연결되어 있습니다.
- 트리의 요소는 노드(node), 연결하는 선은 간선(edge)이라고 부릅니다.
트리는 하나의 루트 노드를 가지고 있으며 루트 노드는 0개 이상의 자식 노드를 갖습니다.
또한 자식 노드도 0개 이상의 자식 노드를 갖습니다.
완전 이진 트리(complete binary tree)
- 힙 정렬(heap sort)은 완전이진트리의 특징을 갖습니다.
완전이진트리란 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리의 종류 중 하나입니다.① 루트(root-node) : 부모 노드가 없는 최상위 노드 (A)
② 리프(leaf-node) : 자식 노드가 없는 노드 (C,D,E)
③ 부모(parent-node) : 자신과 간선으로 이어진 하위 노드가 존재할 때 본인의 노드 (B)
④ 자식(child-node) : 부모 노드가 같은 노드 (D,E). 서로 형제(sibling)라고 부릅니다.
4. 힙 정렬(heap sort)
개념
- 힙(heap)이란 최대값과 최소값을 빠르게 찾아내기 위해 고안된 자료구조입니다.
- 최대 힙(내림차순)이나 최소 힙(오름차순)을 구성하여 정렬을 할 수 있습니다.
힙이란?
- 힙 정렬을 하기 위해서 먼저 힙을 만들어야 합니다.
1부터 7까지 숫자가 섞여있는 배열 {4,6,1,7,5,3,2}로 최대 힙과 최소 힙을 만들어 보겠습니다.
최대 힙
① 첫번째 값인 4가 빠져나와 뿌리 노드가 됩니다.
② 그다음 두번째 값이 빠져나와 자식 노드가 됩니다.
③ 최대 힙 정렬은 높은 숫자가 뿌리 노드에 와야합니다.
자식 노드의 값이 부모 노드보다 크다면 교체를 해줍니다.
④ 1은 부모 노드보다 값이 크지 않으므로 변경하지 않고 넘어갑니다.
⑤ 마침 큰 값의 자식 노드가 생겼습니다.
⑥ 규칙에 맞게 노드를 교체해주면 이와 같이 교체가 됩니다.
남은 값들도 채워준 {7,6,3,4,5,1,2} 배열이 최대 힙입니다.
반대로 작은 수가 뿌리 노드에 오게 하는 것은 최소 힙이라 합니다.
최소 힙
- 최대 힙과 과정이 같으므로 추가적인 설명은 생략합니다.
- 최소 힙의 경우에는 최대 힙과 반대로 작은 순으로 뿌리 노드에 위치하게 만듭니다.
힙 정렬
최대 힙 정렬
- 힙 정렬은 만들어진 힙을 참조하여 정렬을 시행합니다.
- 힙 정렬을 할 때는 가장 늦게 들어온 값부터 뺄 수 있습니다.
- 최대 힙 정렬은 큰 값부터 추출하고 역순으로 나열
- 최대 힙의 뿌리 노드는 배열 중 가장 큰 값이 존재
- 늦게 들어온 값부터 뺄 수 있음
① 처음 시작은 늦게 들어온 값부터 뺄 수 있기 때문에 뿌리 노드(7)의 데이터를 2와 7의 위치를 변경하는 것 입니다.
② 7은 정렬되었다고 간주하고 노드에서 사용을 하지 않습니다.
2가 뿌리 노드로 이동했으므로 다시 힙을 만들어야 합니다.
③ 뿌리 노드의 자식 노드 중 왼쪽 자식 노드와 오른쪽 자식 노드의 크기를 비교합니다.
만약 자식 노드가 부모 노드보다 크지 않으면 변경하지 않습니다.
6과 3을 비교했을 때 6이 크기 때문에 뿌리 노드(2)와 큰 값의 자식 노드(6)의 위치를 교체하면 됩니다.
④ 변경이 완료되었으나 2 밑에 아직 자식 노드가 존재합니다.
다시 자식 노드끼리의 크기 비교를 하여 큰 값을 부모 노드(2)와 위치를 변경합니다.
완료됐습니다. 여기까지가 표의 6행까지 진행 순서입니다.
⑤ 남은 노드들은 다시 최대 힙 정렬을 시행하여 모든 요소가 정렬을 마칠 때까지 반복합니다.
힙 정렬은 꺼낸 숫자를 역순으로 나열하면 최대 힙 정렬이 완료됩니다.
최대 힙 정렬 과정입니다.
최소 힙 정렬
- 최소 힙 정렬은 정렬이 끝나면 오름차순으로 나열이 되야합니다.
마찬가지로 자세한 과정은 생략합니다.
코드로 구현
using System;
namespace ConsoleApp1
{
class Program
{
static int[] array = new int[] { 4, 6, 1, 7, 5, 3, 2 };
static void Print()
{
// 출력 함수
Console.Write(string.Join(", ", array));
}
static void heapSort(int[] array)
{
// 최대 힙 초기화
for (int i = array.Length / 2 - 1; i >= 0; i--)
{
heapify(array, array.Length, i);
}
for (int i = array.Length - 1; i > 0; i--)
{
swap(array, 0, i);
heapify(array, i, 0);
}
}
static void heapify(int[] array, int arrayLength, int i)
{
int parent = i;
int left = i * 2 + 1;
int right = i * 2 + 2;
// 왼쪽 자식노드
if (left < arrayLength && array[parent] < array[left])
{
parent = left;
}
// 오른쪽 자식노드
if (right < arrayLength && array[parent] < array[right])
{
parent = right;
}
// 부모노드 < 자식노드
if (i != parent)
{
swap(array, parent, i);
heapify(array, arrayLength, parent);
}
}
static void swap(int[] array, int a, int b)
{
int temp;
temp = array[a];
array[a] = array[b];
array[b] = temp;
}
static void Main(string[] args)
{
heapSort(array);
Print();
}
}
}- 힙 정렬은 고급 알고리즘인 만큼 코드 이해가 어려울 수 있으므로 부연 설명을 첨부합니다.
↓
heapSort 함수
static void heapSort(int[] array)
{
// 최대 힙 초기화
for (int i = array.Length / 2 - 1; i >= 0; i--)
{
heapify(array, array.Length, i);
}
for (int i = array.Length - 1; i > 0; i--)
{
swap(array, 0, i);
heapify(array, i, 0);
}
}- 첫번째 for문에서는 매개변수로 받아온 배열의 부모 노드의 개수를 파악합니다.
- 두번째 for문은 매개변수로 받아온 배열의 노드를 스왑하고 최대 힙을 재구성합니다. 배열의 최대 길이를 감소식을 사용하여 노드가 지워질 때마다 남은 작동을 하게 됩니다.
- 시작점을 'array.Length / 2 - 1'로 잡는 이유는 우리가 사용할 배열의 길이인 7로 예시를 들어보겠습니다.
① '7 / 2 - 1'는 2.5입니다.이 값을 int형으로 받으면 2 입니다.
② 조건식의 0보다 크거나 같을 때까지. 즉 0, 1, 2는 부모 노드 개수인 3개임을 알 수 있습니다. - 불필요한 작동을 방지하고 효율적인 정렬을 위해 정렬을 할 때마다 매번 for문을 거쳐 작동합니다.
heapify 함수
static void heapify(int[] array, int arrayLength, int i)
{
int parent = i;
int left = i * 2 + 1;
int right = i * 2 + 2;
// 왼쪽 자식노드
if (left < arrayLength && array[parent] < array[left])
{
parent = left;
}
// 오른쪽 자식노드
if (right < arrayLength && array[parent] < array[right])
{
parent = right;
}
// 부모노드 < 자식노드
if (i != parent)
{
swap(array, parent, i);
heapify(array, arrayLength, parent);
}
}
static void swap(int[] array, int a, int b)
{
int temp;
temp = array[a];
array[a] = array[b];
array[b] = temp;
}- 매개변수로 배열, 배열의 길이, 시작점을 받아옵니다.
시작점은 부모 노드와 자식 노드를 계산할 때 사용하는데 부모 노드와 자식 노드간의 관계는 i, 2i, 2i+1로 구할 수 있습니다.
그런데 메소드에서는 왜 i, 2i+1, 2i+2로 선언했을까요?
이는 heapSort 함수 첫 번째 for문 조건식을 0까지 허용했기 때문인데요,
만약 for문의 시작점과 조건식을 'int i = (array.Length - 1) / 2; i >= 1' 로 선언했다면 heapify 함수의 부모, 자식 변수 선언시에는 i, 2i, 2i+1로 사용해야 합니다. - 보통 힙 정렬은 편의상 0번 인덱스는 사용하지 않기 때문에 1로 두는 방법을 많이 쓰는데 속도나 메모리 차이는 없어서 어떤 식으로 작성하나 지장은 없습니다.
- if문은 부모 노드와 왼쪽 자식 노드, 오른쪽 자식 노드를 비교하여
자식 노드가 클 경우 부모와 위치를 바꾸어주고
마지막 if문에서 스왑을 거친 뒤 최대 힙이 재구성될 때까지 함수 자신을 반복실행(재귀)합니다.
특징
장점
- 데이터의 min과 max를 구할 때 편리합니다.
- 항상 O(NlogN)를 제공합니다. (데이터가 작을수록 단점이 됩니다.)
단점
- 불안정 정렬입니다.
유익한 글이었습니다.