버블 정렬(Bubble Sort)
1.배열의 첫번째 요소와 두번재 요소의 대소관계를 비교한다
2. 대소관계에 따른 위치를 바꾼다.
3.비교하는 배열의 첨자를 하나씩 증가하여 1,2,번을 되풀이한다.
4.배열의 끝 요소까지 비교했으면 처음부터 위 작업을 반복하되 바로 앞에서
비교 했던 요소중 제일 마지막 첨자는 제외
인접한 두 자료(a[i]와 a[i+1])를 비교하여 오름차순으로 저장되어 있지 않으면 교환
void bubble(int a[], int n)
{
int i=n-1, j, tmp;
while (i != 0) {
for (j=0; j <= i-1; j++) {
if (a[j] > a[j+1]) {
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
i--;
}
}
(1)기본유형 알고리즘
START
a[5]={5,3,1,2,4}
for i<-0 to 3 do
for j <- 1 to 4 do
if (a[i] > a[j]) then
tmp=a[i]
a[i]=a[j]
a[j]=tmp
endif
endfor
endfor
END
(2) 개선된 방법
한번의 pass동안
한번도 교환이 이루어지지 않으면 끝내도록 개선
flag변수의
사용
void bubble(int a[], int n)
{
int i=n-1, j, tmp ,flag = 1 ;
while (flag &&i != 0) {
for (j=0; j <= i-1; j++) {
if (a[j] > a[j+1]) {
flag = 1;
tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp;
}
}
i--;
}
}
(2)중간에 종료 알고리즘
START
a[5]={5,3,1,2,4}
for i<-0 to 3 do
flag=1
for j<-1 to 4 do
if(a[i]>a[j]) then
tmp=a[i]
a[i]=a[j]
a[j]=tmp
flag=0
endif
endfor
if flag then break
endfor
END
버블 알고리즘 코딩
#include <stdio.h>
void bubble(int a[], int n)
{
int i=n-1, j, tmp;
while (i != 0) {
for (j=0; j <= i-1; j++) {
if (a[j] > a[j+1]) {
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
i--;
}
}
void display(int a[], int n)
{
int i;
printf("정렬:");
for(i=0;i<n;i++)
{
printf("%3d",a[i]);
}
printf("\n");
}
main()
{
int a[]={25,48,37,17,52,86,43};
int n=sizeof(a)/sizeof(int);
int i;
printf("버블 알고리즘!\n");
printf("기존 배열:");
for(i=0;i<n;i++)
{
printf("%3d",a[i]);
}
printf("\n");
bubble(a,n);
display(a,n);
}
