[📗c언어 쉽게 풀어쓴 자료구조12] 정렬

정렬이란?

: 크기순으로 오름차순이나 내림차순으로 나열하는 것 (보통 '레코드'들을 정렬함)

• key: 레코드와 레코드를 구별 해주는 값
  & 안정성에 따른 알고리즘 분류
• 안정성: 같은 키 값을 같는 레코드들이, 정렬 후에도 그 위치가 변하지 않는 것
• 안정성 충족하는 정렬: 삽입 정렬, 버블 정렬, 합병 정렬

👑 선택 정렬

1. 2개의 리스트: 가장 작은 숫자 선택해서 오른쪽 리스트에서 왼쪽 리스트로 이동
2. 제자리 정렬: 가장 작은 숫자를 찾아서 맨 앞의 인덱스와 교환 (그 다음에는 두 번째 인덱스와 교환,,세번째...)

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

👑 삽입 정렬

: 두번째 값부터 앞의 값들과 비교하며, key값이 더 작은 경우에는 그 위치에 있는 것들을 한 칸씩 뒤로 밀며, 적절한 위치에 삽입

• 최솟값부터 앞 쪽에 정렬 완성

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

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

👑 버블 정렬

: 인접한 2개의 레코드들 비교하여 큰 것이 뒤로 가도록

• 최댓값부터 뒷쪽에 정렬 완성

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

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

👑 쉘 정렬

: 부분리스트로 나누어, 각각 정렬 후 합침. 많이 이동해야하는 삽입 정렬 보완 (gap의 값을 줄여가며)- 부분리스트는 삽입 정렬

• 부분리스트의 갯수는 gap과 같음

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

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 - 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) { //다음 gap으로 넘어감
		if ((gap % 2) == 0) gap++;
		for (i = 0;i < gap;i++)   //각 gap에서 다음 부분리스트로 넘어감
			inc_insertion_sort(list, i, n - 1, gap);
	}
}

👑 합병 정렬

: 하나의 리스트를 2개의 균등한 크기로 분할하고, 부분리스트를 정렬한 후 합함 (분할정복 방법- 순환호출 이용)

• 실질적인 정렬은 합병 단계에서 이루어짐

👑 퀵 정렬

: 피벗을 기준으로 하는 분할 정복법 (작은 거 왼쪽으로, 큰 거 오른쪽으로 이동 후, 다시 피벗 정해서)

👑 히프 정렬

: 최소 히프 (완전 이진 트리)를 이용하여, 최솟값을 먼저 삭제하여 맨 앞에 정렬

👑 기수 정렬

: 레코드들을 비교하지 않고, 추가적인 메모리를 통해서 정렬. (버킷 만들어서 넣기)

• 정수 정렬에서 유리 (2자리 수인 경우, 일의 자리를 기준으로 먼저 버킷에 넣은 후 순서대로 빼서 정렬-> 십의 자리를 기준으로 버킷에 넣은 후, 순서대로 빼서 정렬)
• 각각의 버킷은 큐로

👑 정렬 알고리즘 비교

!! 각 경우에 맞게 가장 효율적인 정렬 알고리즘을 선택하는 것이 중요함!! (효율성: 비교 횟수, 이동 횟수- 자료의 개수가 많을수록 효율적인 알고리즘 사용하는 것 더 중요)
!! 퀵 정렬이 가장 빠름

⭕ TIL (Today I Learned)

& 정렬은 레코드들을 순서에 따라서 정렬하는 것임. 각각의 경우에 맞는 효율성이 높은 정렬 알고리즘을 선택하는 것이 중요함. 정렬 알고리즘의 종류는 여러 개가 있다.
1. 선택 정렬: 최솟값을 선택하여 앞의 인덱스로 가져와서 넣는 것 (하나 씩 뒤로 밀기)
2. 삽입 정렬: 두번째 요소부터 앞의 요소들과 비교하며 제자리에 넣는 것 (최솟값부터 정렬 완성)
3. 버블 정렬: 옆의 요소들과 비교해가며 큰 수를 오른 쪽으로 이동 (큰 수부터 정렬 완성)
4. 쉘 정렬: 부분리스트를 만들어, 각 부분리스트를 삽입 정렬 후 합침 (gap에 따라 부분리스트의 갯수 정해짐) gap을 줄여가며 1이 될 때까지 반복
5. 합병 정렬: 분할정복법으로(보통 가운데 값을 기준으로 함), 전체리스트를 부분리스트로 분할하여, 각 부분을 정복 후-순환호출, 합병 함(합병 과정에서 정렬 일어남)
6. 퀵 정렬: 피벗을 기준으로 작은 것은 왼쪽, 큰 것은 오른쪽에 삽입 (그 각각을 또 순환호출을 통해 정렬)
7. 히프 정렬: 최소 히프의 삭제 연산을 통해서, 앞부터 정렬
8. 기수 정렬: 비교를 하는 것이 아닌, 버킷을 이용해, 자료들을 저장하고 순서대로 빼내어 정렬 (정수의 정렬에 유리)