[자료구조] 정렬 , 우선순위 큐(힙정렬)

정렬이란? 물건을 크기순으로 오름/내림차순으로 나열하는 것

 

정렬 알고리즘 종류

• 삽입 정렬(Insertion Sort)
• 선택정렬(Selection Sort)
• 버블 정렬
• 셀 정렬
• 합병 정렬(Merge Sort)
• 퀵 정렬(Qiuck Sort)
• 힙 정렬(Heap Sort) ->우선순위 큐
• 기수 정렬
• 계수 정렬

1. 삽입 정렬(Insertion Sort)

정렬되어 있는 부분에 새로운 레코드(정렬의 대상)를 올바른 위치에 삽입하는 과정 반복

 

구현

//오름차순으로 정렬
void insertionSort(int A[], int n) {
    for (int i = 1; i < n; i++) {
        int key = A[i];
        int j;
        for (j = i - 1; j >= 0 && A[j] > key; j--)
            A[j + 1] = A[j];    //레코드의 오른쪽 이동
        A[j + 1] = key; 
    }
}

시간 복잡도 : O(n^2)

공간 복잡도 : O(1) ->저장장소가 추가로 필요하지 않다.(제자리 정렬)

 

2. 선택 정렬(Selection Sort)

정렬된 왼쪽 리스트와 정렬 안된 오른쪽 리스트를 가져 오른쪽 리스트에서 최소값 선택하여 왼쪽 리스트의 첫번째 수와 교환한다. 왼쪽 리스트 크기는 1증가하고 오른쪽 리스트 크기는 1감소한다.

오른쪽 리스트가 소진될때까지 위와같은 방법을 반복한다.

 

구현

//오름차순으로 정렬
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

void selection_sort(int list[], int n)
{
	int i, j, least, temp;
	for (i = 0; i < n - 1; i++) {
		least = i;
		for (j = i + 1; j < n; j++) 	// 최소값 탐색
			if (list[j] < list[least]) least = j;
		SWAP(list[i], list[least], temp);
	}
}

시간 복잡도 : O(n^2)

공간 복잡도 : O(1) ->제자리 정렬

 

3. 합병정렬(Merge Sort)

-리스트를 두 개의 부분 리스트로 분할하고 각각을 정렬

-정렬된 부분 리스트를 합해 전체 리스트를 정렬

-중간값을 계산하여 균등 분할

 

구현

int sorted[MAX_SIZE];   // 추가 공간이 필요

/* i는 정렬된 왼쪽 리스트에 대한 인덱스
		j는 정렬된 오른쪽 리스트에 대한 인덱스
		k는 정렬될 리스트에 대한 인덱스 */
void merge(int list[], int left, int mid, int right)
{
	int i, j, k, l;
	i = left;  j = mid + 1;  k = left;

	/* 분할 정렬된 list의 합병 */
	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}
	if (i>mid)	/* 남아 있는 레코드의 일괄 복사 */
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	else	/* 남아 있는 레코드의 일괄 복사 */
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	/* 배열 sorted[]의 리스트를 배열 list[]로 재복사 */
	for (l = left; l <= right; l++)
		list[l] = sorted[l];
}
//
void merge_sort(int list[], int left, int right)
{
	int mid;
	if (left<right) {
		mid = (left + right) / 2;     /* 리스트의 균등 분할 */
		merge_sort(list, left, mid);    /* 부분 리스트 정렬 */
		merge_sort(list, mid + 1, right); /* 부분 리스트 정렬 */
		merge(list, left, mid, right);    /* 합병 */
	}
}

시간 복잡도 : O(nlogn)

공간 복잡도 : O(n)

 

4. 퀵 정렬(Quick Sort)

평균적으로 가장 빠른 정렬 방법

-분할 정복법 사용

-리스트를 2개의 부분리스트로 비균등 분할하고 각각의 부분 리스트를 다시 퀵 정렬함(순환 호출)

-피벗(pivot)사용

 

구현

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[MAX_SIZE];
int n;

int partition(int list[], int left, int right)
{
	int pivot, temp;
	int low, high;

	low = left;
	high = right + 1;
	pivot = list[left];
	do {
		do
			low++;
		while (list[low]<pivot);
		do
			high--;
		while (list[high]>pivot);
		if (low<high) SWAP(list[low], list[high], temp);
	} while (low<high);

	SWAP(list[left], list[high], temp);
	return high;
}
void quick_sort(int list[], int left, int right)
{
	if (left<right) {
		int q = partition(list, left, right);
		quick_sort(list, left, q - 1);
		quick_sort(list, q + 1, right);
	}
}

//
int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력 
		list[i] = rand() % 100; 

	quick_sort(list, 0, n-1); // 퀵정렬 호출 
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

시간 복잡도 : O(nlogn)

공간 복잡도 : O(1)

 

5. 힙 정렬(Heap Sort)

-Priority Queue(우선순위 큐)

우선순위를 가진 항목들을 저장하는 큐

우선순위가 높은 데이터가 먼저 나가게 됨

가장 일반적인 큐로 생각할 수 있음

자료구조	삭제되는 요소
스택	가장 최근에 들어온 데이터
큐	가장 먼저 들어온 데이터
우선순위 큐	가장 우선순위가 높은 데이터

-응용분야

시뮬레이션,네트워크 트래픽 제어,os의 작업 스케쥴링 등

 

-구현방법

힙(Heap)을 이용한 구현 : 완전 이진트리

-힙이란?
더미,완전이진트리,최대 힙/최소 힙

-최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리

-최소 힙 : 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리 

-부모노드위 자식노드의 관계
왼쪽 자식의 인덱스= 부모의 인덱스 *2
오른쪽 자식의 인덱스= 부모의 인덱스*2 +1
부모의 인덱스 = 자식의 인덱스/2

삽입연산 :

(1) 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입

(2) 삽입 후에 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족

 

삭제연산 :

최대 힙에서의 삭제는 항상 루트가 삭제됨(가장 큰 키값을 가진 노드를 삭제하는 것)

루트에서 단말노트까지의 경로에 있는 노드들을 교환하여 힙 성질을 만족시킨다.

 

 

구현 

//최대힙 구현
#include <iostream>
using namespace std;
int N,hsize, heap[100000] = { 0, };
void insert(int item) {
	int index = ++hsize;
	while (index != 1 && item > heap[index / 2]) {
		heap[index] = heap[index / 2];
		index /= 2;
	}
	heap[index] = item;
}
int remove() {
	if (hsize == 0)	return 0;
	int ret = heap[1];
	int last = heap[hsize--];
	int parent = 1, child = 2;
	while (child <= hsize) {
		if (child < hsize && heap[child] < heap[child + 1]) {
			child++;
		}
		if (heap[child] < last)	break;
		heap[parent] = heap[child];
		parent = child;
		child *= 2;
	}
	heap[parent] = last;
	return ret;
}
int main() {
	int num;
	cin >> N;
	hsize = 0;
	for (int i = 0; i < N; i++) {
		cin >> num;
		if (num == 0)
			cout <<remove()<<'\n';
		else
			insert(num);
	}
}

입력 : 13 0 1 2 0 0 3 2 1 0 0 0 0 0

출력 : 0 2 1 3 2 1 0 0

( cf. 백준 11279: 최대 힙 )

 

시간복잡도 : O(nlogn)

 

6. 계수 정렬(Counting Sort)

자료구조 책이나 알고리즘 책에 다른 정렬과 같이 나와있지 않고 카운팅 정렬 알고리즘이 따로 있어 같이 정리해보았다.

 

숫자가 등장하는 횟수를 세서 그 기준으로 정렬

 

구현

#include <iostream>
using namespace std;
int main() {
    int N, num;
    cin >> N;
    int count[10001] = { 0, };
    for (int i = 0; i < N; i++) {
        cin >> num;
        count[num]++;
    }
    for (int j = 1; j < 10001; j++) {
        if (count[j] != 0) {
            for (int k = 0; k < count[j]; k++)  //같은 값은 개수만큼 출력한다.
                cout << j << '\n';
        }
    }
}

입력: 10 5 2 3 1 4 2 3 5 1 7   ->10은 N이고 나머지는 count에 index가 되는 num이다.

출력: 1 1 2 2 3 3 4 5 5 7

 

시간 복잡도 : O(n)

 

정렬 알고리즘 비교-시간복잡도

알고리즘	최선	평균	최악
삽입 정렬	O(n)	O(n^2)	O(n^2)
선택 정렬	O(n^2)	O(n^2)	O(n^2)
합병 정렬	O(nlogn)	O(nlogn)	O(nlogn)
퀵 정렬	O(nlogn)	O(nlogn)	O(n^2)
힙 정렬	O(nlogn)	O(nlogn)	O(nlogn)
계수 정렬	O(n)	O(n)	O(n)

->시간 복잡도만 비교한다면 합병 정렬, 퀵 정렬,힙 정렬이 빠르지만

   입력개수를 고려한다면 계수 정렬이 효율적이다.

 

   공간복잡도까지 추가해서 비교한다면 합병 정렬은 추가적인 저장공간이 필요하기 때문에  

   합병 정렬보다는퀵 정렬, 힙 정렬이 더 효율적이다.