자료구조_12.정렬

자료구조

자료구조_12.정렬

강용민 2021. 12. 3. 15:37

정렬이란?

정렬은 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것을 의미한다.

레코드, 필드, 키

보통 정렬시켜야할 될 대상은 레코드(record)라 불리며, 또 레코드는 필드(field)라는 보다 작은 단위로 구성된다.

여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 키라고 한다.

알고리즘의 효율성

모든 경우에 최적인 정렬 알고리즘은 없다. 즉, 각 응용 분야에 적합한 정렬 방법을 사용해야 한다.

대개 정렬 알고리즘을 평가하는 효율성의 기준으로는 정렬을 위해 필요한 비교 연산의 횟수와 이동 연산의 횟수이다.

이들 횟수를 빅오 표기법을 이용하여 근사적으로 표현한다.

정렬의 종류

정렬 알고리즘을 내부 정렬(internal sorting)과 외부정렬(external sorting)로 구분할 수도 있다.

내부 정렬
- 모든 데이터가 주기억장치(메인 메모리)에 저장되어진 상태에서 정렬
외부 정렬
- 외부기억장치(하드디스크 혹은 SSD등)에 대부분의 데이터가 있고 일부만 주기억장치에 저장된 상태에서 정렬

정렬 알고리즘을 안전성(stability)의 측면에서 분류할 수있다.

안전성이란 입력 데이터에 동일한 키값을 갖는 레코드가 여러 개 존재할 경우, 이들 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않음을 뜻한다. 반대로 같은 키값을 갖는 레코드들이 정렬후에 위치가 바뀌게 되면 안정하지 않다고 한다.

안전성을 충족하는 정렬중에는 삽입정렬, 버블정렬, 합병정렬 등이 있다.

선택 정렬

선택정렬은 먼저 왼쪽 리스트와 오른쪽 리스트, 두 개의 리스트가 있다고 가정하고, 왼쪽 리스트에는 정렬이 완료된 숫자들이 들어가게 되며 오른쪽 리스트에는 정렬되지 않은 숫자들이 들어 있다.

오른쪽 리스트에 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 오른쪽 리스트가 공백상태가 될 때까지 이과정을 되풀이 하면 정렬이 완료가 된다.

제자리 정렬

위의 방법은 배열로 구현하기로 한다면, 오른쪽 리스트와 왼쪽리스트 두 개의 배열이 필요하다. 따라서 메모리를 절약하기 위하여 한 리스트만으로 선택 정렬을 하려 한다면 제자리 정렬(in-place sorting)을 사용하면 된다.

제자리 정렬은 한 리스트에 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환한다. 다음에는 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환하는 방식을 n-1번 되풀이하면 추가적인 배열을 사용하지 않고서도 정렬을 할 수 있다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))	//temp를 이용해 x와 y값을 스왑

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++) {	//i번째 배열값 기준
		least = i;
		for (j = i + 1; j < n; j++)	//i번째 이상의 배열중 최소값을 값고 있는 least번째 배열 찾기
			if (list[j] < list[least]) least = j;
		SWAP(list[i], list[least], temp);	//i번째 배열과 least번째 배열 스왑
	}
}

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

	selection_sort(list, n);	//선택정렬 호출
	for (i = 0; i < n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

복잡도 분석

비교 횟수
- (n-1) + (n-2) + ... + 1 = n(n -1) / 2 = O(n^2)
이동 횟수
- 3(n-1) 이하
전체 시간복잡도: O(n^2)
선택 정렬은 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있으므로 안정성을 만족하지 않는다. 하지만 몇개의 구문만 추가하면 만족한다.

삽입 정렬

삽입 정렬은 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다.

선택 정렬과 마찬가지로 입력배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용하면 된다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))	//temp를 이용해 x와 y값을 스왑

int list[MAX_SIZE];
int n;

//삽입정렬
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;

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

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

//	selection_sort(list, n);	//선택정렬 호출
//	insertion_sort(list, n);	//삽입정렬 호출
	for (i = 0; i < n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

복잡도 분석

최선의 경우 O(n) : 이미 정렬되어 있는 경우
- 비교 : n-1 번
최악의 경우 O(n^2) : 역순으로 정렬되어 있는 경우
- 모든 단계에서 앞에 놓인 자료 전부 이동
- 비교 : O(n^2)
- 이동 : O(n^2)
평균의 경우 O(n^2)
안정된 정렬 방법이며, 대부분 정렬되어 있으면 매우 효율적일 수 있다.

버블 정렬

버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트 왼쪽 끝에서 오른쪽 끝까지 진행한다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))	//temp를 이용해 x와 y값을 스왑

int list[MAX_SIZE];
int n;

//버블정렬
void bubble_sort(int list[], int n) {
	int i, j, temp;
	for (i = n - 1; i > 0; i--) {
		for (j = 0; j < i; j++) {
			if (list[j] > list[j + 1])
				SWAP(list[j], list[j + 1], temp);
			for (int j = 0; j < n; j++)
				printf("%d ", list[j]);
			printf("\n");
		}
		
	}
}

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

//	selection_sort(list, n);	//선택정렬 호출
//	insertion_sort(list, n);	//삽입정렬 호출
	bubble_sort(list, n);

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

복잡도 분석

비교 횟수 : 최상, 평균, 최악의 경우 모두 일정 O(n^2)
이동 횟수
- 최악의 경우(역순으로 정렬된 경우) : 3* 비교횟수
- 평균의 경우 : O(n^2)
- 최선의 경우(이미 정렬된 경우) : 0

쉘 정렬

쉘 정렬은 삽입정렬이 어느 정도 정렬된 리스트에서 빠른 것에서 착안했다.

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

삽입 정렬과는 다르게 쉘 정렬은 전체의 리스트를 한 번에 정렬하지 않고, 먼저 정렬해야할 리스트를 일정한 기준(gap)에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.

모든 부분 리스트가 정렬되면 쉘정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이하는데 위의 과정을 부분 리스트의 개수(gap)이 1이 될 때까지 되풀이한다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))	//temp를 이용해 x와 y값을 스왑

int list[MAX_SIZE];
int n;

//쉘 삽입정렬
void 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;
		for (int j = 0; j < n; j++)
			printf("%d ", list[j]);
		printf("\n");
	}
}

//쉘 gap
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++; {
			printf("gap : %d\n", gap);
			for (i = 0; i < gap; i++)
				inc_insertion_sort(list, i, n - 1, gap);
		}
	}
}
int main() {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i < n; i++)	//난수 생성 및 출력
		list[i] = rand() % 100;

//	selection_sort(list, n);	//선택정렬 호출
//	insertion_sort(list, n);	//삽입정렬 호출
//	bubble_sort(list, n);	//버블정렬 호출
	shell_sort(list, n);	//쉘 정렬 호출

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

복잡도 분석

쉘 정렬의 장점
- 불연속적인 부분 리스트에서 원거리 자료 이동으로 보다 적은 위치교환으로 제자리 찾을 가능성 증대
- 부분 리스트가 점진적으로 정렬된 상태가 되므로 삽입정렬 속도 증가
시간복장도
- 최악의 경우 : O(n^2)
- 평균적인 경우 : O(n^1.5)

합병 정렬

합병 정렬(merge sort)은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다.

합병 정렬은 분할 정복(divide and conquer) 기법에 바탕을 두고 있다.

분할 정복 기법은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

분할(Devide) : 배열을 같은 크기의 2개의 부분 배열로 분할
정복(Conquer) : 부분배열을 정렬한다. 부분배열의 크기가 충분히 작지 않으면(합병정렬에서는 부분배열의 요소가 2개초과인 경우) 재귀호출을 이용하여 다시 분할정복기법 적용
결합(Combine) : 정렬된 부분배열을 하나의 배열에 통합

의사코드

merge_sort(list,left,right):

if left < right	//나누어진 구간의 크기가 1이상이면
	mid = (left,right)/2;	//중간 위치를 계산한다.
    merge_sort(list, left, mid)	//앞쪽 부분 배열을 정렬하기 위하여 merge_sort한수를 순환 호출한다.
    merge_sort(list, mid+1, right);	//뒤쪽 부분 배열을 정렬하기 위하여 merge_sort한수를 순환 호출한다.
    merge(list, left, mid, right);	//정렬된 2개의 부분 배열을 통합하여 하나의 정렬된 배열로 만든다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))	//temp를 이용해 x와 y값을 스왑

void random(int tempList[], int list[], int n);
void merge_sort(int list[], int left, int right);
void merge(int list[], int left, int mid, int right);

int n = MAX_SIZE;
int sorted[MAX_SIZE];

int main() {
	int list[MAX_SIZE], tempList[MAX_SIZE];

	srand(time(NULL));
	for (int i = 0; i < n; i++)	//난수 생성 및 출력
		list[i] = rand() % 100;
        
	printf("merge sort \n\n");
	random(tempList, list, n);
	merge_sort(tempList, 0, n - 1);	//합병 정렬 호출
	 
	return 0;
}

void random(int tempList[],int list[], int n) {
	for (int i = 0; i < n; i++) {	//난수 재복제
		tempList[i] = list[i];
		printf("%d ", tempList[i]);
	}
	printf("\n");
}

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); // 합병
		for (int j = 0; j < n; j++)
			printf("%d ", list[j]);
		printf("\n");
	}
}

퀵 정렬

퀵정렬은 평균적으로 가장 빠른 정렬 방법으로, 퀵정렬 또한 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵정렬하는 전형적인 분할-정복법을 사용한다.

그러나 합병 정렬과는 달리 퀵정렬은 리스트를 다음과 같은 방법에 의해 비균등하게 분할한다.

리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다.
피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))	//temp를 이용해 x와 y값을 스왑

void random(int tempList[], int list[], int n);
int partition(int list[], int left, int right);
void quick_sort(int list[], int left, int right);

int n = MAX_SIZE;
int sorted[MAX_SIZE];

int main() {
	int list[MAX_SIZE], tempList[MAX_SIZE];

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

	printf("quick sort \n\n");
	random(tempList, list, n);
	quick_sort(list, 0, n - 1);

	 
	return 0;
}

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);
		for (int j = 0; j < n; j++)
			printf("%d ", list[j]);
		printf("\n");
	} 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);
	}
}

히프 정렬

기수 정렬

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))	//temp를 이용해 x와 y값을 스왑

void selection_sort(int list[], int n);
void insertion_sort(int list[], int n);
void bubble_sort(int list[], int n);
void inc_insertion_sort(int list[], int first, int last, int gap);
void shell_sort(int list[], int n);
void random(int tempList[], int list[], int n);
void merge_sort(int list[], int left, int right);
void merge(int list[], int left, int mid, int right);
int partition(int list[], int left, int right);
void quick_sort(int list[], int left, int right);

int n = MAX_SIZE;
int sorted[MAX_SIZE];

int main() {
	int list[MAX_SIZE], tempList[MAX_SIZE];

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

	printf("seletion sort \n\n");
	random(tempList, list, n);
	selection_sort(tempList, n);	//선택정렬 호출
	printf("===========================\n");

	printf("insertion sort \n\n");
	random(tempList, list, n);
	insertion_sort(tempList, n);	//삽입정렬 호출
	printf("===========================\n");

	printf("bubble sort \n\n");
	random(tempList, list, n);
	bubble_sort(tempList, n);	//버블정렬 호출
	printf("===========================\n");

	printf("shell sort \n\n");
	random(tempList, list, n);
	shell_sort(tempList, n);	//쉘 정렬 호출
	printf("============================\n");

	printf("merge sort \n\n");
	random(tempList, list, n);
	merge_sort(tempList, 0, n - 1);	//합병 정렬 호출
	printf("============================\n");

	printf("quick sort \n\n");
	random(tempList, list, n);
	quick_sort(list, 0, n - 1);

	 
	return 0;
}

//선택정렬
void selection_sort(int list[], int n) {
	int i, j, least, temp;
	for (i = 0; i < n - 1; i++) {	//i번째 배열값 기준
		least = i;
		for (j = i + 1; j < n; j++)	//i번째 이상의 배열중 최소값을 값고 있는 least번째 배열 찾기
			if (list[j] < list[least]) least = j;
		SWAP(list[i], list[least], temp);	//i번째 배열과 least번째 배열 스왑
		for (j = 0; j < n; j++)
			printf("%d ", list[j]);
		printf("\n");
	}
}

//삽입정렬
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;

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

//버블정렬
void bubble_sort(int list[], int n) {
	int i, j, temp;
	for (i = n - 1; i > 0; i--) {
		for (j = 0; j < i; j++) {
			if (list[j] > list[j + 1])
				SWAP(list[j], list[j + 1], temp);
			for (int j = 0; j < n; j++)
				printf("%d ", list[j]);
			printf("\n");
		}
		
	}
}

//쉘 삽입정렬
void 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;
		for (int j = 0; j < n; j++)
			printf("%d ", list[j]);
		printf("\n");
	}
}

//쉘 gap
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++; {
			printf("gap : %d\n", gap);
			for (i = 0; i < gap; i++)
				inc_insertion_sort(list, i, n - 1, gap);
		}
	}
}

void random(int tempList[],int list[], int n) {
	for (int i = 0; i < n; i++) {	//난수 재복제
		tempList[i] = list[i];
		printf("%d ", tempList[i]);
	}
	printf("\n");
}

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); // 합병
		for (int j = 0; j < n; j++)
			printf("%d ", list[j]);
		printf("\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);
		for (int j = 0; j < n; j++)
			printf("%d ", list[j]);
		printf("\n");
	} 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);
	}
}

정렬 알고리즘 비교

정렬의 응용 :영어 사전을 위한 정렬

'자료구조' 카테고리의 다른 글

자료구조_10.그래프 (0)	2021.11.26
자료구조_08.트리 (0)	2021.11.12
자료구조_07.연결리스트(원형 연결 리스트) (0)	2021.11.05
자료구조_06.연결 리스트 (0)	2021.10.08
자료구조_04.스택 (0)	2021.10.01

현재글자료구조_12.정렬

GoldTree of C.E