버블 정렬 Bubble Sort 오름차순으로 구현하기

버블 정렬 Bubble Sort 

---

성균관대학교 소프트웨어학과 조대호 교수님의 2020년도 2학기 알고리즘 수업을 듣고 수행한 과제입니다. 

값을 오름차순으로 정렬하는 버블 정렬을 C로 구현한 코드입니다. 

• pseudo code 

BUBBLE_SORT(A):
1. for i = 0 to A.length
2. 	for j = 0 to A.length-1
3. 		if A[j] > A [j+1]
4. 			swap A[j] and A[j+1]

• input and output conditions

/* 
- Test the function with the following three types of inputs.
 1) int A[100] : filled by rand()%1000, execute srand(time(NULL)) first, (stdlib.h, time.h should be included)
 (Duplicate keys are ignored.)
 
 2) int A[100] : already sorted (Write a function for filling in A[])
 
 3) int A[100] : reversely sorted “
 - Print A, before and after sorting for each case of input. - Give the number of comparisons for each case of input
*/

• source code

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int bubble_sort(int* A) {
    int i, j;
    int count = 0;
    for (i = 0; i < 100; i++) {
        for (j = 0; j < 99 - i; j++) {
            if (A[j] > A[j + 1]) {
                int temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
                count++;
            }
        }
    }
    return count;
}

int print(int* A) {
    int i;
    for (i = 0; i < 100; i++) {
        printf(" %d", A[i]);
    }
    printf("\n");
    printf("\n");
    return 0;
}

int main() {
    int i;
    int A[100];

    printf("=========================================BUBBLE SORT=================================================\n");

    /* (a) random */
    printf("(1) randomly filled array\n\n");
    srand(time(NULL));
    for (i = 0; i < 100; i++) {
        A[i] = rand()%1000;
    }
    print(A);
    int count = bubble_sort(A);
    printf("after bubble sorted\n\n");
    print(A);
    printf("number of comparison: %d\n", count);
    printf("============================================================================================================\n");

    /* (b) sorted */
    printf("(2) sorted array\n\n");
    for (i = 0; i < 100; i++) {
        A[i] = i;
    }
    print(A);
    count = bubble_sort(A);
    printf("after bubble sorted\n\n");
    print(A);
    printf("number of comparison: %d\n", count);
    printf("============================================================================================================\n");


    /* (c) reversly sorted */
    printf("(2) reversly sorted array\n\n");
    for (i = 0; i < 100; i++) {
        A[i] = 99-i;
    }
    print(A);
    count = bubble_sort(A);
    printf("after bubble sorted\n\n");
    print(A);
    printf("number of comparison: %d\n", count);
    


    return 0;
}

• result 

버블 정렬에서 각 경우마다 comparison operation이 발생한 횟수는 다음과 같습니다. 

• 배열이 랜덤으로 채워진 경우 : 2656
• 배열이 이미 정렬된 경우 : 0
• 배열이 반대로 정렬되어 있는 경우 : 4950

다음 결과를 바탕으로 버블 정렬은 주어진 배열이 이미 정렬되어 있는 상태라면 아주 효율적인 정렬 알고리즘이라는 것을 알수 있습니다. 하지만 반대로 정렬되어 있는 경우는 최악의 성능을 보이지만 이런 경우는 드물기 때문에 대체로 효율적인 알고리즘이라고 생각됩니다.