선택 정렬 구현하기

전체 코드

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include "vld.h"

#define MAX_VALUE 30

void select_sort(int arr[], int size);
void swap(int* a, int* b);
int* generate_random_arr(int size);
void print_arr(int arr[], int size);

int main(void)
{
	srand((unsigned)time(NULL));
	const int SIZE = 10;
	int* arr = generate_random_arr(SIZE);
	print_arr(arr, SIZE);

	select_sort(arr, SIZE);
	print_arr(arr, SIZE);

	free(arr);
}

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void select_sort(int arr[], int SIZE)
{
	int min_idx;
	for (int i = 0; i < SIZE; i++) {
		min_idx = i;

		for (int j = i + 1; j < SIZE; j++) {
			if (arr[min_idx] >= arr[j])
				min_idx = j;
		}

		swap(&arr[i], &arr[min_idx]);
	}
}

int* generate_random_arr(int size)
{
	int* arr = (int*)malloc(sizeof(int) * size);
	if (arr == NULL) return NULL;

	for (int i = 0; i < size; i++)
		arr[i] = rand() % MAX_VALUE + 1;
	return arr;
}

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

설명

swap, generate_random_arr, print_arr 함수는 지난 포스팅 '[Data Structure] 버블 정렬 (Bubble Sort) 구현하기, 개선된 버블 정렬' 에서 설명했으므로 생략한다.

void select_sort(int arr[], int SIZE)

선택 정렬을 수행하는 함수. 매 반복(바깥쪽 반복문)마다 최솟값을 선택하여(안쪽 반복문) 정렬한다.

void select_sort(int arr[], int SIZE)
{
	int min_idx;
	for (int i = 0; i < SIZE; i++) {
		min_idx = i;

		for (int j = i + 1; j < SIZE; j++) {
			if (arr[min_idx] >= arr[j])
				min_idx = j;
		}

		swap(&arr[i], &arr[min_idx]);
	}
}

시간 복잡도는 빅오 표기법으로 O(n^2)이다.

이전의 버블 정렬과는 다르게 비교 값이 같은 경우에 기존의 순서가 파괴될 수 있기 때문에 불안정한 정렬이다.

선택 정렬을 안정 정렬로 구현할 수 있다. 삽입 정렬처럼 찾은 값을 삽입하며 모든 원소를 한 칸씩 뒤로 이동하는 것이다. 필요하다면 사용할 방법이지만 그렇게 효과적인진 모르겠다.

실행 결과