C언어로 구현한 버블정렬

다음 자료는 한국 방송통신 대학교 컴퓨터과학과 

인천지역 2학년 과대표님께서 작성하신 소스코드를 수정한 것입니다.

출처 : http://cafe.daum.net/ICCS/LcpH/19

위 출처는 회원가입이 필요하며, 등업이 되어야만 보실 수 있습니다.

※ 참고로 *.cpp 파일로 저장하셔야 합니다. 반복문 안에서의 변수선언이 가능하도록 하기 위해 C++로 작성하였습니다.

---------------------------------------------------------------------------------------

#include<stdio.h>

#include<Windows.h>

/*

버블정렬 함수

- arr : 버블정렬의 대상이 되는 정수형 배열

- length : 배열의 크기(배열원소의 갯수)

*/

void BubbleSort(int arr[], int length)

{

int temp =  0; //두 개의 원소값을 서로 교환하기 위해 사용되는 임시변수

int top = -1; //가장 큰 값을 가진 원소의 인덱스값을 가진다.

int bound =  0; //반복문을 제어하기 위해 사용되는 변수

       //(이미 정렬된 원소를 제외한 나머지 원소를 검사하도록 하기 위해서 사용됨)

/*

- 뒤에서부터 검색한다.

- 뒤에서부터 앞으로 한 칸씩 이동하면서 인접한 두 개의 원소값을 비교하여 가장 큰 값을 찾는다.

- 큰 값을 찾아서 뒤로 옮기는 방식으로 동작한다.

- 간단히 예를 들어 아래와 같이 동작한다.

[4]-[2]-[3]-[1] 이라는 배열이 있다고 가정하자.

**for문의 매 동작시 배열의 변화**

[4]-[2]-[1]-[3]    (for문 1회 반복시)

[4]-[1]-[2]-[3]    (for문 2회 반복시)

[1]-[4]-[2]-[3]    (for문 3회 반복시)

※ for문을 모두 완료하면 가장 작은 값이 맨 앞으로 오게 된다.

   그 다음에는 가장 첫 번째 원소를 제외한 나머지 원소에 대해서 위 과정과 동일하게 반복실행하면,

**for문의 매 동작시 배열의 변화(단 위에 이어서..)**

[1]-[4]-[2]-[3]    (for문 1회 반복시)

[1]-[2]-[4]-[3]    (for문 2회 반복시)

※ 이번에는 두 번째 원소의 위치에 두 번째로 작은 값이 위치하게 된다.

   이렇게 for문 자체를 또다시 반복하기 위해 do-while문이 쓰이는 것이고,

   이미 정렬된 원소(앞에 위치한 원소)를 제외하고 나머지 원소를 검사하도록 하기 위해 bound라는 변수가

   사용된 것이다.

*/

do

{

/*

[가장 마지막 원소를 기준으로 검사하기 위해 top 변수에 마지막 원소의 인덱스 값을 삽입]

do-whlie문이 한번 동작할 때 마다 top의 값이 변경되기 때문에 do-while에 top=length-1; 코드를

삽입함으로써 do-while이 매번 동작할 때 마다 가장 마지막 위치의 원소값을 가르킬 수 있도록 

top의 값을 조정한다.

*/

top = length-1;

//맨 뒤에 있는 원소부터 비교

for(int i=top ; i>bound ; i--)

{

//i번째 원소보다 i-1번째 원소의 값이 더 작다면 (두 개의 인접한 원소를 비교/검사)

if(arr[i] < arr[i-1])

{

//i번째 원소의 값과 i-1번째 원소의 값을 서로 교환

temp  = arr[i];

arr[i]  = arr[i-1];

arr[i-1] = temp;

/*

인접한 두 개의 원소를 비교하여 값이 더 작은 원소의 인덱스값을 top에 저장

쉽게 말하면 정렬을 하지 않아도 되는 위치가 0번째부터 어디까지인지를 저장하기 위함

(나중에 bound변수에 이 값(top의 값)을 저장)

*/

top = i; 

}//if()-----

/*

배열원소의 모든 원소값을 출력

(반복문 매 동작시 배열의 상태변화를 보고 싶으면 아래 주석을 해제하세요.)

*/

//for(int i=0; i<length ; i++)

//{

// printf("%d ",arr[i]);

// printf("\n\n");

//}

}//for()-----

//printf("\n-----------------------------------------\n");

/*

위에서 값이 가장 작은 원소의 값을 맨 앞으로 정렬하였으므로, 

다음 do-while문 실행시 for문에서 가장 맨 앞쪽의 원소를 제외한 나머지 원소값을 서로 비교/검사하도록 한다.

이것이 반복되면 이미 정렬된 앞쪽의 원소들을 제외하고 나머지 원소들을 검사하는 결과를 가져온다.

*/

bound = top;

}while(top < length-1);

}//BubbleSort()=====

void main()

{

//버블정렬 대상이 되는 배열

int arr[]={30, 20, 40, 35, 5, 10, 45, 50, 25, 15};

//배열의 크기(배열원소의 갯수)

int length = sizeof(arr) / sizeof(*arr);

//버블정렬 함수 호출

BubbleSort(arr, length);

//배열원소의 모든 원소값을 출력

for(int i=0; i<length ; i++)

printf("%d ",arr[i]);

//system("pause");

return;

}

/* 버블정렬 특징

1. 안정적이다.

2. 제자리 정렬이다.

3. 시간복잡도 최선의 경우 O(n) 1, 2, 3, 4, 5 입력시...

4. 시간복잡도 최악의 경우 O(n2) 5, 4, 3, 2, 1 입력시...

5. 정의 : 버블의 경우 입력순서에 따라 시간 복잡도가 달라진다

*/