선택정렬

2중for문 시간복잡도 n^2

 

내 풀이

import java.util.*;
import java.io.*;


class Main {
    public int[] solution(int n, int[] arr1){
        int[] arr = arr1;
        for(int i =0; i < arr.length; i++){
            for(int j = i+1; j < arr.length; j++){
                if(arr[i] > arr[j]) {
                    int tmp =0;
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] =tmp;
                }
            }
        }
        return arr;
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i =0; i < n; i++)arr[i] = in.nextInt();

        for(int x : T.solution(n, arr)) System.out.print(x + " ");
    }
}

 

강의 풀이 i를 n-1 까지 돌아서 도는 횟수를 줄이고 idx 변수를 둬서 값 스왑을 마지막에 해주기

 

import java.util.*;
import java.io.*;


class Main {
    public int[] solution(int n, int[] arr1){
        int[] arr = arr1;
        for(int i =0; i < arr.length-1; i++){
            int idx = i;
            for(int j = i+1; j < arr.length; j++){
                if(arr[idx] > arr[j]) {
                    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 in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i =0; i < n; i++)arr[i] = in.nextInt();

        for(int x : T.solution(n, arr)) System.out.print(x + " ");
    }
}