[자료구조]버블 정렬

많이 알려져있고 또 많이 접하기도 했지만 막상 정리가 잘 안 된 터라 정렬에 대한 개념정리 차원에서 정렬 알고리즘에 대한 글을 포스팅하기로 했습니다. 버블 정렬을 시작으로 선택, 삽입, 퀵, 병합, 기수 정렬 내용을 차례대로 정리할 계획입니다. 우선 오늘은 정렬 중에 가장 쉽게 생각할 수 있는 알고리즘인 버블 정렬에 대해 알아보겠습니다.

 

버블 정렬이란 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식입니다. 왜 버블 정렬인지 궁금해서 찾아봤는데 정렬 과정에서 원소의 이동이 마치 거품이 수면위로 떠오르는 것 같다고 하여 붙여진 이름이라고 합니다. 버블 정렬은 데이터를 '비교'하면서 찾기에 '비교 정렬'이라고도 볼 수 있습니다. 정렬의 대상이 되는 데이터 이외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬'이라고 부르기도 합니다. 데이터를 서로 교환하는 과정에서 임시 변수를 필요로 하지만 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것입니다. 이는 선택정렬과도 같은 부분입니다. 시간 복잡도는 다른 정렬 알고리즘과 비교해볼 때 느린 편입니다. 이 점 참고하셔서 알고리즘 문제풀이에 활용하시면 좋겠습니다.

 

버블 정렬은 다음과 같이 루프(loop)를 돌면서 인접한 데이터 간의 swap 연산으로 정렬합니다.

 

 

정렬 과정은 다음과 같습니다.

 

*버블 정렬 과정

1. 비교 연산이 필요한 루프 범위를 설정합니다.

2. 인접한 데이터 값을 비교합니다.

3. swap 조건에 부합하면 swap 연산을 수행합니다.

4. 루프 범위가 끝날 때까지 2와 3을 반복합니다.

5. 정렬 영역을 설정하고 다음 루프를 실행할 때는 이 영역을 제외합니다.

6. 비교 대상이 없을 때까지 1~5를 반복합니다.

 

만약에 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았을 경우 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 됩니다.

 

*버블 정렬 문제

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

*2750번 소스

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        int[] arr = new int[N];
 
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        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 x : arr) {
            System.out.println(x);
        }
    }
}
 

 

*참고

https://st-lab.tistory.com/195