자료구조 - 정렬 모음

정렬 종류

• 삽입정렬 (insert sort)
• 선택 정렬 (select sort)
• 거품 정렬 (buble sort)
• 셀 정렬 (cell sort)
• 합병 정렬 (merge sort)
• 힙 정렬, 큐 (heap sort, queue)
• 퀵 정렬, (quick sort)
• 기수 정렬 (radix sort)
• 계수 정렬 (counting sort)

1. 삽입정렬 (insert sort)

• 개념
  손안의 카드를 정리하는 방식을 착안한 것으로 어떤 카드를 정리할 때 특정 카드를 정렬된 카드들과 순차별로 비교하여 특정카드의 위치를 파악한다.

• 코드

void insertSort(int arr[], int n) {
	int key, i, j;
	for (i = 1; i < n; i++) {//index 1 부터 모두 확인
		key = arr[i];
		for (j = i - 1; j >= 0 && key < arr[j]; j--) { // key의 값보다 크면 인덱스를 +1 이동
			arr[j + 1] = arr[j];
		}// 아니라면 그 위치가 key가 있어야할 위치
		arr[j + 1] = key; //외부에서 j를 정의했기 때문에 for문 밖에서도 사용가능
	}
}

• 시간복잡도
  O(n^2)

• 공간복잡도
  O(n)

• 특징
  배열이 작을수록 효율적임

2. 선택 정렬 (select sort)

• 개념
  배열의 최솟값을 찾고 이를 순차대로 정렬한다.

• 코드

void selectSort(int arr[], int n) {
	int indexMin, temp; // 최솟값 인덱스
	for (int i = 0; i < n - 1; i++) {
		indexMin = i;
		for (int j = i + 1; j < n; j++) {
			if (arr[indexMin] > arr[j]) {
				indexMin = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[indexMin];
		arr[indexMin] = temp;
	}
}

• 시간복잡도
  O(n^2)

• 공간복잡도
  O(n)

3. 거품 정렬 (buble sort)

• 개념
  인접한 두 index(j, j+1)를 비교하면서 순차적으로 정렬한다.

• 코드

void bubbleSort(int arr[], int n) {
	int temp;
	for (int i = 0; i < n; i++) {//회수
		for (int j = 0; j < n - 1-i;j++) { 
			if (arr[j] > arr[j + 1]) {// 인접한 인덱스 비교
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

• 시간복잡도
  O(n^2)

• 공간복잡도
  O(n)

• 특징
  배열이 정리되어 있을수록 효율적임

4. 셀 정렬 (cell sort)

• 개념
  삽입 정렬(insert sort)의 보완형, 삽입 정렬의 경우 값의 이동이 인접한 index+1만 가능, 만약 이동해야할 위치가 멀리 떨어져있을수록 cost(write)가 많이듬 이를 해결하기 위한 방법으로

void shellSort(int arr[], int n) {
	int i, k, j, gap, value;
	for (gap = n / 2; gap > 0; gap /= 2) {
		if (gap % 2 == 0) {
			gap++;
		}
		for (i = 0; i < gap; i++) { // gap으로 나눈 기준까지
			for (j = i + gap; j < n; j += gap) { //인덱스 정렬 시작
				value = arr[j]; // 기준이 되는 인덱스 이자, 변경할 값 
				for (k = j - gap; k >= i && arr[k] > value; k -= gap) {//기준이 되는 j의 인덱스 아래로 정렬진행
					arr[k + gap] = arr[k]; //  값들을 순차대로 정렬
				}
				arr[k + gap] = value; // 맨 마지막 값을 업데이트 해줌!!
			}
		}
	}
}

• 평균 시간복잡도
  O(n^1.5)

• 공간복잡도
  O(n)

• 특징
  교환되어야 할 값들이 멀리 떨어져있을때 삽입 정렬보다 cost가 적게 든다.

5. 합병 정렬 (merge sort)

void merge(int arr[], int first, int mid, int last) {
	int i, j, k, l;
	i = first;
	j = mid + 1;
	k = first;
	while (i <= mid && j <= last) {
		if (arr[i] > arr[j]) {
			sort[k++] = arr[j++];
		}
		else {
			sort[k++] = arr[i++];
		}

	}
	if (i > mid) {// i쪽만 값을 넣었을때 j의 값을 모두 넣는다.
		for (l = j; l <= last; l++) {
			sort[k++] = arr[l];
		}
	}
	else {
		for (l = i; l <= mid; l++) {
			sort[k++] = arr[l];
		}
	}
	for (l = first; l <= last; l++) {
		arr[l] = sort[l];
	}
}

void mergeSort(int arr[], int first, int last) {
	int mid;
	if (first < last) {
		mid = (first + last) / 2;
		mergeSort(arr, first, mid);
		mergeSort(arr, mid + 1, last);
		merge(arr, first, mid, last);
	}
}

6. 힙 정렬, 큐 (heap sort, queue)

7. 퀵 정렬, (quick sort)

8. 기수 정렬 (radix sort)

9. 계수 정렬 (counting sort)