백준 2750 C언어 (버블정렬 구현과 성능평가)

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

---

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

---

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

 

버블정렬 - 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식. 두 데이터룰 비교하여 , 위치가 바뀌어야 하는 경우 두 데이터의 위치를 바꿔나간다. 

 

예를 들어 오름차순 기준으로, 배열의 크기가 4이고 배열의 값이 [5,3,8,1] 일때 버블정렬의 구현과정을 알아보겠다.

 

 

 

 

출처 - https://javaplant.tistory.com/16

버블정렬 버블소트 BubleSort 자바구현

 

버블정렬의 성능평가 : 데이터의 개수가 n개일때 진행되는 비교의 횟수는 (n-1)+(n-2)+..+2+1

->버블정렬의 비교연산에 대한 빅-오는 최악의 경우, 최선의 경우 구분없이 O(n²)이다.

 

전체 소스 코드

#include <stdio.h>

void Bubblesort(int arr[],int n){ 

    int i,j;

    int temp;

    for(i = 0;i<n-1;i++){ //n-1번 연산

        for(j = 0;j<(n-i)-1;j++){ //인덱스 비교 연산

            if(arr[j]>arr[j+1]){ //스왑히는 연산

                temp = arr[j];

                arr[j] = arr[j+1];

                arr[j+1] = temp;

            }

        }

    }

}

 

int main(void){

    int n;

    int arr[1000];

    scanf("%d",&n);

    for(int i = 0;i<n;i++){

        scanf("%d",&arr[i]);

    }

    Bubblesort(arr,n);

    for(int i = 0;i<n;i++){

        printf("%d\n",arr[i]);

    }

}