백준) (자바) 2750 수 정렬하기 1 (버블 정렬로 풀어보기)

수 정렬하기 1

 

수 정렬하기 1 - 백준 -

2750번: 수 정렬하기

---

n개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력하는 문제이다.

 

---

자바에는 sort로 손쉽게 풀 수 있다.

 

하지만 버블정렬(BubbleSort) 방법으로 풀어보고자 한다.

 

Bubble Sort : 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

 

원소의 이동이 거품이 수면위로 올라가 듯한 모습으로 보여 붙여진 이름이다.

 

 

버블 정렬은 두 인접한 데이터의 크기를 비교해서 정렬하는 방법이다.

시간복잡도는 O(n²)으로 다른 정렬 알고리즘보다는 느린 편이다.

 

버블 정렬 과정

1. 비교 연산이 필요한 루프 범위를 설정
2. 인접한 데이터 값을 비교
3.  swap 조건에 부합하면 swap 연산을 수행
4. 루프 범이가 끝날 때까지 2 ~ 3을 반복
5. 정렬 영역 설정. 다음 루프를 실행할 때는 이 영역을 제외
6. 비교 대상이 없을 때 까지 1 ~ 5를 반복

 

 

위의 이미지처럼 조건에 따라 swap해가며 뒤에서부터 정렬이 되어감을 알 수 있다.

 

    public static void bubbleSort(int[] arr, int s, int e) {
        for(int i = s; i < e; i++) {
            for(int j = 0; j < e - i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
    }

 

전체 배열 길이의 -1 번 만큼 루프가 수행되어야 한다.

또한 한 루프가 끝나면 맨 뒷줄부터 정렬되므로 i가 증가함에 따라

j로 swap 하는 범위는 i만큼 줄어들 것이다.

 

인접한 데이터를 비교하여 swap을 해주면 된다.

 

---

1. BufferedReader, StringBuilder로 Bubble 정렬 적용해 보기

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

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

    for(int i=0; i<n; i++) {
      arr[i] = Integer.parseInt(br.readLine());
    }
    
    arr = bubleSort(arr, n);

    for(int i=0; i<n; i++) {
      sb.append(arr[i]).append("\n");
    }

    System.out.print(sb);
    
  }

  public static int[] bubleSort(int[] arr, int n) {
    for(int i=0; i<n-1; i++) {
      for(int j=0; j<n-1-i; j++) {
        int temp = 0;
        if(arr[j] >= arr[j+1]) {
          temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
        }
      }
    }
    return arr;
  }
 
}

---

---

2. Stream, BufferedReader, StringBuilder로 Bubble 정렬 적용해 보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        int[] arr = IntStream.range(0, n)
                .map(i -> {
                    try {
                        return Integer.parseInt(br.readLine());
                    } catch (NumberFormatException | IOException ex) {
                        System.err.println("잘못된 숫자 형식 입니다.");
                        return 0;
                    }
                }).toArray();

        bubbleSort(arr, 0, n - 1);

        Arrays.stream(arr).forEach(i -> sb.append(i).append("\n"));

        System.out.print(sb);
    }

    public static void bubbleSort(int[] arr, int s, int e) {
        for(int i = s; i < e; i++) {
            for(int j = 0; j < e - i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

---

Stream을 하면 조금 더 느려진다.

---

Java의 Arrays.sort()로 정렬해 보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        Arrays.sort(arr);

        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append("\n");
        }

        System.out.print(sb);
    }
}

---

 

자바의 기본적인 sort가 구현이 잘되어있어서 시간도 빠르고 코드도 간결하다.

 

Dual-Pivot 퀵 정렬을 사용하고 있다고 한다.

일반적인 한 개의 pivot을 사용하는 퀵정렬보다 빠르다고 한다.