[자료구조] 정렬 : C언어

728x90

1. 정렬이란?

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

단순하지만 비효울적인 방법

삽입정렬, 선택정렬, 버블정렬

복잡하지만 효율적인 방법

퀵정렬, 히프정렬, 합병정렬, 기수정렬

2. 선택 정렬(selection sort)

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[MAX_SIZE];
int n;

//
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);
	}
}

//
int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL));

	// 난수 생성 및 출력
	for (i = 0; i < n; i++) {
		list[i] = rand() % 100;		// 난수 발생 범위 0~99
	}

	selection_sort(list, n);		// 선택정렬 호출 

	for (i = 0; i < n; i++) {
		printf("%d ", list[i]);
	}
	printf("\n");

	return 0;
}

*선택정렬의 시간 복잡도: O(n²)

3. 삽입 정렬

: 정렬되어 있는 부분에 새로운 레코드를 오른 위치에 삽입하는 과정 반복

삽입정렬 코드

// 삽입정렬
void insertion_sort(int list[], int n)
{
	int i, j, key;
	for (i = 1; i < n; i++) {
		key = list[i];
		for (j = i - 1; j >= 0 && list[j] > key; j--) {
			list[j + 1] = list[j]; // 레코드의 오른쪽 이동
		}
		list[j + 1] = key;
	}
}

*삽입정렬의 시간복잡도: O(n²)

4. 버블 정렬

: 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환

버블정렬 코드

void bubble_sort(int list[], int n)
{
	int i, j, temp, count=0;
	for (i = n - 1; i > 0; i--) {
		for (j = 0; j < i; j++) {
			// 앞뒤의 레코드를 비교한 후 교체
			if (list[j] > list[j + 1]) {
				count++;
				SWAP(list[j], list[j + 1], temp);
			}
		}
	}
}

*버블정렬의 시간복잡도: O(n²)

5. 쉘 정렬

: 삽입정렬이 어느 정도 정렬된 리스트에서 대단히 빠른 것에 착안

삽입 정렬은 요소들이 이웃한 위치로만 이동하므로, 많은 이동에 의해서만 요소가 제자리를 찾아감
요소들이 멀리 떨어진 위치로 이동할 수 있게 하면, 보다 적게 이동하여 제자리 찾을 수 있음

전체 리스트를 일정 간견(gap)의 부분 리스트로 나눔

나뉘어진 각각의 부분 리스트를 삽입정렬

셸 정렬 코드

// gap 만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last
inc_insertion_sort(int list[], int first, int last, int gap)
{
	int i, j, key;
	for (i = first + gap; i <= last; i = i + gap) {
		key = list[i];
		for (j = i - gap; j >= first && key < list[j]; j = j - gap) {
			list[j + gap] = list[j];
		}
		list[j + gap] = key;
	}
}
//
void shell_sort(int list[], int n)   // n = size
{
	int i, gap;
	for (gap = n / 2; gap > 0; gap = gap / 2) {
		if ((gap % 2) == 0) { // gap은 홀수로 조정.
			gap++;
		}
		for (i = 0; i < gap; i++) {
			// 부분 리스트의 개수는 gap
			inc_insertion_sort(list, i, n - 1, gap);
		}
	}
}

*셸 정렬의 시간복잡도: O(n2)

6. 합병 정렬(merge sort)

1) 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분리스트를 정렬

2) 정렬된 두 개의 부분 리스트를 합하여 전체 리스트를 정렬함

1. 분할(Divide): 배열을 같은 크기의 2개의 부분 배열로 분할

2. 정복(Conquer): 부분배열을 정렬한다. 부분배열의 크기가 충분히 작지 않으면 재귀호출을 이용하여 다시 분할정복기법 적용

3. 결합(Combine): 정렬된 부분배열을 하나의 배열에 통합

합병정렬 코드

// 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(nlog(n))

7. 퀵 정렬

: 평균적으로 가장 빠른 정렬 방법, 분할정복법 사용

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

퀵 정렬 코드

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);
	}
}

*퀵 정렬의 시간 복잡도: nlog(n)

8. 기수 정렬

: 기수 정렬은 레코드를 비교하지 않고 정렬 수행