C++/왕복버블정렬 알고리즘

 

풀이.

#include "config.h"
 
void main() {
 
    int d[] = { 21, 1, 19, 10, 5, 39, 4, 74, 64, 99 };    // 예시로 든 숫자
    int n = 10;
    int left = 0, right = 9, shift, i;
    // left =>  왼쪽에서 오른쪽으로 비교할 때 정렬하기 위한 비교를 실행하는 시작 위치
    // right => 오른쪽에서 왼쪽으로 비교할 때 정렬하기 위한 비교를 실행하는 시작 위치
    // shift => 마지막으로 값 교환이 실행된 위치 => 중요!!
 
    while (left < right) {
 
//        먼저 왼쪽에서 오른쪽으로 비교하며 정렬한다.
        i = left;
        while (i < right) {
            if (d[i] > d[i + 1]) {
                swap(d[i], d[i + 1]);
//        값 교환이 실행되었으므로 마지막으로 값 교환이 실행된 위치를 기억하는 변수인 shift에 값 교환이 실행된 위치(i)를 넣어준다.
                shift = i;    // 마지막으로 값 교환이 이루어진 자리를 기억함으로서, swift 자리부터 다시 돌리면 됨.  i 가 swift 가 되어야 함.
            }
            i++;
        }
        right = shift;
 
//        오른쪽에서 왼쪽 비교 정렬.
        i = right;
        while (i > left) {
            if (d[i - 1] > d[i]) {
                swap(d[i], d[i - 1]);
                shift = i;
            }
            i--;
        }
        left = shift;
 
    }
 
    printf("정렬 결과 : ");
    for (int i = 0; i < 10; i++) {
        printf("%d\n", d[i]);
    }
    printf("\n");
 
 
}
 

 

주석 없는 ver.

#include "config.h"
 
void main() {
    int d[] = { 21, 1, 19, 10, 5, 39, 4, 74, 64, 99 };
    int left = 0, right = 9, shift, i;
 
    while (left < right) {
        i = left;
        while (i < right) {
            if (d[i] > d[i + 1]) {
                swap(d[i], d[i + 1]);
                shift = i;
            }
            i++;
        }
        right = shift;
        i = right;
        while (i > left) {
            if (d[i - 1] > d[i]) {
                swap(d[i], d[i - 1]);
                shift = i;
            }
            i--;
        }
        left = shift;
 
    }
 
    printf(" 정렬 결과 : ");
    for (int i = 0; i < 10; i++) {
        printf("%d\n", d[i]);
    }
    printf("\n");
 
}