다음 자료는 한국 방송통신 대학교 컴퓨터과학과
인천지역 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. 정의 : 버블의 경우 입력순서에 따라 시간 복잡도가 달라진다
*/
'기타' 카테고리의 다른 글
C언어로 구현한 삽입정렬 (0) | 2013.10.24 |
---|---|
C언어로 구현한 선택정렬 (0) | 2013.10.24 |
C언어로 구현한 단순연결리스트 (0) | 2013.10.21 |
C언어로 구현한 원형 큐 소스코드 (0) | 2013.10.08 |
다음 지도 API 사용하기 (지도연동) (0) | 2013.09.09 |