[알고리즘] 버블 정렬

버블 정렬

---

버블정렬

• 버블 정렬이란, 인접한 요소들간의 값들을 비교하고, 더 작은 값을 앞으로 보내주는 방식
• 배열의 원소가 하나가 남을 때 까지, 인접한 요소들의 값을 비교하는 방식을 계속적으로 진행한다.

GIF로 이해하는 버블 정렬의 동작원리

---

1. 인접한 요소들 간의 값을 비교해준다.
2. 두 요소 중 앞의 값이 뒤의 값보다 더 크다면, 값을 바꿔준다.
3. 배열의 요소가 하나가 남을 때 까지 1~2의 과정을 반복한다.

복잡도

---

시간 복잡도

첫 번째 회전에서의 비교 횟수 : n-1
두 번째 회전에서의 비교 횟수 : n-2 (두번째 인덱스부터 시작)
					/.../

이러한 원리를 적용하여, 배열의 원소가 하나가 남을 때 까지 비교를 반복하면,
최종 시간 복잡도는 (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 이므로,
O(n^2) 이다.

공간 복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)이다.

장점

• 구현이 매우 간단하다.
• 정렬하고자 하는 배열 안에서 교환하는 방식 -> 제자리 정렬(in-place Sorting)
• 안정 정렬 (Stable Sorting)이다.

단점

• 원소를 교환하는 횟수가 많다.
• 시간 복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.

구현 코드

package hw_0926;

public class BubbleSort {
	public static int[] bubbleSort(int n, int[] arr) {
		int temp;
		
		for(int i=0;i<n-1;i++) {
			for(int j = i+1;j<n;j++) {
				if(arr[i] > arr[j]) {
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
		return arr;
	}
	
	public static void showArray(int [] arr) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println(); //단순히 출력 형식을 맞춰주기 위함 
	}

	public static void main(String[] args) {
		int arr[] = { 7, 4, 5, 1, 3  };
		int n = arr.length;
		System.out.println("-----------정렬 전-----------");
		showArray(arr);
		
		bubbleSort(n,arr);

		System.out.println("-----------정렬 후-----------");
		showArray(arr);
	}
}

출력 결과

나가면서

버블 정렬에 대해 오래간만에 다시 공부해보았습니다.
학부 시절, 인접한 요소들끼리 계속적으로 비교하는 과정을 네모로 묶었을 때, 네모가 계속 겹쳐 "와 이래서 버블 정렬인가?" 라고 생각하며 공부 했었던 기억이 떠올랐습니다.
아무쪼록, 버블 정렬의 개념에 대해 알아볼 수 있는 유익한 시간이었습니다.