정렬 (1)

[출처]

book.naver.com/bookdb/book_detail.nhn?bid=10896666

C로 배우는 쉬운 자료구조

​

​

목차

01 정렬이란

02 선택 정렬

03 버블 정렬

04 퀵 정렬

05 삽입 정렬

06 셸 정렬

07 병합 정렬

08 기수 정렬

09 히프 정렬

10 트리 정렬

​

​

01. 정렬이란

◆ 정렬(Sort) : 순서 없이 배열된 자료를 오름차순(작은 것 → 큰 것), 내림차순(큰 것 → 작은 것)으로 재배열하는 것

▶ 키 : 자료를 정렬하는 데 사용하는 기준이 되는 특정값

▶ 정렬 방법

실행 방법	비교식 정렬	비교할 키 값을 한 번에 2개씩 비교 → 교환 ⇒ 정렬
	분배식 정렬	자료를 키값을 기준으로 여러 개의 부분집합으로 분해 → 각 부분집합 정렬 ⇒ 전체 정렬
정렬 장소	내부 정렬	컴퓨터 메모리 내부에서 정렬
	외부 정렬	보조 기억 장치(메모리 외부)에서 정렬

​

· 내부 정렬 : 정렬할 자료를 메인 메모리에 올려 정렬하는 방식

- 속도 : 빠름

- 양 : 메모리 용량에 따라 제한

- 종류

비교식	교환 방식	키 비교, 교환 선택 정렬, 버블 정렬, 퀵 정렬
	삽입 방식	키 비교, 삽입 삽입 정렬, 셸 정렬
	병합 방식	키 비교, 병합 2-way 병합, n-way 병합
	선택 방식	이진 트리 사용 히프 정렬, 트리 정렬
분배식	분배 방식	키를 구성하는 값을 여러 개의 부분집합에 분배 기수 정렬

· 외부 정렬 : 파일을 부분 파일로 분리 → 각각 내부 정렬 방법으로 정렬 → 병합하는 방식

- 속도 : 내부정렬보다 느림 ( ∵ 보조 기억 장치 사용 )

- 양 : 내부정렬보다 많음 ( ∵ 보조 기억 장치 대용량으로 사용 가능 )

- 종류 : 2-way 병합, n-way 병합

​

02. 선택 정렬

◆ 선택 정렬 : 전체 원소 中 기준 위치에 맞는 원소 선택 → 자리 교환

- 공간 복잡도 : n ( ∵ 메모리 n개 사용 )

- 전체 비교 횟수 :

첫째 원소 기준으로 가장 작은 원소 찾기 → (n-1)개의 원소 비교

둘째 원소 기준으로 가장 작은 원소 찾기 → (n-2)개의 원소 비교

…

∴ (n-1) + (n-2) + (n-3) + … + 2 + 1 = (n-1)*n / 2

- 시간 복잡도 : O(n2) ← 어떤 경우에서나 비교 횟수 같음

​

ⅰ) 전체 원소 中 가장 작은 원소 찾기 → 첫째 원소와 자리 교환

ⅱ) 두번째로 작은 원소 찾기 → 둘째 원소와 자리 교환

ⅲ) 반복

​

​

#include <stdio.h>
typedef int element;
int size;

void SelectionSort(int a[], int size) {
	int i, j, t, min;
	element temp;
	
	//정렬 전 원소 츌력
	for (t = 0; t < size; t++)
		printf("%3d", a[t]);

	//정렬
	for (i = 0; i < size; i++) {
		min = i;
		for (j = i + 1; j < size; j++) {
			if (a[j] < a[min])
				min = j;
		}
		temp = a[i];
		a[i] = a[min];
		a[min] = temp;
	}
	printf("\n");
	//정렬 후 원소 출력
	for (t = 0; t < size; t++)
		printf("%3d", a[t]);
}

int main() {
	element list[7] = { 4,15,1,6,10,8,11 };
	size = 7;
	SelectionSort(list, size);

	return 0;
}

 

​

​

03. 버블 정렬

◆ 버블 정렬 : 인접한 원소 두 개를 비교,자리 교환 → 반복

- 공간 복잡도 : n ( ∵ 메모리 n개 사용 )

- 전체 비교 횟수 : 1 + 2 + … + (n-1) = (n-1)*n / 2

- 시간 복잡도 : O(n2) ←최악의 경우, 최선의 경우의 평균

연산시간 가장 짧은 경우(최선) : 자료들이 이미 정렬

연산시간 가장 긴 경우(최악) : 자료들이 역순으로 정렬

​

ⅰ) 1단계 : 첫째 원소 ~ 마지막 원소까지 차례로 버블 정렬 수행 → 가장 큰 원소가 마지막 자리로 정렬

ⅱ) 정렬하지 않은 원소에 대해 두 번째 버블 정렬 수행 → 나머지 원소 중 가장 큰 원소가 끝에서 둘째 자리로 정렬

ⅲ) 반복

3단계

4단계

5단계

6단계

#include <stdio.h>
typedef int element;
int size;

void bubbleSort(element a[], int size) {
	int i, j, t;
	element temp;

	for (t = 0; t < size; t++) {
		printf("%3d", a[t]);
	}
	
	for (i = size - 1; i > 0; i--) {
		for (j = 0; j < i; j++) {
			if (a[j] > a[j + 1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
	printf("\n");
	for (t = 0; t < size; t++) {
		printf("%3d", a[t]);
	}
}

int main() {
	element list[7] = { 30, 5, 11, 25, 18, 22, 1 };
	size = 7;
	bubbleSort(list, size);

	return 0;
}

​

 

​

​

​