[알고리즘] 선택,삽입 정렬

모든 정렬은 오름차순을 기준으로 한다.

1. 선택정렬

선택정렬은 아래와 같은 행동을 반복한다.

1. n번째 인덱스(기준이 되는 값)와 n+1인덱스와 값을 비교한다.
2. n+1인덱스의 값이 더 큰 경우 두 값을 바꾼다.
3. 이번엔 n번째 인덱스와 n+2의 값을 비교한다.
4. 이 행동을 마지막 인덱스까지 반복한다.

1~4의 과정을 마치고 난 후 n을 n+1(기준이 되는 값)로 변경한다.그리고 다시 1~4를 반복 후 n+2로 변경 다시 1~4 ........
기준이 되는 인덱스가 (배열의 마지막 -1)이 될 때까지 반복

선택정렬 코드

#include <Stdio.h>
#pragma warning (disable:4996)

void printArr(int arr[5]);

void main() {
	int arr[5] = { 2, 3, 5, 1, 4 },cnt=1;

	printf("정렬 전 : ");
	printArr(arr);

	for (int i = 0; i < 4; i++)
		for (int j = i + 1; j < 5; j++) {
			printf("%d : ", cnt++);
			if (arr[i] > arr[j]) {
				int tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
			}
			printArr(arr);
		}
}

void printArr(int arr[5]) {
	for (int i = 0; i < 5; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

2. 삽입정렬

삽입정렬은 아래와 같은 행동을 반복한다.

1. n번째 인덱스(기준이 되는 값, n > 0)와 n-1인덱스와 값을 비교한다.
2. n-1인덱스의 값이 더 큰 경우 두 값을 바꾼다. 만약 크지않는 경우 기준이 되는 인덱스를 n->n+1로 바꿔준다. 그리고 1부터 다시 시작
3. 이번엔 n-1번째 인덱스와 n-2의 값을 비교한다.
4. 1번째 인덱스와 비교할 때 까지한다.

1~4의 과정을 마치고 난 후 n을 n+1(기준이 되는 값)로 변경한다.그리고 다시 1~4를 반복 후 n+2로 변경 다시 1~4 ........
기준이 되는 인덱스가 배열의 마지막이 될 때까지 반복

삽입정렬 코드

#include <Stdio.h>
#pragma warning (disable:4996)

void printArr(int arr[5]);

void main() {
	int arr[5] = { 2, 3, 5, 1, 4 },cnt=1;

	printf("정렬 전 : ");
	printArr(arr);

	for (int i = 1; i < 5; i++)
		for (int j = i; j > 0; j--) {
			printf("%d : ", cnt++);
			if (arr[j] < arr[j - 1]) {
				int tmp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = tmp;
				printArr(arr);
			}
			else{
				printArr(arr);
				break;
			}
		}
}

void printArr(int arr[5]) {
	for (int i = 0; i < 5; i++)
		printf("%d ", arr[i]);
	printf("\n");
}