자료구조(정렬 알고리즘) - 버블소트(Bubble Sort)

안녕하세요, 츄르 사려고 코딩하는 집사! 코집사입니다.

이번 글에서는 자료구조의 기초 정렬 알고리즘에서도 버블 소트(Bubble Sort)를 게시하려고 합니다.

버블 소트는 정렬 알고리즘에서도 가장 기본적인 것입니다. 

버블 소트란?

버블 소트는 서로 인접한 두 원소를 비교하여 정렬을 하는 알고리즘입니다.

예를 들어, A[5]라는 정수형 배열을 선언하고, 그 원소는 A[0]부터 3,1,4,5,9 가 선언이 되었습니다.

그러면, A[0]과 A[1]을 비교를 하여 오름차순 정렬을 하면 3이 1보다 크니까 1,3,4,5,9가 됩니다.

이처럼, 두 원소를 비교하여 정렬을 합니다.

버블 소트의 시간 복잡도(O(n^2))

만약에 5개의 원소가 배열에 저장되어 있다고 가정한다.

A[4]의 배열에는 5,4,3,2,1이 있다고 가정을 하면, (5,4), (4,3), (3,2), (2,1) 총 4번을 비교한다.

비교 후에 5는 A[4]위치에 배열이 완료되어 4,3,2,1,5이 된다.

비교 횟수는 4번이 된다.

그 다음, 다시 (4,3), (3,2), (2,1) 총 3번을 비교한다.

비교 후에 4는 5 앞의 배열에 위치하여 3,2,1,4,5가 된다. 

비교 횟수는 3번이 된다.

이 작업을 계속 반복하면 비교횟수는 1씩 감소하게 되고, 결국엔 1로 남게 된다.

그래서 총 비교 횟수는 4+3+2+1 로 총 10번이 된다.

(n-1)+(n-2) 이런 식으로 증명이 된다. 그래서, n(n-1) / 2 이 된다.

그래서 n^2-n / 2 라는 식이 나와서, 

O(n^2)의 시간 복잡도가 나오게 된다.

버블 소트 C언어 코드

#include<stdio.h>

int A[10000];

int n;

void swap(int a, int b)

{

int temp = a;

a=b;

b=temp;

}

void BubbleSort(int A[],int n)

{

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

{

if(A[i]>A[i+1])

{

swap(A[i],A[i+1]);

}

i++;

}

for(int j=0;j<n;j++)

{

printf("%d",A[j]);

}

}

int main()

{

printf("수 입력 ");

scanf("%d",&n);

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

{

scanf("%d",&A[i]);

}

BubbleSort(A,n);

}

바뀔게 없으면 중간에 끝내기

#include<stdio.h>

int A[10000];

int n;

void swap(int a, int b)

{

int temp = a;

a=b;

b=temp;

}

void BubbleSort(int A[],int n)

{

  int flag = 1;

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

{

if(A[i]>A[i+1])

{

swap(A[i],A[i+1]);

}

     else

     {

             break;

     }

i++;

}

for(int j=0;j<n;j++)

{

printf("%d",A[j]);

}

}

int main()

{

printf("수 입력 ");

scanf("%d",&n);

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

{

scanf("%d",&A[i]);

}

BubbleSort(A,n);

}