버블정렬 (Bubble Sort) | (+Special Sort)

​- 버블정렬(Bubble Sort) -

 

탐색해나갈 경계(i)를 정하고

현재 위치(j)의 바로 옆 위치(j+1)의 원소들과 비교, 맞바꾸는 정렬

 

---

 

문제인식)

다음 그림과 같은 수(數)의 배열이 있다.

int a[10] = {10, 2, 1, 9, 7, 4, 5, 8, 6, 3};

 

이 배열을 오름차순 정렬, 즉 가장 작은 수부터 차례대로 정렬하기 위해선 어떻게 프로그래밍 해야할까?

 

---

 

해결과정)

1) 탐색해나갈 범위의 경계를 잡는다.

2) 범위를 잡았으면 현재 위치의 바로 옆 원소와 비교, 맞바꾸기를 경계전까지 연속적으로 실행해나간다.

 

(※ [더보기]를 클릭하면 C/C++ 소스코드를 참조할 수 있습니다.)

int n, i, j, idx, tmp;
int a[10] = {10, 2, 1, 9, 7, 4, 5, 8, 3, 6};

n=10; //배열의 크기

for(i=n-1; i>=0; i--) {
    for(j=0; j<=i-1; j++) {
        if(a[j]>a[j+1]) {
            tmp=a[j];
            a[j]=a[j+1];
            a[j+1]=tmp;
        }
    }
}

 

실질적으로 정렬이 이뤄지는 안쪽 for문은

바로 옆 원소와 비교하여 더 큰 값을 우측으로 밀어낸다.

안쪽 for문이 끝나면 가장 큰 값이 가장 오른쪽으로 밀려나갈 것이다.

 

바깥쪽 for문은 탐색 범위를 우측에서 한 칸 줄어들면서 진행되어간다.

이렇게 하면 결국은 오름차순 정렬이 될 것이다.

 

사실 버블정렬은 매 순간마다 비교와 swap을 하기 때문에

같은 O(n²)의 정렬 알고리즘에 비해서도 시간은 더욱 걸릴 것이다.

 

메인 함수와 출력까지 나타낸 최종 코드는 다음과 같다.(C/C++)

#include <stdio.h>

int main() {
    int n, i, j, idx, tmp;
    int a[10] = {10, 2, 1, 9, 7, 4, 5, 8, 3, 6};

    n=10; //배열의 크기

    for(i=n-1; i>=0; i--) {
        for(j=0; j<=i-1; j++) {
            if(a[j]>a[j+1]) {
                tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
            }
        }
    }

    for(i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
	
	return 0;
}

 

---

 

응용)

내림차순 정렬해보기,

 

탐색경계(i)를 감소하는 방향이 아닌 증가하는 방향으로 설정해보기,

 

Special Sort

(※ [더보기]를 클릭하면 Special Sort의 설명과 소스코드를 미리 볼 수 있습니다.)

(※ Special Sort를 별개의 포스트로 올리진 않겠습니다.)

- Special Sort -

 

[문제]

n개의 정수가 입력되면,

음의 정수, 양의 정수의 나열순서는 각각 유지하되

음의 정수들은 양의 정수들의 왼편에 위치하도록 정렬하시오.

 

[입력]

첫째 줄에 배열의 크기 n이 주어진다.

둘째 줄엔 차례대로 배열의 원소가 n개씩 주어진다.

 

[입력예]

8

1 2 3 -3 -2 5 6 -6

 

[출력]

-3 -2 -6 1 2 3 5 6

 

[소스코드]

.

.

.

#include <stdio.h>

int main() {
    int n, a[101], i, j, tmp, pos=0;
    scanf("%d", &n);
    for(i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }

    for(i=0; i<n; i++) {
        if(a[i]<0) {
            for(j=i; j>pos; j--) {
                tmp=a[j];
                a[j]=a[j-1];
                a[j-1]=tmp;
            }
            pos++;
        }
    }

    for(i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
	
	return 0;
}

 

등