정렬-1

정렬은 특정 기준을 적용하여 나열하는 것이다.

 

선택 정렬

선택 정렬이란 최솟값을 앞으로 이동시키는 것이다.

 

import java.util.Arrays;
import java.util.Scanner;
//선택 정렬
public class Main{
    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<arr.length; i++){
            arr[i] =sc.nextInt();
        }
        for (int i =0;i<n;i++){
            //i번째 최솟값을 넣어라 i부터 맨끝까지 값중 최솟값
           int index = i;

           for (int j =i;j<n;j++){
               if (arr[index]>arr[j]){
                   index=j;
               }
           }
           int temp;
           temp = arr[i];
           arr[i] = arr[index];
           arr[index] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

코드를 보면 0부터 n까지 반복하는데, i번째 자리에  최솟값을 넣는 것을 의미한다.

즉 i=0일 때는 값들 중 가장 작은 값이 오게 된다.

i의 위치를 고정하면 그다음 자리부터 탐색하게 된다.

이를 n번 반복하면 정렬이 된다. 

즉 선택 정렬의 시간 복잡도는 O(n^2)가 된다.

 

 

삽입 정렬

원소를 차례대로 정렬된 배열에 삽입시키는 것이다.

 

import java.util.Arrays;
import java.util.Scanner;

//삽입 정렬
public class Main{
    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 i=0;i<n;i++){
            //i가 가르키고 있는 값을 넣어야함.
            //단 i 왼쪽은 정렬되어있음
            for (int j=i;j>=1;j--) {
                if (arr[j - 1] > arr[j]) {
                    int temp;
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                } else break;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

0부터 시작하여 n까지 반복하는데, 해당 i번째 수를 왼쪽으로 값과 비교한다.

그리고 만약 왼쪽의 수가 본인보다 적으면 거기서 자리를 옮기는 작업을 그만둔다.

이러면 i번째 작업을 수행할 때, index i를 기준으로 왼쪽은 정렬된 상태이다.

이를 n번 반복하면 정렬이 된다.

즉 삽입 정렬의 시간 복잡도는 O(n^2)이 된다.

 

 

버블 정렬

인접한 원소를 비교하여 큰 수를 뒤로 보낸다.

 

 

import java.util.Arrays;
import java.util.Scanner;

//버블 정렬
public class Main {
    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 i=0; i<n;i++){
            //n번 훑는다
            for (int j=0;j<n-i-1;j++){
                if (arr[j]>arr[j+1]){
                    int temp;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

0부터 n까지 반복하는데, 바로 오른쪽에 있는 수와 비교하여 큰 수를 오른쪽으로 옮긴다.

이러면 가장 큰 수는 제일 오른쪽으로 이동되어있다.

이를 n번 반복하면 정렬이 된다.

즉 버블 정렬의 시간 복잡도는 O(n^2)이 된다.