[버블 정렬] 수 정렬하기

목차

1. 풀이

(1) 문제

백준 2750번, 수정렬하기 : https://www.acmicpc.net/problem/2750

 

핵심키워드

1) 문제 설명

- N개의 수가 정해졌을 때, 오름차순 정렬

 

2) 입력

- 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다.

- 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

3) 출력

- 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

(2) 풀이

- 시간제한은 1초이고 N의 최대 크기가 1,000이기 때문에 시간 복잡도 O(n²)를 가진 알고리즘을 사용할 수 있다.

- 버블 정렬 알고리즘 활용해서 풀면 쉽게 풀 수 있다.

 

버블 정렬 알고리즘

1) 버블 정렬(bubble sort)

- 버블 정렬은 인접한 두 값을 비교하여 왼쪽의 값이 더 큰 경우에 자리를 바꾸는 과정을 반복해서 정렬하는 방식이다.

 

2) 특징

1. 안정적인 정렬 알고리즘이다. 버블 정렬은 인접한 두 데이터가 정렬되지 않는 경우에만 교환이 발생한다.
2. 제자리 정렬 알고리즘이다. n을 담는 배열과 입력 크기 n을 위한 저장공간 이외에 필요한 저장공간은 기껏해야 루프의 제어 변수와 데이터 교환을 위한 변수 뿐이다.

3) 버블 정렬 시간 복잡도

Best	O(n)
Worst	O(n2)
Average	O(n2)

4) 버블 정렬 예제

오름차순으로 정렬할 경우 

 1. 첫번째 step에서 배열 인덱스 i 와 (i+1)의 값, 즉 인접한 두 개의 값을 서로 비교해서 크기가 큰 값은 오른쪽으로 보낸다.

출처 : https://www.programiz.com/dsa/bubble-sort

 

2. 두번째 스텝에서 매일 끝에 있는 값을 제외하고 나머지 인접한 값들을 비교해서 가장 큰 값을 맨 끝 앞으로 보낸다.

출처 : https://www.programiz.com/dsa/bubble-sort

 

3. 모든 값이 정렬될 때까지 반복한다.

 

2. 정답

1) 버블 정렬 1

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];
        int count = 0;

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        while (count < N) {
            for (int i = 0; (i + 1) < N; i++) {
                int temp = arr[i];
                if (arr[i] > arr[i+1]) {
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
            count++;
        }

        for (int num : arr) {
            System.out.println(num);
        }
        sc.close();
    }
}

 

2) 버블정렬 2

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        for (int i = 0; i < N-1; i++) {
            for (int j = 0; j< (N-1-i); j++) {
                if (A[j] > A[j+1]) {
                    int temp = A[j];
                    A[j] = A[j+1];
                    A[j+1] = temp;
                }
            }
        }

        for (int num : A) {
            System.out.println(num);
        }
    }
}

• 버블 정렬 1과 다른 점은 버블 정렬 1은 정렬된 값도 다시 체크하지만 버블정렬 2는 이미 정렬된 값은 비교하지 않고 넘어간다.
• 버블 정렬 1보다 개선된 알고리즘이다.

3. 참고

- Do it 알고리즘 코딩 테스트 자바 편(김종관)

- 알고리즘(이관용&김진욱)