[c언어 문제] #3 난수 배열 정렬, 선택정렬 알고리즘

튜터링 준비하면서 오랜만에 정렬 알고리즘을 사용했는데 기억이 가물가물해져서 정렬 알고리즘 하나씩 우연히 만날 때마다 정리해보겠습니다. 2학기에 알고리즘 수업을 듣게 되는데 그때 아주 도움이 될 것 같습니다 :)

---

문제

길이가 10인 배열을 선언하고 0부터 99까지의 난수를 넣는다. 이를 정렬하여 출력하는 프로그램을 작성하라.

- 배열을 정렬하는 부분을 함수화하라.

---

코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void arrSort(int arr[], int len);
int main(void)
{
	int arr[10], i;

	// 1. 배열에 값 넣기
	srand(time(NULL));
	for (i = 0; i < 10; i++) 
		arr[i] = rand() % 100;

	// 정렬 전 출력
	printf("정렬 전 출력: ");
	for (i = 0; i < 10; i++)
		printf("%d ", arr[i]);
	printf("\n");
	
	// 2. 배열 정렬 -> 함수화
	arrSort(arr, 10);

	return 0;
}

void arrSort(int arr[], int len)
{
	int i, min, minIndex, j, tmp;

	// 선택정렬 : 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가며 정렬.
	for (i = 0; i < len; i++) {
		// i번째를 min으로 두고 i+1번째부터 검사하면서
		// i번째보다 작은 값 있는지 확인! 찐 min을 찾아간다.
		min = arr[i]; 
		minIndex = i;
		for (j = i + 1; j < len; j++) {
			if (arr[j] < min) {
				min = arr[j];
				minIndex = j;
			}
		}
		// arr[i]랑 arr[minIndex] 위치 바꾼다. 
		// 최소값을 가장 앞으로 빼는 과정!
		tmp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = tmp;
	}

	// 정렬 후 출력
	printf("정렬 후 출력: ");
	for (i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

1. 우선 배열 선언하고 값을 넣는다. 값은 0부터 99까지의 난수다. 난수 발생 함수를 호출하고 값을 넣어줄 때 난수 범위를 설정한다. 

 

2. 배열 정렬하는 함수를 별도로 작성한다. 선택정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가며 정렬하는 방법이다. 선택정렬이 뭔지 정확히 알고 있으면 어렵지 않게 코드를 쓸 수 있다.

 

3. 선택정렬은 제자리 정렬 알고리즘의 하나이다. 입력 배열(정렬되지 않은 값들) 이외의 다른 추가 메모리를 요구하지 않는 정렬 방법이다. 어떤 순서에 원소를 넣을 것인지 그 위치는 이미 정해져 있는 것이고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 

 

4. 첫 번째 데이터를 두 번째 데이터부터 마지막 데이터까지 차례로 비교해 가장 작은 값을 찾아 첫 번째 위치에 놓는다. (첫 번째 데이터와 교환) 두 번째 데이터를 세 번째 데이터부터 마지막 데이터까지 차례로 비교해 가장 작은 값을 찾아 두 번째 위치에 놓는다. (두 번째 데이터와 교환) 이 과정을 반복한다.