버블정렬(Bubble Sort) 구현

 

버블정렬(Bubble sort)

- 1순회마다 큰숫자가 제일 뒤로 밀려나는게 거품이 수중표면으로 올라가는것과 비슷해서 지어진 이름이다.

- 인접한 두 원소를 검사하여 정렬하는 방법이다.

- 시간복잡도가 O(n^2)이기 때문에 느리지만 코드가 단순하다.

 

 

 

 

원리 (오름차순 기준)

  ※ 모든 순회를 다 표현하기엔 이미지 양이 많아지므로 1순회만 기준으로 설명한다.

  1. 2중 반복문으로 원소들을 돌면서 바로 다음 원소와 대소관계를 비교한다.

  2. 비교한 다음 대소관계에 따라 해당 원소와 비교 원소의 위치를 바꿔준다.

    ※ 마지막 순회는 정렬할 필요가 없으므로 순회를 돌 필요가 없다.

 

 

코드

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 10

void SetArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        arr[i] = rand() % 100;
    }
}

void PrintArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        printf("%%d\n", i, arr[i]);
    }
}

void BubbleSortAscending(int arr[])
{
    for (int i = MAX - 1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

void BubbleSortDescending(int arr[])
{
    for (int i = MAX - 1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (arr[j] < arr[j + 1])
            {
                int tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

void main()
{
    srand(time(NULL));
    int iArr[MAX] = { 0 };
    
    SetArr(iArr);
    
    BubbleSortAscending(iArr);
    //PrintArr(iArr);
    
    BubbleSortDescending(iArr);
    //PrintArr(iArr);
}