01. 선택 정렬과 삽입 정렬

선택 정렬의 정의

• 가장 작은 것을 선택하여 앞으로 보내는 정렬 기법
• 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산
  --> O(N^2) 시간 복잡도

선택 정렬의 과정

선택 정렬의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>
#define SIZE 1000

// 배열 선언
int a[SIZE];

// 교환 함수 선언
int swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

int main(void) {
	// n     : 총 숫자의 개수
	// min   : 남은 배열 중 최소값
	// index : 최소값의 인덱스
	int n, min, index;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  
    // 선택 정렬
	for (int i = 0; i < n; i++) {
		min = INT_MAX;
		for (int j = i; j < n; j++) {
			if (min > a[j]) {
				min = a[j];
				index = j;
			}
		}
		swap(&a[i], &a[index]);
	}
  
	// 선택 정렬된 배열 전체 출력
	for (int i = 0; i < n; i++) printf("%d ", a[i]);
	system("pause");
	return 0;
}

삽입 정렬의 정의

• 각 숫자를 적절한 위치에 삽입하는 정렬 기법
• 들어갈 위치를 선택하는 데에 N번, 선택하는 횟수로 N번의 연산
  --> O(N^2)의 시간 복잡도

선택 정렬보다는 약간 빠름

삽입 정렬의 과정

삽입 정렬의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>
#define SIZE 1000

// 배열 선언
int a[SIZE];

// 교환 함수 선언
int swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

int main(void) {
	// n     : 총 숫자의 개수
	// min   : 남은 배열 중 최소값
	// index : 최소값의 인덱스
	int n, min, index;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);

	// 삽입 정렬
	for (int i = 0; i < n - 1; i++) {
		int j = i;
		while (j >= 0 && a[j] > a[j + 1]) {
			swap(&a[j], &a[j + 1]);
			j--;
		}
	}

	// 삽입 정렬된 배열 전체 출력
	for (int i = 0; i < n; i++) printf("%d ", a[i]);
	system("pause");
	return 0;
}