[알고리즘][정렬] 선택 정렬

선택 정렬

정의

출처- https://visualgo.net/ko

• 정렬되지 않은 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식

가장 작은 것을 선택해서 제일 앞으로 보낸다

초록색이 순회하며 정렬되지 않은 부분들 중에서 최솟값을 찾는다. 최솟값과 현재 위치인 빨간색을 비교하여 더 작은 키 값을 빨간색과 교환한다. 정렬이 된 부분은 노란색으로 변한다.

구현1

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
void printArray(int value[], int count) {
	int i = 0;
	for (i = 0; i < count; i++) {
		printf("%d ", value[i]);
	}
	printf("\n");
}

void selectionSort(int value[], int count) {
	int i = 0, j = 0;
	int min = 0, temp = 0;
	for (i = 0; i < count - 1; i++) {
		min = i;	
		for (j = i+1; j < count; j++) {
			if (value[j] < value[min]) {
				min = j;
			}
		}
		temp = value[i];
		value[i] = value[min];
		value[min] = temp;

		printf("Step-%d ", i + 1);
		printArray(value, count);
	}
}

int main() {
	int values[] = { 5,3,8,1,2,7 };
	printf("Before Sort\n");
	printArray(values, 6);
	
	selectionSort(values, 6);

	printf("After Sort\n");
	printArray(values, 6);
}

구현2

#include <stdio.h>
#pragma warning(disable:4996)
int main(void) {
	int i, j, min, index, temp;
	int array[10] = { 1,10,5,8,7,6,4,3,2,9 };
	for (i = 0; i < 10; i++) {
		min = 9999;
		for (j = i; j < 10; j++) {
			if (min > array[j]) {
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}
	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
}

구현3

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define MAX_SIZE 10
#define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
int list[MAX_SIZE];
int n;
void selection_sort(int list[], int n) {
	int i, j, least, temp;
	for (i = 0; i < n - 1; i++) {
		least = i;
		for (j = i + 1; j < n; j++) {
			if (list[j] < list[least])
				least = j;
		}
		SWAP(list[i], list[least], temp);
	}
}
int main(void) {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i < n; i++) {
		list[i] = rand() % 100;
	}
	selection_sort(list, n);
	for (i = 0; i < n; i++) {
		printf("%d ", list[i]);
	}
	printf("\n");
}

특성

• 최선,평균,최악: O($n^2$)
• 알고리즘의 효율성이 매우 느림
• 정렬의 안정성을 만족하지 않음

-참고 자료

• visual algorithm
• 열혈 강의 자료구조
• C언어로 쉽게 풀어쓴 자료구조
• 나동빈 알고리즘