6-2장 버블 정렬

1. 버블 정렬 알아보기 

 

버블 정렬(bubble sort)

- 이웃한 두 요소의 대소관계를 비교하여 교환을 반복

 

ex) 배열 {6,4,3,7,1,9,8} 오름차순 정렬

- 왼쪽에 있는 값이 오른쪽에 있는 값보다 작아야 함

- 요소의 개수가 n개인 배열에서 n-1회 비교, 교환을 하면 오름차순으로 정렬됨

- 패스(pass) : 일련의 과정(비교, 교환 과정)

 

- 버블 정렬의 첫 번째 패스 

 

 

 - 버블 정렬의 두번째 패스 

- 패스를 1회 수행할 때마다 정렬할 요소가 하나씩 줄어듬

- 패스를 k회 수행하면 앞쪽의 요소가 k개 정렬됨

- 모든 정렬이 끝나려면 n-1회의 패스가 수행되어야 함

 

- 버블정렬 프로그램

//버블 정렬 (버전1)
#include <stdio.h> 
#include <stdlib.h>
#define swap(type,x,y) do {type t=x; x=y; y=t;} while(0)

//버블 정렬
void bubble(int a[], int n) 
{
	for(int i=0; i<n-1; i++) {
		//변수 i값을 0부터 n-2까지 1씩 증가하며 n-1회의 패스를 수행
		//끝에서 부터 앞쪽으로 스캔하면서 이웃하는 두 요소를 비교하고 교환 
		for(int j=n-1; j>i; j--) 
			if(a[j-1]>a[j])
				swap(int,a[j-1],a[j]);
	}
}

int main()
{
	int nx;
	
	puts("버블 정렬");
	printf("요소 개수:");
	scanf("%d",&nx);
	int *x=(int*)calloc(nx, sizeof(int));
	
	for(int i=0; i<nx; i++)
	{
		printf("x[%d]:",i);
		scanf("%d",&x[i]);
	}
	
	bubble(x,nx); //배열 x를 버블 정렬
	
	puts("오름차순으로 정렬했습니다.");
	for(int i=0; i<nx; i++)
		printf("x[%d]=%d",i,x[i]);
		
	free(x); //배열 해제 
	
	return 0; 
}

 

1.1 알고리즘 개선 (1)

 

- 이미 배열이 정렬을 마친 상태라면 그 이후의 패스는 요소 교환을 하지 않음 

- 어떤 패스에서 요소의 교환횟수가 0이면 더 이상 정렬할 요소가 없음을 뜻함

 -> 정렬작업 '멈춤' 

 

- 버블 정렬의 세번째 패스 

 

- 버블 정렬 프로그램 ( 교환횟수에 따라 정렬 작업을 멈춤)

//버블 정렬(버전 2: 교환 횟수에 따라 정렬 작업을 멈춤)
 void bubble(int a[],int n)
 {
	for(int i=0; i<n-1; i++) {
		int exchg =0; //패스에서 시도한 교환횟수
		for(int j=n-1; j>i; j--) 
			if(a[j-1]>a[j]) {
				swap(int,a[j-1],a[j]);
				exchg++;
			}
		if(exchg==0) break; //교환이 수행되지 않았다면 정렬을 멈춤  
	}
 }

- 변수 exchg

 -> 패스를 시작하기 전에 0으로 초기화 

 -> 패스에서 요소를 교환할 때마다 1씩 증가 

 -> 패스를 마쳤을 때의 exchg값 == 한 번의 패스에서 시도한 교환 횟수 

 -> exchg=0이면 정렬을 마친것이므로 break문으로 함수 종료 

 

 

1.2 알고리즘 개선(2)

 

- 배열 {1,3,9,4,7,8,6}에 대해서 버블 정렬

 - 마지막 교환 이후의 {1,3,4}는 정렬을 마친 상태 

 - 어떤 시점 이후의 교환이 수행되지 않는 다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태 

 - 두번째 패스는 나머지 4개의 요소에 대해서만 비교, 교환 수행하면됨

 

- 버블 정렬 프로그램 (스캔 범위를 제한)

//버블 정렬 (버전 3: 스캔 범위를 제한)
void bubble(int a[], int n) 
{
	int k=0; //a[k]보다 앞쪽의 요소는 정렬을 마친 상태 
	while(k<n-1) {
		int last = n-1; //마지막으로 교환을 수행한 위치를 저장
		for(int j=n-1;j<k;j--) 
			if(a[j-1]>a[j]) {
				swap(int,a[j-1],a[j]);
				last=j;
			}
		k=last;
	} 	
}

 

 - 교환을 수행할 때마다 오른쪽 요소의 인덱스 값을 last에 저장 

 - 패스를 마친 시점에 last에는 마지막으로 교환한 두 요소 가운데 오른족 요소의 인덱스가 저장 

 - last값을 k에 대입하여 다음에 수행할 패스의 범위를 a[k]까지로 제한 

  -> 다음 패스에서 마지막으로 비교할 두 요소는 a[k]와 a[k+1]이 됨