버블 정렬(Bubble Sort)

이번에 배워볼 정렬 알고리즘은 버블 정렬(Bubble Sort)이다.

버블 정렬은 인접한 2개의 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행하여 정렬하는 알고리즘이다.

 

선택 정렬과 삽입 정렬은 정렬된 원소들이 좌측에 위치하는 반면, 버블 정렬은 이와 다르게 정렬된 원소들이 우측에 위치하는 차이점이 존재한다.

버블 정렬의 가장 큰 문제점은 순서에 맞지 않은 원소를 인접한 원소와 매번 교환한다는 것이다. 특정 원소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 발생하기 때문에 구현하기가 정말 단순하지만 좋지 못한 성능 때문에 거의 사용되지 않는다.

버블 정렬(Bubble Sort)의 시간 복잡도는 O(N^2)이다.

 

버블 정렬은 Java로 구현한 코드는 다음과 같다.

public class Main {

	public static void main(String[] args) throws IOException {
		int[] num = {5, 3, 1, 2, 4};
		
		num = bubble_sort(num.length, num);
		for (int k : num) {
			System.out.print(k + " ");
		}
	}
	
	public static int[] bubble_sort(int n, int[] num) {
		for (int i = n - 1; i > 0; --i) {
            //정렬되지 않은 영역내의 모든 원소를 조건에 맞도록 교환한다.
			for (int j = 0; j < i; ++j) {
				if (num[j] > num[j + 1]) {
					int temp = num[j];
					num[j] = num[j + 1];
					num[j + 1] = temp;
				}
			}
		}
		return num;
	}
}