[Java] 버블정렬(Bubble sort)

 

 안녕하세요 코북입니다. 오늘은 버블 정렬을 활용하여 오름차순 정렬하는 문제를 풀어봤습니다. 버블 정렬의 경우 사실상 거의 사용되지 않는 알고리즘이지만, 반대로 가장 기초적인 정렬 알고리즘이기 때문에 정렬 알고리즘에 대해 배우면 가장 먼저 배우는 알고리즘 중 하나일 것입니다.

 

정의 

버블 정렬이란 두 인접한 원소를 검사하여 정렬하는 방법으로 시간복잡도가 O(n²)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용됩니다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이라고 합니다. 

 

과정 (오름차순 기준)

1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교

2. 현재 원소가 다음 원소보다 크면 원소를 교환

3. 다음 원소로 이동하여 해당 원소와 그 다음 원소를 비교

 

풀이

9 8 5 7 2

현재 문제에서 나와있는 배열입니다. 먼저 맨 앞에 있는 9와 그다음 수인 8을 비교합니다. 9가 더 크므로 9를 뒤로 보내줍니다.

 

8 9 5 7 2

그 다음 9와 5를 비교합니다. 앞에 있는 수인 9가 더 크기 때문에 9를 뒤로 보내줍니다.

 

8 5 9 7 2

그다음 9와 7을 비교합니다. 9가 더 크기 때문에 뒤로 보내줍니다.

 

8 5 7 9 2

그 다음 9와 2를 비교합니다. 9가 더 크기 때문에 뒤로 보내줍니다.

 

8 5 7 2 9

이렇게 정렬을 마치면 1회가 끝입니다. 비교는 총 4번이었습니다.

9가 가장 큰 수라는 것을 알게 되었고 다시 처음부터 정렬을 시작합니다.

 

 

 

5 8 7 2 9

8과 5를 비교합니다. 8이 더 크기 때문에 뒤로 보내줍니다.

 

5 7 8 2 9

그 다음 8과 7을 비교합니다. 8이 더 크기 때문에 8을 뒤로 보내줍니다.

 

5 7 2 8 9

그 다음 8과 2를 비교합니다. 8이 더 크기 때문에 8을 뒤로 보내줍니다.

두 번째 정렬이 끝났고 비교는 총 3번 하였습니다.

 

...

 

5 2 7 8 9 

이렇게 반복적으로 정렬을 하다 보면 마지막에는 5와 2를 비교하게 됩니다.

5가 더 큰 수이므로 5를 뒤로 보내줍니다.

 

2 5 7 8 9

 

배열 크기가 5인 경우,

정렬은 총 4회 진행되었고

비교는 1회 때 4번

2회 때 3번

3회 때 2번

4회 때 1번 진행되었습니다.

 

규칙을 찾아보면

배열 크기가 n인 경우,

정렬은 총 n-1회가 진행됩니다.

비교는 n-정렬 차수 만큼 진행됩니다.

 

 아래는 소스코드입니다.

public class Java18_2 {
	public static void main(String[] args) {
		// 버블정렬
		// 옆의 배열과 계속 비교하면서 치환
		
		// 값 입력
		Scanner sc = new Scanner(System.in);
		int[] arr = new int[5];
		for(int i=0; i<arr.length; i++) 
		{			
			System.out.print((i+1) + "번째 수 입력 : ");
			arr[i] = sc.nextInt();
		}
		
		System.out.println("정렬 전");
		System.out.println(Arrays.toString(arr));		
		
		bubbleSort(arr);
		

	}
	
	public static void bubbleSort(int[] arr) {
		for(int i=1; i<arr.length; i++) // n-1회 정렬을 진행
		{
			for(int j=0; j<arr.length-i; j++)  // n-정렬 차수 만큼 비교
			{
				if(arr[j]>arr[j+1])
				{
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1]= temp;
				}
			}
		}
		System.out.println("정렬 후");
		System.out.println(Arrays.toString(arr));
	}
}

 

버블 정렬의 장점 및 단점

장점

1. 추가적인 메모리 소비가 적다.

2. 구현이 매우 쉽다.

3. 안정 정렬이 가능하다.

 

단점

1. 다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다.

 

배운 점

 버블 정렬의 개념에 대해 이해하고 공부할 수 있었다. 시간 복잡도와 정렬 속도에 대해 공부할 필요가 있을 것 같다.

 

 

 

 

본 글은 아래 링크의 내용을 참고하여 학습한 내용을 나름대로 정리한 글임을 밝힙니다.

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

https://yjg-lab.tistory.com/161

https://st-lab.tistory.com/195