[알고리즘] #1 거품 정렬(Bubble Sort)

 

거품 정렬(Bubble Sort)를 Eclipse에서 Java코드로 구현해 보자

---

 

거품(Bubble) 정렬이란?
 가장 기본적인 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하고 조건에 따라 위치를 교환하여 배열을 정렬하는 것
마치 거품이 물 위로 올라오는 것 처럼 큰 값들이 배열의 끝으로 이동하는 모습에서 유래되었다고함

직관적이고 구현하기 쉬운 알고리즘이나, 성능이 뛰어나지는 않음

 

동작원리

1. 배열의 첫 번째 요소와 두번째 요소를 비교하여 조건에 따라 교환 -> 두 번째 요소와 세 번째 요소를 비교하여 조건에 따라 교환 -> ....이런식으로 마지막 -1 번째 요소와 마지막 번째 요소를 조건에 따라 교환하는 이 과정을 배열의 끝까지 반복함, 이 과정을 1회전(1 round)이라고 함

2. 각 1회전을 마친 후, 해당 회전에서 가장 큰 요소가 배열의 맨 뒤에 위치하게 되므로 2회전 부터는 정렬이 이미 완료된 마지막 요소를 제외하고 비교하는 것으로 시작함

3. 이 과정을 배열이 완전히 정렬될 때 까지 반복함

 

자바 코드로 버블정렬 구현

import java.util.Arrays;

	// 버블 정렬
public class Bubble_Sort {
	public static void main(String[] args) {
    	int[] arr = { 6, 3, 2, 4, 5, 1 };
		int temp = 0;						
		System.out.println("정렬 전 : " + Arrays.toString(arr));
        
		for (int j = 0; j < arr.length; j++) { 		     // 1.	
			for (int i = 0; i < arr.length - 1; i++) {   // 2.
				if (arr[i] > arr[i + 1]) {	     // 3.
					temp = arr[i + 1];
					arr[i + 1] = arr[i];
					arr[i] = temp;
				}
			}
		}
		System.out.println("정렬 후 : " + Arrays.toString(arr));
	}
}

버블 정렬은 위와 같이 2중 for문으로 이루어져 있다. 위 코드를 해석하면 다음과 같음.

 

1. 외부 반복문

바깥쪽 for문으로 J는 제외할 요소의 개수를 의미함. 즉 1회전에는 제외할 요소의 개수는 0개이며 한번 회전할 때 마다 가장 큰 요소가 배열의 맨 끝으로 이동하게 되므로 매 회전마다 제외할 요소의 개수가 1씩 늘어남

총 회전은 배열의 크기인 6번

 

2. 내부 반복문

안쪽 for문으로 요소를 비교할 인덱스인 i를 이용하여 1번의 외부 반복문에서 선택한 범위 내에서 인접한 요소를 비교하고 교환하기 위해 i 가 0 부터 시작하므로 배열의 0번 인덱스에 있는 데이터인 arr[0]부터 arr[5]까지의 인접한 요소를 비교할 수 있게 i를 증가시켜주는 반복문임

arr.length - 1은 비교시 배열의 끝이 넘어가지 않도록 범위를 제한하기 위함

 

( 위 코드에서 arr.length 은 6이므로 -1을 해주지 않는다면 if 문에서arr 배열의 최대 인덱스 arr[5]를 넘어가서 arr[6]을 참조하기 때문에 오류가 나기 때문)

 

3. 조건문

이 버블정렬의 핵심적인 부분이고 인접한 요소를 비교하여 교환하는 부분, arr[i](=현재 인덱스)의 요소와 arr[i+1](=다음 인덱스)를 비교하여 현재 인덱스의 위치한 요소가 다음 인덱스에 위치한 요소보다 크다면 위치를 서로 교환 해 주게 됨

이 과정을 통해 매 반복마다 가장 큰 요소가 배열의 끝으로 이동하게 됨

 

※ 위 코드는 오름차순으로 정렬했기 때문에 가장 큰 요소가 맨 뒤로 이동하지만 조건문의 부등호 방향을 변경 해주면 가장 작은 요소가 맨 뒤로 이동하게 되어 내림차순으로도 정렬이 가능

출력결과

정렬 전 : [6, 3, 2, 4, 5, 1]

정렬 후 : [1, 2, 3, 4, 5, 6]

 

요소들이 비교 & 교환되는 과정은 다음 GIF을 보면 이해하기가 더 쉬울것이다.

버블정렬의 특징

• 단순함 : 구현이 간단하고 코드가 직관적이어서 이해하기 쉽다.
• 효율성 : 평균적인 경우 시간 복잡도는 O(n^2)이므로 학습 목적이나 작은크기의 데이터 정렬에는 적합할 수 있으나 대규모 데이터에는 비효율적이다. 
• 안정성 : 동일한 값에 대해서는 순서가 유지되므로 안정 정렬(Stable Sort)이라고도 부른다.
• 시간 복잡도 : 최악, 최선, 평균 모두 O(n^2)로 동일하다. ( 최적화된 버블정렬은 최선에서 O(n)을 가짐 )
• 공간 복잡도 : 주어진 배열 안에서 요소들의 위치를 바꾸어 수행하므로 O(n) 이다.

마치며

오늘은 정렬 알고리즘 중 가장 먼저 배우게 되는 버블정렬에 대해 알아보고 구현해 보았다.

실제로는 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 등의 더 효율적인 정렬 알고리즘이 사용된다고 한다.

잘 쓰이지는 않지만 이러한 정렬 알고리즘들을 자주 연습해보면 프로그래밍 능력 뿐만 아니라 문제 해결 능력 향상에 매우 도움이 될 것이고 코딩테스트와 정보처리기사 시험문제로도 자주 출제되기 때문에 알아두면 좋을 것이다.

 

 

[참고자료]

https://jinhyy.tistory.com/9