[문제풀이] 06-01. 선택 정렬

인프런, 자바(Java) 알고리즘 문제풀이

Sorting and Searching - 0601. 선택 정렬

🗒️ 문제

🎈 나의 풀이

	private static int[] solution(int[] arr) {
        int tmp, index;

        for(int i=0; i<arr.length-1; i++) {
            index = i;

            for(int j=i+1; j<arr.length; j++) {
                if(arr[i] > arr[j]) index = j;
            }

            tmp = arr[i];
            arr[i] = arr[index];
            arr[index] = tmp;
        }

        return arr;
    }
    public static void main(String[] args) {
        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();

        arr = solution(arr);

        for(int i : arr) System.out.print(i + " ");
    }

🖍️ 강의 풀이

  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;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++) arr[i]=kb.nextInt();
		for(int x : T.solution(n, arr)) System.out.print(x+" ");
	}

💬 짚어가기

해당 문제는 정렬 알고리즘 중 가장 단순한 선택 정렬이다.
배열을 순회하며 가장 작은 값을 찾고, 해당 요소와 n번 쨰 요소의 값을 swap하여 정렬한다.

두개의 중첩 반복문을 순회하여 $O(n^2)$의 시간 복잡도를 갖는다.