서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다.
버블 정렬 개념 요약
- 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
- 인접한 2개의 레코드 크기를 비교하여 서로 교환한다.
- 선택정렬과 기본개념이 유사하다.
버블 정렬 구체적 개념
첫번째 원소와 두번째 원소를, 두번째와 세번째, 세번째와 네번째, ...
이렇게 n-1번째와 n번째 원소를 비교하여 교환하는 식으로 정렬한다.
1회전을 수행하고 난 후에는 가장 큰 원소가 맨 뒤로 이동하므로
2회전 수행때는 마지막 원소는 정렬범위에서 제외된다.
한 회전 수행될때마다 제외되는 데이터 길이가 하나씩 줄어든다.
버블 정렬의 예제
배열에 7,4,5,1,3이 저장 되있다고 가정하고 오름차순 정렬을 수행해보자.
1회전
- 첫 번째 원소 7을 두 번째 원소 4와 비교하여 교환, 두 번째의 7과 세 번째의 5를 비교하여 교환, 세 번째의 7과 네 번째의 1을 비교하여 교환, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 네 번 비교한다. 그리고 가장 큰 자료가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 자료는 비교할 필요가 없다.
2회전
- 첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 세 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 두 번째에 놓인다.
3회전
- 첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 두 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 세 번째에 놓인다.
4회전
- 첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.
버블 정렬의 예제 자바 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class BubbleSort {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] sort = new int[Integer.parseInt(br.readLine())];
for (int i=0; i<sort.length; i++) {
sort[i] = Integer.parseInt(br.readLine());
}
for (int i=0; i<sort.length; i++) {
for (int j=0; j<sort.length-i-1; j++) {
if (sort[j] > sort[j+1]) {
int tmp = sort[j];
sort[j] = sort[j+1];
sort[j+1] = tmp;
}
}
}
System.out.println(Arrays.toString(sort));
}
}버블 정렬의 특징
- 구현이 매우 간단하다.
- 하지만 단점이 더 크기 때문에 보통은 잘 사용하지 않는다.
- 단점에는 순서에 맞지 않는 요소 교환, 한개의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동할 때 모든 요소들과 교환이 이루어져야 한다
- 특정 요소가 최종 정렬 위치에 있음에도 교환 되는 일이 일어난다.
- 시간 복잡도가 결국 T(n) = O(N^2)
References
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
