algorithm - 선택,삽입,버블 정렬

선택정렬

선택정렬 -> 최솟값을 찾아서 앞자리에 넣기.

선택정렬 구현

public class ex1 {
    public static int[] solution(int n,int[] arr) {
        int min,temp;
        for(int i=0; i<n-1; i++){      // 1.마지막은 자동정렬.
            min=i;
            for(int j=i+1; j<n; j++){  // 2.
                if(arr[j]<arr[min]){   // 3.
                    min=j;
                }
            }
            //스왑.
            temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
        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();
        }
        for(int x : solution(n,arr)){
            System.out.print(x + " ");
        }
    }
}

풀이
1.겉 for 문 -> i인덱스부터 for문으로 돌면서,마지막은 자동정렬 -1
2.안 for 문 -> 제일 작은 값의 j인덱스를 찾는다.
3.두 인덱스값을 스위치.

삽입정렬

삽입정렬 구현

삽입 정렬 -> 2번째 인덱스부터 앞의 정렬된 리스트의 알맞은 자리에 끼워넣기.

public class ex2 {
    public static int[] solution(int n,int[] arr) {
        for(int i=1; i<n; i++){
            int tmp=arr[i]; int j;
            for(j=i-1; j>=0; j--){
                if(arr[j]>tmp) arr[j+1] = arr[j];
                else break;
            }
            arr[j+1] = 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();
        }
        for(int x: solution(n,arr)){
            System.out.print(x+" ");
        }
    }
}

풀이
1.겉 for 문 -> 앞 정련된 리스트에 넣을 i를 찾는 for문, 해당 arr[i]를 tmp로 정의.
2.안 for 문 -> for(j=i-1; j>=0; j--) 로 정렬된 리스트를 탐색해서
tmp보다 크면 전부 한칸씩 오른쪽으로 민다. 더 큰값이 없으면 for문이 break로 멈추는데,
한칸 더 들어가서 break되기 때문에 for()문을 빠져나가서 arr[j+1]위치에 tmp를 넣는다.
근데 이때! j는 값이 for문안에서 선언되면 for()을 탈출하면 초기화되는데 그걸 방지하기 위해서 for()밖에 선언.

버블정렬

버블 정렬 -> 바로옆과 비교하면서 정렬

버블정렬 구현

public class ex3 {
    public static int[] solution(int n,int[] arr) {
        for(int i=0; i<n; i++){
            for(int j=0; j<n-i-1; j++){
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = 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();
        }
        for(int x : solution(n,arr)){
            System.out.print(x + " ");
        }
    }
}

풀이
1.겉 for 문 -> 라운드횟수
2.안 for 문 -> arr[j]>arr[j+1]이면 바꾸면서 끝까지 가는데 j+1과 비교하기때문에 맨뒷칸-1까지만 해야하고 라운드가 지날수록 큰 값이 뒤에 고정되기 때문에 -i를 해줘야한다. -> j<n-i-1;