버블 정렬(Bubble 정렬)

버블 정렬 알고리즘의 개념

• 서로 인접한 두 원소를 검사해 정렬하는 알고리즘 ⇒ 인접한 2개의 원소의 대소를 비교해 크기가 원하는 순서대로 (오름/내림차순 혹은 사용자가 정의한 Comparator) 되어 있지 않으면 서로 교환
• 제자리 정렬 : 정렬하고자 하는 배열 안에서 교환하는 방식. 입력 배열 (정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법 ⇒ 공간복잡도 O(N)
• 과정 설명
  • 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환
  • 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동 ⇒ 1 회전에서는 맨 끝에 있는 자료는 정렬에서 제외
  • 2회전을 수행하고 나면 뒤에서 두번째 원소까지는 정렬에서 제외
  • 정렬을 1회전 수행할 때 마다 정렬에서 제외되는 데이터가 하나씩 늘어남.

 

버블 정렬 예제

• 7, 4, 5, 1, 3이 저장되어 있는 자료를 오름차순으로 정렬해 보자.

  

• GIF로 한눈에 이해하기
  
   

  ---

버블 정렬 JAVA 코드

import java.util.Arrays;

// bubble sort로 오름차순 정렬하기
public class bubbleSort {
	public static void main(String[] args) {
		int[] list = { 7, 4, 5, 1, 3 };
		BubbleSort(list, list.length); // 새로운 공간이 필요없고 처음 리스트 내에서 자리를 바꿈
		System.out.println(Arrays.toString(list));
	}

	private static void BubbleSort(int[] list, int N) {
		// 총 N-1회전 정렬을 진행한다.
		for (int i = 0; i < N - 1; i++) {
			for (int j = 0; j < N - 1 - i; j++) {
				if (list[j] <= list[j + 1]) { // 정렬 조건에 맞다면
					continue;
				} else { // 정렬 조건에 맞지 않다면 swap
					int temp = list[j];
					list[j] = list[j + 1];
					list[j + 1] = temp;
				}
			}
		}
	}
}

• 결과

 

버블 정렬 Python 코드

def bubbleSort(arr, N):
    for i in range(N - 1):
        for j in range(N - 1 - i):
            if arr[j] <= arr[j + 1]:
                continue
            else:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

list = [7, 4, 5, 1, 3]
bubbleSort(list, len(list))
print(list)

• 결과

 

---

버블 정렬 장단점

• 장점
  • 구현이 매우 간단, 소스코드가 직관적
  • 제자리 정렬 → 공간복잡도 O(n)
  • 안정정렬 (Stable Sort) : 중복된 값을 입력순서와 동일하게 정렬(버블정렬, 삽입정렬, 병합정렬) cf) 불안정정렬(Unstable Sort) : 중복된 값이 입력 순서와 동일하지 않고 무작위 정렬(퀵정렬, 선택정렬, 계수정렬)
• 단점
  • 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적
  • 특정 요소가 최종 정렬 위치에 있는 경우라도 교환이 일어남
  • 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡

---

버블 정렬 시간복잡도

• 비교횟수
  • 최상, 최악, 평균 모두 같음
  • n-1, n-2, ... , 1번 = n(n-1)/2
• 교환 횟수
  • swap은 3번의 이동이 필요함. 입력이 역순으로 정렬되어 있는 경우 ⇒ 3 n(n-1)/2
  • 입력 자료가 이미 정렬되어 있는 경우 ⇒ n(n-1)/2
• 총 합계 (역순 정렬된 경우)
  • T(n) = 3n(n-1)/2 = O(n^2)

---

정렬 알고리즘 시간복잡도 비교

 

 

 

출처

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

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EA%B1%B0%ED%92%88%20%EC%A0%95%EB%A0%AC%20(Bubble%20Sort).md#%EA%B1%B0%ED%92%88-%EC%A0%95%EB%A0%AC-bubble-sort 

GitHub - GimunLee/tech-refrigerator: 🍰 기술 냉장고입니다. 🛒 기술 면접 , 전공 시험 , 지식 함양 등 분