[Sort] 개선된 버블정렬

1. 소개

버블정렬은 인접한 요소를 검사하여 정렬하는 방식입니다.

여기서 이미 정렬이 되어있을시 넘어가는 개선된 버블정렬을 소개하려합니다.

2. 장점 & 단점

시간복잡도는 O(n²)으로 느립니다. 하지만 코드가 단순합니다.

개선된 버블정렬은 이미 정렬되있을시 넘어갑니다.

3. 정렬 순서

< 알아두어야 할것 >

1. 이 버블정렬은 오름차순 정렬입니다.

2. 조건: 둘이 비교하여 왼쪽이 더 클경우 교환

- 이번엔 2,4,5,1,3 이라는 임의의 수를 버블정렬을 통해 정렬해보겠습니다.

2와 4부터 비교하죠

조건에 맞을때까지 돌립니다~

조건에 맞는칸 발견! 교환 ~

- 다음칸도 조건 일치! 교환!

- 이제 5는 무조건 확정이니 두고

다시 처음부터 시작합니다

여기도 조건에 맞으니 교환!

- 다시첨으로가서 바로 조건에 맞는친구 교환

정렬 완료!

4. 코드

#include <stdio.h>
 
 
// 개선된 버블정렬
#if 1
 
// bool 값을 넣어 오름차순인지 내림차순인지 확인함
// flag를 넣어 바뀔값이 없으면 그대로 나옴
void BubbleSort(int data[], int dataSize, bool isAscending)
{
    int i, j, temp;
    bool flag = true;
    int count = 0;
    for (int i = 0; flag > 0; i++)
    {
        flag = false;
         for (j = 0; j < dataSize - (i + 1); j++)
        {
            if (isAscending ? data[j]>data[j + 1] : data[j] < data[j+1])
            {
 
                flag = true;
                temp = data[j + 1];
                data[j + 1] = data[j];
                data[j] = temp;
            }
            ++count;
        }
 
    }
    printf("count: %d\n", count);
}
 
#endif
 
 
 
int main()
{
    int data[] = {2,4,1,3,5 };
    int dataSize = sizeof(data) / sizeof(data[0]);
    int i;
    // QuickSort(data,dataSize);
    BubbleSort(data, dataSize, true);
    for (int i = 0; i < dataSize; i++)
    {
        printf("%d ", data[i]);
    }printf("\n");
 
    return 0;
}