정렬 알고리즘 - Bubble Sort (버블 정렬) | C, Python 코드 구현

 

 

알고리즘 공부 시작-!
알고리즘에서 기본 중의 기본, 필수 중의 필수, 정렬 알고리즘 sorting algorithm에 대하여 공부를 시작한다. 정렬 알고리즘의 종류는 매우 다양하며, 따라서 똑같은 문제에 대해서도 다양한 알고리즘이 고안될 수 있다. 이때, 각 알고리즘간 성능 비교와 분석을 통해 보다 효율적인 알고리즘을 사용할 수 있도록 공부해보자.

정렬 sorting

• 정렬 sorting: 주어진 데이터들을 정해진 순서대로 나열하는 것
• 프로그램 작성시 필요한 경우가 많음
• 알고리즘 학습에서의 기본!!

버블정렬 bubble sort

bubble sort는 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 sorting algorithm이다.

 

버블 정렬은 인접한 두개의 숫자를 비교해가면서 가장 큰 숫자부터 맨 뒤로 보내어 픽스시키는 정렬 방법니다.

• 데이터의 길이가 n이라면, 최대 n-1번의 turn을 돌아야 한다.
• 1번의 turn마다 가장 큰 숫자가 뒤에서부터 1개씩 결정된다. 따라서 다음 turn에서는 마지막 index의 조건 체크를 할 필요가 없다.
• 경우에 따라 로직이 일찍 끝날 수도 있다. 따라서 한 번도 데이터가 swap된 것이 없다면 이미 정렬된 상태이므로 더이상 로직을 반복할 필요가 없다.

 

알고리즘 구현 (C, Python)

✅ C Code

void bubble_sort(int *num_arr, int arr_len){
	int j;
	while (arr_len > 0)
	{
		j = 0;
		while (j < arr_len - 1)
		{
			if (num_arr[j] > num_arr[j + 1])
				swap(num_arr, j, j+1);
			j++;
		}
		arr_len--;
	}
}

C에서 배열의 길이를 반환해주는 내장 함수 따위는 없기 때문에 함수 사용시, 배열의 길이를 인자로 직접 넘겨주어야 한다.

 

 

✅ Python Code

import random

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

        if swap == False:
            break

    return data

python에서는 더이상 swap이 없다면 i가 완전히 다 돌지 않아도 이미 정렬이 끝난 것으로 판단하여 for문을 종료하는 코드를 추가해주었다.

 

알고리즘 분석

반복문(for문)이 두 개이므로 시간복잡도는 $$O(n^2)$$이라고 할 수 있겠다. 결국 시간복잡도에 영향을 주는 애는 len(data)이다. len(data)에 따라 반복문의 반복 획수가 결정되기 때문이다.

이미 완전 정렬이 되어있는 상태라면 최선의 경우로, 시간복잡도는 $$O(n)$$이다. (이 경우에는 처음 for문은 한번만 돌아가고 바로 break되기 때문에 두번째 for문만 돌아간 것이다.)