[개념 학습 및 정리] 정렬

1. 정렬

특정 기준(오름차순, 내림차순)을 적용하여 나열하는 것이다. 기본 정렬 방법은 다음과 같다.

• 선택 정렬
• 삽입 정렬
• 버블 정렬

 

 

 

2. 선택 정렬

1) 원리

오름차순 기준으로 최솟값을 앞으로 이동시켜 정렬하는 방법이다.

• 최솟값 찾기 (1)
• 최솟값 이동 (2)
• 과정 반복

 

(1)

14

4

8

23

11

5

3

2

4

9

(2)

2

4

8

23

11

5

3

14

4

9

(1)

2

4

8

23

11

5

3

2

4

9

(2)

2

3

8

23

11

5

4

2

4

9

. . .

2) 구현

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 선택 정렬
        for(int i = 0; i < n; i++) {
            int inx = i;
            for(int j = i; j < n; j++) {
                if(arr[inx] > arr[j]) {
                    inx = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[inx];
            arr[inx] = temp;
        }

        for(int i = 0; i < n; i++) bw.write(arr[i] + " ");

        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

 

3. 삽입 정렬

1) 원리

원소를 차례대로 정렬된 배열에 삽입하는 방법이다.

• 인접한 원소와 비교 (1)
• 작은 원소를 왼쪽으로 삽입 (2)
• 과정 반복

 

(1)

4

8

14

23

<- 11

5

3

2

4

9

(2)

4

8

14

<- 11

23

5

3

2

4

9

(3)

4

8

11

14

23

5

3

2

4

9

2) 구현

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 삽입 정렬
        for(int i = 0; i < n; i++) {
            for(int j = i; j >= 1; j--) {
                if(arr[j-1] > arr[j]) {
                    int temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                } else break;
            }
        }

        for(int i = 0; i < n; i++) bw.write(arr[i] + " ");

        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

 

4. 버블 정렬

1) 원리

인접한 원소를 비교하여 큰 수를 뒤로 보내는 방법이다. 최대값이 항상 뒤에 있음을 보장할 수 있다.

14 ->

4

8

23

11

5

3

2

4

9

 

4

14 ->

8

23

11

5

3

2

4

9

 

4

8

14 ->

23

11

5

3

2

4

9

 

4

8

14

23 ->

11

5

3

2

4

9

 

4

8

14

11

23 ->

5

3

2

4

9

. . .

4

8

14

11

5

3

2

4

9

23 (고정)

2) 구현

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 버블 정렬
        for(int i = 0; i < n-1; i++) {
            for(int j = 0; j < (n-1)-i; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

        for(int i = 0; i < n; i++) bw.write(arr[i] + " ");

        bw.flush();
        bw.close();
        br.close();
    }
}