[알고리즘][정렬] 버블 정렬

버블 정렬

정의

출처-https://visualgo.net/ko

• 정렬되지 않은 전체 자료들을 대상으로 인접한 두 개 자료의 키 값을 비교하여 위치를 교환하는 정렬 방식

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다

두 개의 초록색은 서로를 비교하며 작은 값이 앞에 오도록 교환한다. 그 과정에서 결국에는 가장 큰 값이 맨 뒤에 위치에 하게 되는데 정렬이 된 부분은 노란색으로 변한다.

구현1

#include <stdio.h>
#include <stdlib.h>
void printArray(int value[], int count) {
	int i = 0;
	for (i = 0; i < count; i++) {
		printf("%d ", value[i]);
	}
	printf("\n");
}

void bubbleSort(int value[], int count) {
	int i=0, j=0;
	int temp = 0;
	for (i = count - 1; i >= 0; i--) {
		for (j = 0; j <= i; j++) {
			if (value[j - 1] > value[j]) {
				temp = value[j - 1];
				value[j - 1] = value[j];
				value[j] = temp;
			}
		}
		printf("Step-%d ", count - i);
		printArray(value, count);
	}
}

int main() {
	int values[] = { 80,50,70,10,60,20,40,30 };
	printf("Before Sort\n");
	printArray(values, 8);

	bubbleSort(values, 8);

	printf("After Sort\n");
	printArray(values, 8);
}

구현2

#include <stdio.h>
#pragma warning(disable:4996)
int main(void) {
	int array[10] = { 1,10,5,8,7,6,4,3,2,9 };
	int i, j,temp;
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 9-i; j++) {
			if (array[j] > array[j + 1]) {
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
}

구현3

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
#define MAX_SIZE 10
int list[MAX_SIZE];
int n;
void bubble_sort(int list[], int n) {
	int i, j, temp;
	for (i = n - 1; i >= 0; i--) {
		for (j = 0; j < i; j++) {
			if (list[j] > list[j + 1])
				SWAP(list[j], list[j + 1], temp);
		}
	}
}
int main(void) {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i < n; i++) {
		list[i] = rand() % 100;
	}
	bubble_sort(list, n);
	for (i = 0; i < n; i++) {
		printf("%d ", list[i]);
	}
	printf("\n");
}

특성

• 최선, 평균, 최악: O($n^2$)
• 알고리즘의 효율성이 매우 느림
• 자료의 크기가 클 때 사용이 어려움
• 정렬의 안정성 유지