[알고리즘] 06.정렬, 이분검색과 결정알고리즘 / 01. 선택 정렬

선택 정렬

설명

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 선택정렬입니다.

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

출력

오름차순으로 정렬된 수열을 출력합니다.

예시 입력 1

6
13 5 11 7 23 15

예시 출력 1

5 7 11 13 15 23

느낀점

다양한 정렬방식이 있어서 헷갈리는 부분들이 있는데 이번에 알고리즘 문제풀이를 하면서 다시 한번 개념을 다잡아봐야겠다
시간 복잡도와 함께 묶어서 개념 정리!

선택정렬

• 선택 정렬(Selection sort) 알고리즘의 특징

  • 장점
    자료 이동 횟수가 미리 결정된다.

  • 단점
    안정성을 만족하지 않는다. 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

출처 : [Algorithm] 각 정렬의 특징 및 장단점 & 시간복잡도

코드

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		for(int x : T.solution(n, arr)) {
			System.out.print(x + " " );
		}
	}

	/*
	선택정렬
	6
	13 5 11 7 23 15
	*/

	public int[] solution(int n, int[] arr) {

		for(int i=0; i<n-1; i++) {
			int idx = i;

			for(int j=i+1; j<n; j++) {
				if(arr[j] < arr[idx]) {
					idx = j;
				}
			}

			int tmp = arr[i];
			arr[i] = arr[idx];
			arr[idx] = tmp;
		}
		return arr;
	}
}