[알고리즘] 자바에서의 버블 정렬

정렬 알고리즘의 개요

- 정렬(sorting) : 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는것

- 정렬은 프로그램 작성 시 빈번하게 필요로 한다.

    - 다양한 알고리즘이 고안 되었으며, 알고리즘 학습의 필수 요소이다.

- 다양한 정렬 알고리즘 이해를 통해 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘 간 성능 비교를 통해 알고리즘 성능 분석에 대해서도 이해할 수 있다.

 

버블 정렬

- 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 알고리즘

- 매 반복 마다 0번째 인덱스 부터 시작하여 마지막 인덱스 까지 앞, 뒤에 있는 숫자끼리 비교하여 각자 위치를 바꿔줌으로서 최종적으로 오름차순, 또는 내림차순 정렬을 완료한다.

- 매 반복마다 숫자 간의 비교 횟수는 배열 길이 -1 회이다.

- 매 반복마다 가장 큰 숫자가 배열의 가장 끝에 배치된다, 그 다음 반복 부터는 가장 마지막 위치의 인덱스를 제외한 나머지 숫자들 중에서 가장 큰 숫자가 마지막 위치의 바로 앞 인덱스부터 차례대로 배치된다.

 

* 그 말은 즉, 매 반복 마다 항상 가장 큰 값이 제일 뒤로 밀려나므로 그 다음 반복에서는 해당 인덱스의 숫자와는 비교를 할 필요가 없게되어, 반복이 진행되면 진행될수록 점점 숫자간의 비교 횟수가 1씩 줄어들게 된다.

 

그렇다면 정렬이 완료 되었음을 판별하는 방법은?

- 일련의 정렬 알고리즘을 통해 배열의 정렬이 완료되었든, 애초에 배열이 정렬되어 있었든, 결국 배열이 최종적으로 정렬 완료되었음을 판단할 수 있어야 한다.

- boolean 타입의 변수를 만들어 기본값을 false 로 지정한 후, 배열 내부에서 매 반복마다 숫자들간의 위치 변경이 있으면 해당 변수를 true 로 바꿔주는 방식으로 정렬이 완료되었는지, 완료되지 않았는지를 판별할 수 있다.

- 만약 해당 반복 때 숫자들간의 위치 변경이 발생하지 않았다면, 배열의 정렬이 완료 되었다는 뜻이므로 반복문을 종료 시킨다.

 

데이터	1회 반복	2회 반복	3회 반복
5, 7, 3, 9, 4	5, 3, 7, 4, 9	3, 5, 4, 7, 9	3, 4, 5, 7, 9

https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

자바 코드로 직접 구현해보자.

- BubbleSort.java

public class BubbleSort {
	
	private int[] array;
	
	public BubbleSort(int[] array) {
		this.array = array;
	}
	
	public int[] bubbleSort(int[] array) {
		
		for(int i = 0; i < this.array.length - 1; i++) {
			boolean swap = false;
            // 배열의 길이 - 1 에서 현재 i 의 값을 빼면
            // 현재 배열에서 가장 뒤로 밀려난 최대값에 대한 비교를 생략해줄 수 있다.
			for(int index = 0; index < this.array.length - i - 1; index++) {
				if(this.array[index] > this.array[index + 1]) {
					int temp = this.array[index + 1];
					this.array[index + 1] = this.array[index];
					this.array[index] = temp;
					
					swap = true;
				}
			}
			
			if(!swap)
				break;
		}
		
		return this.array;
	}
}

 

코드가 제대로 동작하는지 확인하기 위한 main 코드는 다음과 같다.

- BubbleSort_main.java

import java.util.Arrays;
import java.util.Random;

public class BubbleSort_main {
	public static void main(String[] args) {
		int[] array = new int[10];
		
		Random random = new Random();
		
		for(int i = 0; i < array.length; i++) {
			array[i] = random.nextInt(100); // 0 ~ 100 이하 랜덤 정수 생성
		}
		
		BubbleSort sortArray = new BubbleSort(array);
		int[] resultArray = sortArray.bubbleSort(array);
		
		Arrays.stream(resultArray).forEach(x -> System.out.print(x + " "));
	}
}

 

버블 정렬 알고리즘 분석

- 서로 중복되는 값이 있을 경우, 두 숫자의 위치가 서로 뒤바뀌지 않도록 안정성을 보장하는 안정 정렬(Stable Sort) 이다.

- 2중첩 반복문을 사용하기 때문에 시간 복잡도는 O(n^2) 이며, 최악의 경우 n * (n - 1) / 2 가 된다.

- 이미 정렬이 되어 있는 상태라면 최선의 경우이므로 O(n) 이다.

(2중첩 반복에서 내부 반복문을 한번 순회한 이후, 숫자들간의 위치 변경이 발생하지 않았기 때문에 그대로 전체 코드가 종료된다.)

- 구현이 단순하지만 그만큼 비효율적인 정렬 방법이다.(비슷한 예시 : 삽입 정렬, 선택 정렬)