버블 정렬(Bubble Sort) + C로 작성한 코드

Procedure

- 인접한 두 데이터를 SWAP하는 정렬

- 비교하고 교환하는 과정이 왼쪽에서부터 오른쪽으로 진행된다.

- 붙어있는 데이터를 비교하는 게 거품같다고 해서 버블 정렬이라고 한다.

- stable sort이다.

 

Example

- [ 5, 3, 8, 1, 2, 7] 이라는 배열 A가 있다고 하자.

- 첫 번째 반복의 절차는 아래 그림과 같다.

- 첫 번째 정렬이 끝나면 가장 오른쪽에 가장 큰 수인 '8'이 위치한다.

- 이런 식으로 총 5번을 반복하면 [ 1, 2, 3, 5, 7, 8 ]로 정렬이 된다.

 

장점

- 구현이 간단하다

 

단점

- 어떤 데이터가 정렬 후의 위치와 같게 있다 하더라도 근접한 데이터에 따라 이동할 수 있다 (비효율적)

- 한 데이터를 오른쪽으로 이동시키기 위해 모든 데이터들과 비교해야 한다.

 

 

# N개의 정수를 포인터를 이용하여 버블정렬하는 코드를 작성해보자.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

void bubbleSort(int N, int* a) {
	int tmp = 0;
	for (int i = N; i > 0; i--)
		for (int j = 0; j < i-1; j++)
			if (a[j] > a[j + 1]) {
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
			}
}

int main() {
	int N, *arr;
	printf("정수의 개수 : "); scanf("%d", &N);
	arr = (int*)malloc(sizeof(int) * N);

	printf("정수 %d개 입력 : ", N);
	for (int i = 0; i < N; i++)
		scanf("%d", &arr[i]);
	
	printf("버블 정렬 전 : ");
	for (int i = 0; i < N; i++)
		i == N - 1 ? printf("%d\n",arr[i]) : printf("%d ", arr[i]);

	bubbleSort(N, arr);
	printf("버블 정렬 후 : ");
	for (int i = 0; i < N; i++)
		i == N - 1 ? printf("%d\n", arr[i]) : printf("%d ", arr[i]);
}