[알고리즘] 선택정렬

목표

• 기초적인 정렬 알고리즘 중 선택 정렬 알고리즘에 대해 이해한다.
• 기초적인 장렬 알고리즘 중 선택 정렬 알고리즘을 c로 구현한다.

선택 정렬 알고리즘이란?

• 선택 : 가장 큰 수 또는 가장 작은 수를 선택 정렬
• 정렬 : 항목들을 체계적으로 정리하는 과정
• 가장 큰 수 또는 가장 작은 수를 선택하여 항목들을 체계적(오름차순, 내림차순)으로 정리하는 과정이다.

선택 정렬 알고리즘의 예

• 배열에 8, 31, 45, 73, 3을 저장하자.

선택 정렬 알고리즘의 특징

• 같은 레코드 값이 있는 경우 상대적인 위치가 바뀐다.

선택 정렬 알고리즘의 구현(c++)

#include <iostream>
using namespace std;
int main (){
	int n; cin >> n;
	int a[n];
	int last;
	for(int i = 0; i < n; i++){
		cin>> a[i];
	}
	for(int i = n-1; i >= 0; i--){
		last = i;
		for(int j = 0; j < last; j++){
			if(a[j] > a[last])
				swap(a[j], a[last]);
		}
	}
	for(int i = 0; i < n; i++){
		cout <<  a[i] << endl;
	}
}

• 선택정렬 알고리즘 풀어보기 : https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

정리 및 느낀 점 

• 선택 정렬 알고리즘이 무엇인지 어떻게 구현하는 알아보았다.
• 같은 레코드 값을 가진 경우 상대적인 위치가 바뀔 수 있다.

참조

• https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html
• https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC