버블 정렬

버블 정렬은 정렬되는 모습이 거품이 일어나는 듯하다 해서 버블 정렬이다.

 

버블 정렬은 인접한 데이터와 자신을 비교하여 기준에 따라 정렬하는 것을 무수히 반복하면 된다.

 

문장에서 '기준'과 '무수히'라는 표현이 애매하게 만드는 것 같다.

 

기준은 오름차순 정렬을 기준으로 한다.

 

무수히는 데이터의 개수를 n개라 했을 때 n-1회 반복하면 된다.

 

n-1회는 최악의 경우를 고려하여 계산해 보면 알 수 있다.

 

버블 정렬은 인접한 데이터와 자신을 비교하여 자신이 크면 바꾸는 것을 n-1회 반복하면 된다.

 

void BubbleSort()
{
    int i = 0;
    int j = 0;
    int temp = 0;
    int DataSet[10] = { 5, 6, 9, 1, 2, 4, 3, 7, 8, 10 };
    Length = sizeof(DataSet) / sizeof(DataSet[0]);

    for (i = 0; i < Length - 1; i++)
    {
        for (j = 0; j < Length; j++)
        {
            if (DataSet[j] > DataSet[j + 1])
            {
                temp = DataSet[j + 1];
                DataSet[j + 1] = DataSet[j];
                DataSet[j] = temp;
            }
        }
    }
}

여기서 한사이클 이 돌때, 배열의 제일 마지막은 정렬이 완료 되므로 다음과 같이 수정할 수 있다.

void BubbleSort()
{
    int i = 0;
    int j = 0;
    int temp = 0;
    int DataSet[10] = { 5, 6, 9, 1, 2, 4, 3, 7, 8, 10 };
    Length = sizeof(DataSet) / sizeof(DataSet[0]);

    for (i = 0; i < Length - 1; i++)
    {
    	// 수정된 부분
        for (j = 0; j < Length - (i + 1); j++)
        {
            if (DataSet[j] > DataSet[j + 1])
            {
                temp = DataSet[j + 1];
                DataSet[j + 1] = DataSet[j];
                DataSet[j] = temp;
            }
        }
    }
}