버블 정렬(Bubble Sort)

• 원소의 이동이 거품이 수면으로 올라오는듯한 모습을 보여 지어진 이름.

• 인접한 두 원소를 검사하여 작은 수를 앞으로 보냄. 각 사이클마다 가장 큰 값이 맨 뒤로 보내짐

• 코드가 단순하기 때문에 자주 사용.

• 내부연산이 가장 비효율적으로, 수행시간이 가장 느린 안좋은 알고리즘

순서

1. 두 번째 인덱스부터 시작해, 현재 인덱스 값과 이전 인덱스 값을 비교.
2. 이전 인덱스가 더 크다면 현재 인덱스와 Swap, 현재 인덱스가 더 크다면 다음 두 연속된 인덱스값 비교.
3. (전체 배열의 크기 - 현재 순환한 바퀴수) 만큼 반복

시간복잡도

버블 정렬의 시간복잡도는 O(N^2)

• 데이터의 갯수가 N개일 때, N(N+1)/2 번의 연산을 수행함
• 1부터 비교를 시작해 n-1개, n-2개··· 1개씩 비교를 반복함

공간복잡도

하나의 배열에서만 진행하므로 O(n)

코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

# define MAX_SIZE 25
# define RAND_RANGE 100


// 난수에 매번 다른 시드를 주기 위한 함수 
void seed_init() {
	srand((unsigned int)time(NULL));
} 

// 난수 발생 함수 
void random_number(int *array, int length) {
	bool overlapCheck = false; // 원소값 중복체크 변수 
	 
	for(int i=0; i<length; i++) {
		while(true) {
			array[i] = (rand()%RAND_RANGE)+1;
			overlapCheck = false;
			
			for(int j=0; j<i; j++) {
				if(array[j] == array[i]) {
					overlapCheck = true;
					break;
				}
			}
			if(!overlapCheck) {
				break;
			}
		}	
	}	
}

// 버블 정렬 
void bubble_sort(int *array, int length) {
	int i, j, temp;
	
	random_number(array, length);
	
	printf("정렬 전: ");
	for(i=0; i<length; i++) {
		printf("%d ", array[i]);
	}
	
	for(i=0; i<length; i++) {
		for(j=0; j<(length-1)-i; j++) {
			if(array[j] > array[j+1]) {
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
			}
		}
	}
	
	printf("\n정렬 후: ");
	for(i=0; i<length; i++) {
		printf("%d ", array[i]);
	}
	
	
}

int main() {
	clock_t second = 0;
	int data[MAX_SIZE] = {};
	int length = sizeof(data)/sizeof(int); // 배열의 크기
	seed_init();
	
	second = (int)clock();
	printf("\n\nBubble Sort\n");
	bubble_sort(data, length);
	printf("\n데이터 %d개의 정렬 수행시간: %0.4f초\n", MAX_SIZE, (float)(clock() - second) /CLOCKS_PER_SEC);   //요기까지 걸린 시간은?


	return 0;
}

결과

{:.alignleft}

---