버블정렬(BubbleSort)이란?

버블 정렬

버블정렬은 현재 원소와 다음 원소를 비교하여 조건에 맞으면 교환하는 식의 정렬이다.

원소가 거품처럼 올라오는 듯하여 버블정렬이라고 부른다.

---

처음 7과 5를 비교하여 7이 더 크므로 위치를 바꾼다. 이후 배열의 끝까지 비교해서 값이 더 크다면 위치를 바꾼다.

다시 5와 1을 비교해 5가 더 크므로 위치를 바꿔준다. 이번엔 정렬이 끝난 7 전까지만 해당 과정을 반복 해준다.

다시 1과 4를 비교하여 1이 더 작으므로 위치를 바꾸지않는다.

이후 4와 3을 비교했을 때 4가 더 크므로 위치를 바꿔준다.

1과 3을 비교하여 1이 더 작으므로 위치를 바꾸지 않는다. 이렇게하면 버블정렬이 완료된다.

 

버블정렬의 특징

• 버블정렬은 하나의 배열에서 값을 바꾸는 식으로 동작하므로 공간복잡도는 O(1)이다. 선택정렬과 마찬가지로 SWAP할 때 필요한 임시변수 정도의 추가공간만 있으면 되므로 IN-PLACE 정렬이다.
• (N-1), (N-2) ... 1번의 탐색이 필요하므로 시간복잡도는 O(N^2)이다.
• 버블정렬은 중복된 키 값의 순서가 정렬 후에도 유지되므로 STABLE정렬이다.

 

전체 코드

#include <stdio.h>
#define LEN 5

void bubbleSort(int* arr) {
	int i, j,temp;
	for (i = 0; i < LEN; i++) {
		for (j = 0;j < LEN - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

int main() {
    int arr[LEN] = { 7,5,1,4,3 };
    int i;
    printf("정렬 전 : ");
    for (i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    bubbleSort(arr);
    printf("정렬 후 : ");
    for (i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

실행결과