정렬 알고리즘: 선택, 삽입, 버블, 쉘, 합병, 퀵 정렬

 

선택 정렬

 

오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 반복한다.

 

1. 입력 배열에서 최솟값을 발견한 다음, 이 최솟값을 배열의 첫번째 요소와 교환한다.

2. 첫번째 요소를 제외한 나머지 요소들 중에 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다.

3. 이 절차를 숫자 개수-1 만큼 되풀이 한다.

 

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

void selection_sort(int list[], int n)
{
	int i, j, least, tmp;
	for (i = 0; i < n - 1; i++) {
		least = i; // 최솟값 인덱스
		for (j = i + 1; j < n; j++) { // 인덱스 i+1 부터 끝가지 가장 작은 값의 인덱스 찾기
			if (list[j] < list[least]) least = j;
		}
		if(i!=least) // 최솟값이 자기 자신이 아닐때만 자료 이동
			SWAP(list[i], list[least], tmp); // 가장 작은 값과 i값 교환
	}
}

 

 

삽입 정렬

 

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

 

1. 정렬되어 있지 않은 부분의 첫 번째 숫자(key)가 정렬된 부분의 어느 위치에 삽입되어야 하는지 찾는다.

2. 해당 위치에 이 숫자를 삽입한다. 정렬된 부분의 크기는 하나 커지고, 정렬이 되지 않은 부분의 크기는 하나 줄어들게 된다.

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--) // 인덱스 i-1부터 0까지 list[j]가 key보다 크다면 
			list[j + 1] = list[j]; // list[j]를 뒤로 한칸 이동
		list[j + 1] = key; // j번째 정수가 key보다 작으므로 j+1번째에 key값을 삽입
	}
}

 

 

 

버블 정렬

 

인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 전체 숫자가 전부 정렬될때까지 이러한 비교-교환 과정을 반복한다.

 

1. 인접한 두개의 레코드를 비교해 크기가 순서대로 되어 있지 않으면 서로 교환한다.

2. 이 과정을 왼쪽 끝 부터 오른쪽 끝까지 진행하면 한번의 스캔에 의해 가장 큰 레코드가 오른쪽 끝으로 이동하게 된다.

3. 자기 자리에 위치한 맨 오른쪽 레코드를 제외한 나머지 왼쪽 리스트를 대상으로 이 과정을 반복한다.

 

 

void bubble_sort(int list[], int n)
{
	int i, j, tmp;
	for (i = n - 1; i > 0; i--) {
		for (j = 0; j < i; j++) { // 하나의 스캔은 j=0부터 j=i-1까지 
			if (list[j] > list[j + 1]) // 인접한 데이터가 크기 순으로 되어있지 않으면 교환
				SWAP(list[j], list[j + 1], tmp);
		}
	}
}

 

 

쉘 정렬

 

먼저 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고,

각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이 한다. 

 

1. 입력 리스트의 k번째(n/2) 요소를 추출하여 부분 리스트들을 만든다.

2. 각각의 리스트에 대해 삽입 정렬이 수행된다.

3. 간격(k)을 1/2 줄여서 부분 리스트들을 만들어 정렬하는 과정을 간격이 1이 될 때까지 반복한다. 

 

 

장점 

 

교환되는 아이템들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다. 

부분리스트는 어느정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되었을 때 수행되는 삽입 정렬이 빠르다.

 

 

// gap 만큼 떨어진 요소들을 삽입 정렬
int gap_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)
{
	int i, gap;
	for (gap = n / 2; gap > 0; gap = gap / 2) {
		if ((gap % 2) == 0) gap++; // 간격이 짝수면 1을 더하는 것이 좋은 것으로 분석됨
		for (i = 0; i < gap; i++) // 부분 리스트의 개수는 gap
			gap_insertion_sort(list, i, n - 1, gap);
	}
}

 

 

 

합병 정렬

 

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는다.

 

1. 분할: 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

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

3. 결합: 정렬된 부분 배열들을 하나의 배열에 통합한다.

 

 

int sorted[100];

void merge(int list[], int left, int mid, int right)
{
	int i, j, k, l;
	i = left; j = mid + 1; k = left;

	while (i <= mid && j <= right) {
		// 두 리스트 i, j번째 원소 중 작은 걸 sorted 배열로 옮김 
		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 = left; l <= mid; l++)
			sorted[k++] = list[l]; // 왼쪽 리스트의 남아있는 원소들을 모두 복사
	 
	for (l = left; l <= right; l++) // 배열 sorted의 리스트를 배열 list로 재복사
		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);
	}
}

 

 

 

퀵 정렬

 

리스트 안의 한 요소를 피벗으로 선택하고, 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.

이 상태에서 두 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.

 

1. 피벗을 기준으로 피벗 보다 작은 요소들은 왼쪽 리스트, 큰 요소들은 오른쪽 리스트 이렇게 2개의 리스트로 분할한다. 

2. 2개의 부분 리스트가 각각 순환 호출되어 다시 피봇을 정하고 피봇을 기준으로 2개의 부분 리스트로 나눈다.

3. 위의 과정을 부분 리스트들이 더이상 분할이 불가능 할때까지 반복한다. 

 

 

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

	low = left; // do-while 루프에서 먼저 증가를 시키므로
	high = right + 1; // do-while 루프에서 먼저 감소를 시키므로
	pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택

	do {
		do
			low++;
		while (list[low] < pivot); // low는 왼쪽에서 오른쪽으로 탐색해가다가 피벗보다 큰 데이터를 찾으면 멈춤 
		do
			high--;
		while (list[high] > pivot); // high는 오른쪽 끝에서 왼쪽으로 탐색해가다가 피벗보다 작은 데이터를 찾으면 멈춤 
		if (low < high) { // low와 high가 아직 교차하지 않았으면 
			SWAP(list[low], list[high], temp); // list[low]와 list[high]를 교환
		}
	} while (low < high); // low와 high가 교차하였으면 반복을 종료

	SWAP(list[left], list[high], temp); // 피봇을 중앙에 위치시킴 
	return high; // 피봇의 위치를 반환 
}

void quick_sort(int list[], int left, int right)
{
	if (left < right) { // 정렬할 범위가 2개 이상의 데이터이면 
		int q = partition(list, left, right); // 피벗을 기준으로 2개의 리스트로 분할 후 피봇의 위치 반환 
		quick_sort(list, left, q - 1); // left에서 피봇 위치 바로 앞까지의 대상으로 순환 호출
		quick_sort(list, q + 1, right); // 피봇 위치 바로 다음부터 right 까지를 대상으로 순환 호출 
	}
}