버블 정렬(Bubble Sort)

1) 버블 정렬(bubble Sort) 이란? 

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

Bubble sort - Wikipedia

 

2) 알고리즘 구현

- n 개의 리스트가 있는 경우 최대 n-1 번의 로직을 적용한다.

- 로직을 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정된다.

- 로직이 경우에 따라 일찍 끝날 수도 있다. 따라서 로직을 적용할 때 한 번도 데이터가 교환된 적이 없다면 이미 정렬된 상태이므로 더이상 로직을 반복 적용할 필요가 없다.

 

 

▼ 파이썬

// Python
def bubblesort(data):
    for idx in range(len(data) - 1):	// 반복
        swap = False			// 교환이 되었는지를 확인하는 변수
        for idx2 in range(len(data) - idx - 1):
            if data[idx2] > data[idx2 + 1]:
                data[idx2], data[idx2 + 1] = data[idx2 + 1], data[idx2]
                swap = True
        if swap == False:
            break
    return data

1. for num in range(len(data) - 1) 반복

2. swap = False 를 통해 교환이 완료되었는지 확인

3. 1의 반복문 안에서, for idx2 in range(len(data) - idx -1) 반복

4. 3의 상황에서 data[idx2] 와 data[idx2 + 1] 의 크기를 비교

5. data[idx2] 의 크기가 크다면 순서를 바꿈

6. swap = True 로 변경

7. 3의 반복문이 진행되지 않고, swap == False 인 상태이면 break

 

결과 

import random

data = random.sample(range(100), 50)
print(bubblesort(data))

 

 

▼ 자바

// Java
void bubbleSort(int[] arr) {
	int tmp = 0;
    for(int i = 0; i < arr.length; i++) {
    	for(int j = 0; j < arr.length - i - 1; j++) {
        	if(arr[j] > arr[j+1]){
            	tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

 

 

3) 알고리즘 분석

- 반복문이 두 개인 형태이므로, O(n^2)

   단, 최악의 경우에는 {n*(n-1)}/2

- 완전 정렬이 되어 있는 상태라면 최선은 O(n)

 

 

 

참고)

1. Bubble sort - Wikipedia

Bubble sort - Wikipedia

2. 패스트캠퍼스 '코딩 알고리즘 온라인 완주반'