자료구조 공부 #22 (정렬)

 

2021.06.14 - [이론공부/자료구조] - 자료구조 공부 #21 (그래프2)

---

정렬

• 정렬은 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는것
• 컴퓨터 공학을 포함한 모든 과학기술 분야에서 가장 기본적이고 중요한 알고리즘 중 하나
• 정렬은 자료 탐색에 있어서 필수적
  ex) 영어사전에서 단어들이 알파벳 순으로 정렬되있지 않다면 복잡할 것이다.

 

 

정렬의 대상

• 일반적으로 정렬시켜야하는 대상은 레코드(record)
• 레코드는 필드라는 작은 단위로 구성
• 키 필드로 레코드와 레코드를 구별함

레코드(record) 구성예시

 

정렬 알고리즘 개요

• 모든 경우의 최적인 정렬 알고리즘은 존재하지 않는다.
  
  
• 각 응용 분야에 적합한 정렬 방법을 사용해야 함
  • 레코드 수의 많고 적음
  • 레코드 크기의 크고 작음
  • key의 특성 (문자, 정수, 실수)
  • 메모리 내부/외부 정렬
    
    
• 정렬 알고리즘의 평가 기준
  • 비교 횟수의 많고 적음
  • 이동 횟수의 많고 적음
• 단순하지만 비효율적인 방법
  • 삽입정렬, 선택정렬, 버블정렬 등
• 복잡하지만 효율적인 방법
  • 퀵 정렬, 힙 정렬, 병합(합병) 정렬, 기수 정렬

정렬의 종류와 특징

 

• 내부 정렬
  
  • 모든 데이터가 주기억장치에 저장되어진 상태에서 정렬
• 외부 정렬
  • 외부 기억장치에 대부분의 데이터가 있고 일부만 주기억장치에 저장된 상태에서 정렬

정렬 알고리즘의 안정성

• 동일한 키 값을 갖는 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않음

안정하지 않은 정렬예시

선택 정렬

정렬된 왼쪽 리스트와 정렬안된 오른쪽 리스트 가정

 - 초기에는 왼쪽 리스트는 비어있고, 정렬할 숫자들은 모두 오른쪽 리스트에 존재

 

C++ 구현코드

#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];

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

 

선택 정렬 복잡도 분석

 

삽입정렬

 

알고리즘

 

복잡도 분석

삽입 정렬의 경우 잘 사용하지 않는다

잘 사용하지 않는 정렬 방식으로 알고만 있자

 

 

버블 정렬

앞뒤 인접 레코드를 비교하여 순서를 바꿔 정렬하고 이를 반복하는 방식

 

알고리즘과 구현 코드

 

복잡도 분석

 

셸 정렬

 

셸 정렬 C++ 구현 코드

기존에 사용한 삽입정렬 함수를 그대로 인용한다

복잡도 분석

 

장점

• 불연속적인 부분 리스트에서 원거리 자료 이동으로 보다 적은 위치 교환으로 제자리를 찾을 가능성 증대
• 부분 리스트가 점진적으로 정렬된 상태가 되므로 삽입 정렬 속도 증가

시간복잡도

 최악의 경우 : O(n^2)

 평균적 경우 : O(^1.5)

 

 

병합(합병) 정렬

분할 -> 정렬 -> 합병 하는 방식

 

 

 

 

 

알고리즘

 

 

C++ 구현 코드

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

#define MAX_SIZE 10

int list[MAX_SIZE];
int sorted[MAX_SIZE]; 

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

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

	for (i = 0; i < n; i++) 
		list[i] = rand() % 100;

	merge_sort(list, 0,9); // 병합정렬 호출

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

	printf("\n");
	return 0;
}

 

 

복잡도 분석

---

퀵 정렬

알고리즘

재귀 호출 방식을 이용함

 

코드, 알고리즘 작동과정 설명

 

C++ 구현 코드

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 (low <= right && list[low] < pivot);
		do
			high--;
		while (high >= left && 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;
}

 

복잡도 분석

최선의 경우

최악의 경우

 

힙 정렬

2021.05.25 - [이론공부/자료구조] - 자료구조 공부#19 (우선순위 큐, 힙)

자료구조 공부#19 (우선순위 큐, 힙)

이전 우선순위큐, 힙 관련 내용을 확인하자

down heap 알고리즘으로 실행 (최대힙 기준)

 

 

기수 정렬

여기서 버켓은 큐 구조를 갖는다

2자리수의 경우 자릿수에 따라 버킷을 나누는 형식으로 작동

 

데이터 형식에 따라 버켓 개수는 달라진다.

C++ 코드 구현

#define BUCKETS 10
#define DIGITS 4
void radix_sort(int list[], int n) {
	int i, b, d, factor = 1;
	QueueType queues[BUCKETS];
	for (b = 0; b < BUCKETS; b++) init(&queues[b]); // 큐들의 초기화
	for (d = 0; d < DIGITS; d++) {
		for (i = 0; i < n; i++) // 데이터들을 자리수에 따라 큐에 입력
			enqueue(&queues[(list[i] / factor) % 10], list[i]);
		for (b = i = 0; b < BUCKETS; b++) // 버켓에서 꺼내어 list로 합친다.
			while (!is_empty(&queues[b]))
				list[i++] = dequeue(&queues[b]);
		factor *= 10; // 그 다음 자리수로 간다.
	}
}

#define SIZE 10
int main(void) {
	int list[SIZE];
	srand(time(NULL));
	for (int i = 0; i < SIZE; i++) // 난수 생성 및 출력
		list[i] = rand() % 100;
	radix_sort(list, SIZE); // 기수정렬 호출
	for (int i = 0; i < SIZE; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

 

 

복잡도 분석

---

전체 정렬 알고리즘 복잡도 비교

평균적으로 퀵정렬, 힙정렬, 합병정렬이 괜찮은거 같다