14. 정렬(Sort) - 버블정렬(Bubble Sort)

0. 정렬의 특징

• 시간복잡도
• 안정(Stable) 정렬 VS 불안정(Unstable) 정렬
  중복된 값의 순서를 보장하느냐 안하느냐의 여부
• In-place 정렬 VS Out-of-place 
  구현방식에 따라서 원본 데이터 내에서 정렬하는가 아니면 정렬된 새로운 배열을 만드는가

---

1. Bubble Sort 개념

앞에서부터 비교연산을 수행하여 큰 값을 오른쪽에 위치시키는 비교연산을 수행 후 한 칸씩 옮겨가며 반복한다. 

한 사이클이 돌면 배열 내에 가장 큰 값이 오른쪽에 위치하고 종료된다.

이러한 사이클을 (배열의 크기  - 1) 만큼 수행해주면 정렬이 완료된다.

 

직관적이고 단순한 알고리즘 / 느리고 비효율적

시간 복잡도 O(N^2)

안정정렬

In-place 정렬

---

2. Bubble Sort 구현 - JAVA

package sort;

public class BubbleSort implements ISort {
    @Override
    public void sort(int[] arr) {
        // 안정 정렬
        for (int i = 0; i < arr.length - 1; i++) { // 전체 리스트
            for (int j = 0; j < arr.length - 1 - i; j++) {  // 정렬된 리스트 제외
                if (arr[j] > arr[j + 1]) { // 왼쪽 값이 오른쪽 값보다 크면 위치 교환
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }
}

---

3. Bubble Sort 구현 - Python

def bubble_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


if __name__ == "__main__":
    arr = [9,1,6,3,7,2,8,4,5,0]
    bubble_sort(arr)

    print(arr)