* Bubble Sort

마치 거품방울이 뽀글뽀글 올라가는 모양과 비슷하다하여 붙어진 이름이다.
Bubble Sort는 두가지만 알고 있으면 된다.

1. 두가지 값을 비교
2. 두값을 swap함

백문이 불여일견이다.

// Bubble sort
void bubble_sort(int size , int* val)
{
     for (int i = 0 ; i < size - 1; i++)
    {
          for (int j = 0 ; j < size - 1 - i ; j++)
         {
              if (val[j] > val[j+1])
              {
                    int tmp = val[j];
                    val[j] = val[j+1];
                    val[j+1] = tmp;
              } 
         }
   }
}

예로 다음 배열을 Bubble Sort 해보이겠다.
{ 9 , 7 , 3 , 5 , 1 , 7 , 2 }

우선 첫 Loop에서의 모습을 보이겠다.
9 7 3 5 1 7 2
7 9 3 5 1 7 2
7 3 9 5 1 7 2
7 3 5 9 1 7 2
7 3 5 1 9 7 2
7 3 5 1 7 9 2
7 3 5 1 7 2 9

마치 왼쪽이 밑이고 오른쪽이 위라고 생각하면 9라는 값은 마치 거품방울이 올라가듯
뽀글뽀글 올라가는 것이 보인다 @^-^@

다음은 7 값이 올라가게 될것이다.

결국  1 2 3 5 7 7 9 로 정렬이 될 것이다.



* 장점
  1. 알고리즘이 간단하다.
2. 2중 Sorting이 간편하다. 즉, 학번순으로 정렬을 한뒤 같은 학번내에서 이름순의 정렬이
     가능해진다.

* 단점
  1. 성능이 O(n^2)으로 약간 느리다고 할 수 있다.


연속하는 날들에 대하여 각 날의 주식 가격이 주어져 있다. 이때 어떤 날에 주식을 산 후, 최대 이익을 남기며 이후의 날에 팔고자 한다. 어떤 날에 사서 어떤 날에 팔면 되는가?

두 가지 방법으로 해결하라.

방법 1: O(n2) 시간의 알고리즘

방법 2: 분할과 정복을 이용한 O(n log n) 알고리즘


입력 예

3 // 날 수
9 1 5 // 첫째 날 주식 가격: 9, 둘째 날 주식가격: 1, 셋째 날 주시가격: 5

출력 예

사는 날: 2일째
파는 날: 3일째





test 화일을 올려놉니다.







저는 O(n)의 속도로 탐색하는 알고리즘을 생각했습니다.
매우 빠른 속도로 동작하며, min , max 값의 원리를 이용하였습니다.

data : int 배열
len : 배열의 길이
buy : 주식을 사야하는 날 저장 공간
sell : 주식을 팔아야하는 날 저장 공간

중요 함수 부분입니다.


'도서관 I > Algorithm' 카테고리의 다른 글

[바람이] Bubble Sort  (0) 2006.05.25

+ Recent posts