[정렬] 선택 정렬

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

 

선택 정렬(Selection Sort)

Selection Sort

1. 배열 중 가장 작은 값을 찾는다.
2. 배열의 첫번째 값과 교환한다.
3. 첫번째 배열을 제외한 나머지 배열을 가지고 1~3을 반복한다.

 

시간 복잡도 : O(n^2)

 

---

 

소스코드

#define __main

#ifdef __main

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

#define MAX_SIZE 10

void Init(int arr[]) {
	srand(time(NULL));
	for (int i = 0; i < MAX_SIZE; i++) {
		// 임의의 정수 입력
		arr[i] = rand() % 1000;
	}
}

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

	tmp = *a;
	*a = *b;
	*b = tmp;
}

void Selection_Sort(int arr[]) {
	int p = 0;
	for (int i = 0; i < MAX_SIZE - 1; i++) {
		p = i;
		for (int j = i + 1; j < MAX_SIZE; j++) {
			if (arr[p] > arr[j]) p = j;
		}
		swap(&arr[i], &arr[p]);
	}
}

void Print(int arr[]) {
	for (int i = 0; i < MAX_SIZE; i++) {
		printf("[%d] -> %d\n", i, arr[i]);
	}
	printf("\n--------------------\n\n");
}

int main() {
	int arr[MAX_SIZE];

	Init(arr);

	Print(arr);

	Selection_Sort(arr);

	Print(arr);

	return 0;
}

#endif