[Algorithm] 버블정렬(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. Bubble sort 는 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다.

     첫 번째 원소부터 마지막 원소가지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.

     하지만,, 굉장히 비효율적인 방법이기 때문에 잘 쓰이려나..?

     시간복잡도도 selection sort 와 같이 좋진 않다. ㅋ..ㅋ

     Best : O(n^2)

     Average : O(n^2)

     Worst : O(n^2)

     정렬 이름과 같이 거품처럼 계속 보글보글 정렬을 수행한다.

     귀찮지만 과정을 한번 그려볼까..?

     13 23 11 7 5 15 를 정렬한다고 해보자.

     [ i = 0 ]

     13 23 11 7 5 15

     13 23 11 7 5 15  (13은 23보다 작으므로 pass)

     

     13 23 11 7 5 15

     13 11 23 7 5 15 (23은 11보다 크므로 교환)

     

     13 11 23 7 5 15

     13 11 7 23 5 15  (23은 7보다 크므로 교환)

     

     13 11 7 23 5 15

     13 11 7 5 23 15 (23은 5보다 크므로 교환)

     13 11 7 5 23 15

     13 11 7 5 15 23 (15는 23보다 크므로 교환)

     여기서 보면 가장 큰 원소가 마지막 자리로 정렬된 것을 볼 수 있다.

     작은 친구는 계속 앞으로 가고 큰 친구는 계속 뒤로 밀려난다고 생각하면(?) 된다.    

     [ i = 1 ]

     13 11 7 5 15 23

     11 13 7 5 15 23 (13은 11보다 크므로 교환)

     ...

     위와 동일한 방법으로 계속 해보자. 보글보글.. 너무 교환 횟수가 많다

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, i, j, tmp;
    
    scanf("%d", &n);
    vector<int> v(n);
 
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);
 
    for (i = 0; i < n; i++)
    {
        for (j = 1; j < n; j++)
        {
            if (v[j] < v[j - 1])
            {
                tmp = v[j];
                v[j] = v[j - 1];
                v[j - 1] = tmp;
            }
        }
    }
 
    for (i = 0; i < n; i++)
        printf("%d ", v[i]);
 
    puts("");
 
    return 0;
}

#. Other code

#include <stdio.h>
 
int main() {
    int a[101], n, i, j, tmp;
 
    scanf("%d", &n);
 
    for(i=0; i<n; i++)
        scanf("%d", &a[i]);
    
    for(i=0; i<n-1; i++){
        for(j=0; j<n-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;
}

나는 왜 j 랑 j-1 로 비교했지?! 

버블정렬은 거품이 뒤로 버블버블하면서 교환되는데 나는 앞으로 버블버블하면서 교환되는 느낌이다.

그래도 결과가 같으면 상관없기야 하지만.. 

무튼 더 중요한 것은

가장 큰 원소가 마지막 자리로 정렬된다는 것을 이용하여

j 는 n-i-1 만큼만 루프를 돈다는 것이다. 나는 n까지 계속 돌았는데, 결국 데이터가 커지면 불필요한 연산을 계속 하게 될 것이다.

알고리즘의 특징을 이용해서 더 효율적인 코드를 짜는 것도 중요한 것 같다.

#. Result

  - Input --------------------------------------------------------

6

13 23 11 7 5 15

------------------------------------------------------------------

  - Output --------------------------------------------------------

5 7 11 13 15 23

------------------------------------------------------------------