Bubble Sort

서로 인접한 두 원소의 대소를 비교, 조건에 맞지 않으면 자리를 교환하며 정렬하는 알고리즘

void bubbleSort(int arr[], int n) {
	int i, j;
    for(i = 0; i < n - 1; i++)
    	for(j = 0; j < n - i - 1; j++)
        	if(arr[j] > arr[j+1])
            	swap(arr[j], arr[j+1]);

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

시간복잡도

모두 O(n^2)

공간복잡도

O(n), 주어진 배열 안에서 swap 사용으로

장점

구현 간단, 직관적

제자리 정렬(in-place sorting), 배열 안에서 교환하는 방식

안정 정렬(stable sort)

단점

비효율적. 시간복잡도 O(n^2)

swap 연산이 많이 일어남(정렬된 자리로 이동을 위해)

Optimized version

array 가 sort 되어있으면 빠져나오도록 처리

def bubbleSort(arr):
	n = len(arr)
    for i in range(n):
    	swapped = False
        for j in range(0, n-i-1):
        	if arr[j] > arr[j+1]:
            	arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if swapped == False:
        	break

 

References

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

https://www.geeksforgeeks.org/bubble-sort/

Bubble Sort Algorithm - GeeksforGeeks