변형된 버블정렬 (Bubble Sort)

변형된 버블정렬 (Bubble Sort)

앞서 했던 버블정렬은 리스트에 존재하는 값중 제일 큰 값을 찾아 리스트의 오른쪽 끝으로 밀어버리고,

그 다음 큰 값을 찾아 제일 오른쪽 자리를 제외한 오른쪽 끝으로 다음 큰 값을 밀어버리는 방법을 사용했다.

이번에 사용할 방법은 리스트에 존재하는 값중 제일 작은값을 첫 번째 자리에 확정하고,

그 다음 작은 값을 찾아 두 번째 자리에 확정, 그 다음 작은 값을 찾아 세 번째 자리에 확정하는 방식을 이용할 것이다.

※ 앞서했던 버블정렬과 변형된 버블정렬에 차이는?

결론만 말하자면 차이가 없다.

형태만 조금 다를뿐 기능과 연산량은 같다고 생각하면 된다.

구지 차이점을 말하자면 코드 길이가 조금 더 길다의 차이일 뿐이다.

▷ 정렬방법

1. 첫 번째 자리에 잡은 값을 중심으로 나머지 값들을 비교 한다.

2. 첫 번째에 자리한 값보다 비교하는 값이 작다면 자리를 바꾼다.

3. 이를 리스트의 끝까지 반복한다.

4. 첫 번째 비교 및 교환이 끝났다면 중심 값(자리)를 두 번째로 바꾼다.

5. 중심 값(자리)가 리스트의 끝 까지 갈때까지 이를 반복한다.

※ [ ]은 중심 값이다.

시작 : 5, 7, 3, 4, 9, 1

0.   [5], 7, 3, 4, 9, 1 - 5와 7을 비교 교환 X

1.   [5], 7, 3, 4, 9, 1 - 5와 3을 비교 교환 O

     [3], 7, 5, 4, 9, 1

2.   [3], 7, 5, 4, 9, 1 - 3과 4를 비교 교환 X

3.   [3], 7, 5, 4, 9, 1 - 3과 9를 비교 교환 X

4.   [3], 7, 5, 4, 9, 1 - 3과 1을 비교 교환 O

     [1], 7, 5, 4, 9, 3

5.   1, 7, 5, 4, 9, 3

다음은 2번째 자리의 값을 중심으로 그 뒤의 있는 값들을 위와 같은 방식으로 비교 및 교환 한다.

앞의 값들은 이미 정렬된 값이므로 비교하지 않아도 된다.

Code

#include <iostream>
using namespace std;
 
#define MAX            6
 
void BubleSort(int *Number );
void main()
{
    int Number[MAX] = {5,7,3,4,9,1};
 
    BubleSort( Number );
 
    for(int i = 0; i < MAX; i++)
        printf("%d \n", Number[i] );
}
 
void BubleSort(int *Number)
{
    for(int i = 0; i < MAX; i++)
    {
        for(int j = i + 1; j < MAX; j++)
        {
            if(Number[i] > Number[j])
            {
                int Temp = Number[i];
                Number[i] = Number[j];
                Number[j] = Temp;
            }
        }
    }
}

결과