정렬 - Bubble sort

Bubble sort

 

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#define swap(type, x, y) do {type t = x; x = y; y = t;} while(0)

void bubble(int a[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)
	{
		for (j = n - 1; j > i; j--)
			if (a[j - 1] > a[j])			
				swap(int, a[j - 1], a[j]);			
	}
}

int main(void)
{
	int i, nx;
	int *x;
	puts("Bubble sort");
	printf("number of factors : ");
	scanf("%d", &nx);
	x = calloc(nx, sizeof(int));

	for (i = 0; i < nx; i++)
	{
		printf("x[%d] : ", i);
		scanf("%d", &x[i]);
	}

	bubble(x, nx);

	puts("Aligned in ascending order.");
	for (i = 0; i < nx; i++)
		printf("x[%d] = %d\n", i, x[i]);
	free(x);

	return 0;
}

 

 

상단의 코드에서 void bubble함수를 개선해 본다.

모든 사이클을 다 돌 필요가 없을 수도 있기에 만약 사이클을 돌 때 배열에서 swap이 한 번도 일어나지 않았다면 정렬을 멈추고 break문으로 빠져나오게 할 수 있다.

// 카운터 도입
void bubble(int a[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)
	{
		int exchg = 0;
		// 한 사이클 돌리는 for문
		for(j = n -1; j > i; j--)
			if (a[j - 1] > a[j])
			{
				swap(int, a[j - 1], a[j]);
				exchg++;
			}
		if (exchg == 0) break;
	}
}

 

 

더 나아가서 사이클을 도는 범위를 점차 좁혀갈 수도 있다.

void bubble(int a[], int n)
{
	int k = 0; // 마지막 swap이 이루어진 자리 저장 변수
	// swap해준 자리가 배열 마지막 자리와 같다면 while문 패스
	while (k < n - 1)
	{
		int j;
		int last = n - 1;
		for(j = n - 1; j > k; j--)
			// swap 판단
			if (a[j - 1] > a[j])
			{
				swap(int, a[j - 1]; a[j]);
				last = j; // swap 판단해준 자리 저장
			}
		k = last; // for바깥에서 또 마지막으로 swap된 자리 저장
	}
}