Bubble-Sort(버블 정렬)

시간 복잡도 : O(n²)

처음 수를 잡고 뒤의 수와 계속 비교하며, 뒤의 수가 크면 뒤의 수를 잡고 아니면 뒤의 수와 바꾼다. 이 과정을 계속 반복하여 마지막에는 가장 큰 수가 오게 한다.

예)

[5,7,8,39,1,6] - 처음의 수를 잡는다

[5,7,8,39,1,6] - 뒤의 수와 비교한다

[5,7,8,39,1,6] - 처음 잡은 수보다 뒤의 수가 크기에 처음 수를 놔두고 뒤의 수를 잡는다

[5,7,8,39,1,6] - 다시 뒤의 수와 비교

[5,7,8,39,1,6] - 잡고 있는 수 보다 뒤의 수가 크기에 뒤의 수를 잡는다

[5,7,8,39,1,6] - 다시 뒤의 수와 비교

[5,7,8,39,1,6] - 잡고 있는 수 보다 뒤의 수가 크기에 뒤의 수를 잡는다

[5,7,8,39,1,6] - 다시 뒤의 수와 비교

[5,7,8,1,39,6] - 잡고 있는 수 보다 뒤의 수가 작기 때문에 잡고 있던 수와 바꾼다

[5,7,8,1,39,6] - 바뀐 수(원래 잡고 있던 수)를 잡는다

[5,7,8,1,39,6] - 다시 뒤의 수와 비교

[5,7,8,1,6,39] - 잡고 있는 수 보다 뒤의 수가 작기 때문에 잡고 있던 수와 바꾼다

[5,7,8,1,6,39] - 최종적으로 가장 큰 수가 뒤로 온다.

위의 단계를 반복

소스 - c언어

#include <stdio.h>
#include <stdlib.h>
#define MAX 100000


int main()
{
    int n,k;
    int i,j;
    int a[MAX];

    scanf("%d",&n);

    k=n;

    for(i=1;i<=n;i++)
    {
        a[i]=0;
    }

    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=k-1;j++)
        {
            if(a[j+1]<a[j])
            {
                int temp;
                temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;
                count++;
            }
        }
        k--;
    }

    for(i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

피드백 환영