버블 정렬 (Bubble Sort)

버블 정렬

- Selection Sort와 유사한 알고리즘으로 인접한 두 원소의 대소를 비교해서 정렬하는 알고리즘이다.

- 정렬을 하게 되면 오름차순 기준으로 맨 마지막 배열에 가장 큰 값이 순서대로 쌓이게 된다.

- 원소의 이동이 거품이 수면위로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.

 

정렬 알고리즘 (오름차순)

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

1. 배열의 0번째에서 시작하게 되는데 0번부터 마지막까지 비교를 한차례 시작한다.

2. 비교를 하면서 만약 앞의 원소가 뒤의 원소보다 크다면 바꿔주고 다시 인덱스를 한칸 넘어가서 비교를 한다.

3. 비교를 마치고 나면 맨 마지막 위치에 가장 큰 값이 위치하게 된다.

4. 이러한 비교를 배열번 만큼 반복하는데 마지막 자리에는 반복한 횟수만큼 큰 값들의 자리가 고정 되기 때문에 i 번       반복하게 되면 length - i 까지만 비교를 진행하면 된다.

 

JAVA Code

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

public class BubbleSort {
    public static void bubbleSort(int arr[]) {
        int tmp = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[j - 1] > arr[j]) {
                    tmp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int _loop = Integer.parseInt(br.readLine());

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

        bubbleSort(arr);

        IntStream.range(0, arr.length).map(i -> arr[i]).forEach(System.out::print);
        System.out.println();
    }
}