버블정렬(Bubble sort) 알고리즘

버블정렬(Bubble sort)

인접한 두 개의 원소를 검사하여 정렬하는 알고리즘

 

버블정렬(Bubble sort) 알고리즘의 구체적인 개념

 

▶ 첫 번째 원소(8)과 두 번째 원소(4)를 비교하여 둘 중 큰 값이 오른쪽으로 올 수 있도록 자리 교환을 한다. 예시인 경우 8이 4보다 크기 때문에 8과 4의 자리를 바꾼다.

 

▶이번에는 두 번째 원소(8)과 세 번째 원소(1)을 비교한다. 이번에도 8이 1보다 크기 때문에 8과 1의 자리를 서로 바꾼다.

 

▶ 이와 같은 과정을 배열의 마지막까지 진행하고나면 배열의 마지막 원소에는 배열 내에서의 최대값이 위치하게 된다. 예시에서 볼 수 있듯이 최대 값은 13이 나왔다.

 

▶ 이번에는 배열의 가장 오른쪽을 제외하고,  위 과정을 다시 실행한다. 이번에는 최대값은 11이 나왔다.

 

▶ 이과정을 반복하면 최종적으로 오름차순으로 정렬된 배열을 얻을 수 있다. 

 

▶ 이와 같이 이웃한 두 개의 원소를 비교하여 정렬하는 알고리즘을 "버블 정렬(Bubble sort) 알고리즘"이라 한다. 

 

 

 

버블정렬(Bubble sort) 알고리즘의 예시

배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬

 

---

버블정렬(Bubble sort) 알고리즘의 소스 코드 구현

import java.util.Scanner;

public class programming {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		// 배열 사이즈 입력
		System.out.print("배열의 사이즈 입력:");
		int size = scan.nextInt();
		int[] data = new int[size];
		
		// 배열 원소 입력
		for(int i=0; i<size; i++)
			data[i] = scan.nextInt();
		
		// Bubble sort (ascending)
		for(int i=size-1; i>0; i--) {
			for(int j=0; j<i; j++) 
				if(data[j+1]<data[j]) {
					int tmp = data[j];
					data[j] = data[j+1];
					data[j+1] = tmp;
				}		
		}
		
		// 결과 출력
		System.out.print("Sorted array: ");
		for(int i=0; i<size; i++) 
			System.out.printf("%d ", data[i]);
	}
}

배열의 사이즈 입력:9
5 7 9 8 4 2 6 1 3 
Sorted array: 1 2 3 4 5 6 7 8 9

---

버블 정렬(Bubble sort) 알고리즘의 특징

 

장점

• 구현하기 쉽고, 간단하다.

단점

• 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
• 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.

 

일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

---

Reference

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