[C언어] 정렬 알고리즘 (버블정렬, 선택정렬)

컴퓨터는 한 번에 두 개의 수만 비교할 수 있다. 컴퓨터상에서의 대표적인 정렬방법인 버블정렬과 선택정렬에 대해 알아보자. 

1. 버블정렬

버블정렬의 과정은 다음과 같다. 

1. 첫 번째 숫자와 두 번째 숫자를 비교한다. 더 작은 수가 앞에, 큰 수가 뒤에 오도록 위치를 바꾼다. 

2. 두 번째 숫자와 세 번째 숫자를 비교한다.

3. 세 번째 숫자와 네 번째 숫자를 비교한다. 

.

.

.

4. 마지 막번째 수를 비교할 때까지 위 과정을 반복한다. 

.

5. 위 과정을 마치면 제일 큰 수가 맨 뒤로 가있을 것이다. 그러면 잘 정렬된 맨뒤의 수를 빼고 나머수들로 위 과정을 반복한다. 더 이상 비교할 나머지 수가 없으면 정렬 끝!

 

#include <stdio.h>

int main(void)
{
	int arr[10] = { 10, 8, 3, 7, 2, 6, 4, 9, 1, 5 };

	int temp;

	for (int i = 1; i < 10; i++) {
		for (int j = 0; j < 10 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	for (int i = 0; i < 10; i++) printf("%d", arr[i]);

	return 0;
}

버블정렬 코드는 한 번에 이해가 가지 않았다. 이중 for문으로 실행 범위를 잘 설정해 주는 게 중요하다. 비교하는 범위가 끝에서부터 점점 줄어든다고 생각하니까 이해가 조금 편했다. 

참고 유튜브 링크: https://youtu.be/fxuhgRRqYsY

2. 선택정렬

선택정렬은 최솟값을 찾아서 그 수를 맨 앞으로 옮기는 과정의 반복이다. 버블정렬과 다른점은 버블정렬은 비교 될 때 마다 값을 바꿔주지만 선택정렬은 임시변수에 위치(index)를 담아두고 최솟값을 찾을 때까지 계속 비교한 후 값을 바꿔준다.  

 

선택정렬 과정은 다음과 같다.

1. 첫 번째 값을 최솟값이라 가정한다. 

2. 나머지 수들과 차례대로 비교하면서 최솟값을 찾는다.

3. 최솟값을 맨 앞으로 이동시킨다.

4. 두 번째 값을 최솟값이라 가정한다. 

. 

.

. 

5. 위 과정을 반복하고 더 이상 비교할 수들이 남아있지 않으면 정렬 끝!

 

#include <stdio.h>

int main(void)
{
	int arr[10] = { 10, 8, 3, 7, 2, 6, 4, 9, 1, 5 };
	int temp;
	int min_i; // 최솟값의 인덱스 

	for (int i = 0; i < 10; i++) {
		min_i = i;
		for (int j = i; j < 10; j++) {
			if (arr[j] < arr[min_i]) {
				min_i = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[min_i];
		arr[min_i] = temp;
	}

	for (int i = 0; i < 10; i++) printf("%d", arr[i]);

	return 0;
}