태극기 왼쪽 배너
BLOG main image
all category (187)
Notice (7)
Daily life (62)
secret note (73)
Utility (5)
play (26)
Multimedia (13)
secret (0)
Fitness DNA tests
Fitness DNA tests
Edmond Mueller
NEW CHALLENGE - kaspersky lice..
Ugg España
Ugg España
Longchamp España
Longchamp España
3d building construction
3d building construction
hit counters
331,522 Visitors up to today!
Today 0 hit, Yesterday 3 hit
daisy rss
tistory 티스토리 가입하기!
2010. 9. 5. 19:35

  1. bubble sort ( 버블 정렬 ) 의 정의


    bubble sort ( 버블정렬 ) 의 진행과정이 마치 비누거품 ( bubble ) 같다고 하여 이름 붙여졌다. 인접한 elements 들 간의 반복적인 swap ( 교환 ) 을 이용해 정렬을 한다.



  2. bubble sort ( 버블 정렬 ) 의 수행방법


    bubble sort ( 버블정렬 ) 는 인접한 두 elements 들을 비교해 정렬이 되어 있지 않을 경우에 서로 위치를 바꾸는 방식으로 처음부터 끝까지 한번 진행한다. 한번의 loop 를 돌게 되면 가장 커다란 elements 가 맨 마지막에 위치하게 되고 이 elements 를 제외하고 다시 loop를 돌아 마지막까지 비교를 하게된다.

    수행 방법이 단순하므로 예제를 보면 쉽게 이해가 된다.


  3. bubble sort ( 버블 정렬 ) 의 예제


     bubble sort ( 버블 정렬 ) 의 간단한 예제를 보자

    example input { 2 11 5 3 23 4 } 이라고 할 때,

    1. 2 11 5 3 23 4 | ( 2, 11 비교 11이 더 크므로 교환하지 않는다 )
    2. 2
    11 5 3 23 4 | ( 11, 5 비교 11이 더 크므로 5와 교환한다 ) 
    3. 2 5
    11 3 23 4 | ( 11, 3 비교 11이 더 크므로 3과 교환한다 )
    4. 2 5 3
    11 23 4 | ( 11, 23 비교 23이 더 크므로 교환하지 않는다 )
    5. 2 5 3 11 23 4 | (23, 4 비교 23이 더 크므로 4와 교환한다 )
    6. 2 5 3 11 4 | 23 ( 한번의 loop 완료. 가장 큰 수 23을 가장 오른쪽으로 배치했다 )
    7.
    2 5 3 11 4 | 23 ( 2, 5 크기비교 교환하지 않는다 )
    8. 2
    5 3 11 4 | 23 ( 5, 3 크기비교 교환한다. )
    9. 2 3
    5 11 4 | 23 ( 5, 11 크기비교 교환하지 않는다 )
    10. 2 3 5
    11 4 | 23 ( 11, 4 크기비교 교환한다 )
    11. 2 3 5 4 | 11 23 ( 남은 elements 중에서 가장 큰 수 11을 오른쪽으로 배치 )
    12.
    2 3 5 4 | 11 23 ( 2,5 크기비교 교환하지 않는다 )
    13. 2
    3 5 4 | 11 23 ( 3,5 크기비교 교환하지 않는다 )
    14. 2 3
    5 4 | 11 23 ( 5,4 크기비교 교환한다 )
    15. 2 3 4 | 5 11 23 ( 5 정렬완료 오른쪽 배치됨 )
    16.
    2 3 4 | 5 11 23 ( 2,3 크기비교 교환하지 않는다 )
    17.
     2 3 4 | 5 11 23 ( 3,4 크기비교 교환하지 않는다 )
    18.
     2 3 | 4 5 11 23 ( 4 정렬완료 오른쪽 배치됨 )
    19. 
    2 3 | 4 5 11 23 ( 2,3 크기비교 교환하지 않는다 )
    20. 2 | 3 4 5 11 23 ( 3 정렬완료 오른쪽 배치됨 , bubble sort 종료 )

    이처럼 모든 elements 들을 다 비교하는 방식이다.



  4. bubble sort ( 버블 정렬 ) 의 특징



    bubble sort ( 버블정렬 ) 의 비교횟수는 elements 의 상태, 크기와 상관없이 최상, 최악, 평균의 어떠한 경우라도 같은 비교횟수를 가진다. 오직 elements의 수에만 영향을 받는다. 
    또한 bubble sort ( 버블정렬 ) 은 인접한 두 elements 중 왼쪽 elements 가 더 큰 경우에만 교환을 하므로 같은 크기의 elements 들은 원래의 상대적인 순서를 정렬 후에도 유지하게 된다 ( stability를 가진다 )



  5. bubble sort ( 버블 정렬 ) 의 구현

    void bubbleSort( int a[], int n ){
    int i,j,temp;
    for ( i = 0; i < n-1 ; i++ ){
    for ( j = 1 ; j < i-1 ; j ++){
    if( a[j-1] > a[j] ){
    temp = a[j-1];
    a[j-1] = a[j];
    a[j] = temp;
    }
    }
    }
    }

    bubble sort ( 버블 정렬 ) 의 간단한 알고리즘이다. 이 알고리즘에는 최적화의 가능성이 존재하는데 j loop가 수행되면서 한번도 교환이 일어나지 않았다면 그 배열은 이미 정렬이 완료된 상태이라는 것을 알 수 있다. 이러한 상태를 확인하기 위해서 flag를 만들어 확인하는 방법을 쓸 수 있는데 정렬 도중에 flag를 사용할 상황 ( 정렬 중간에 정렬이 완료된 경우 ) 이발생하지 않을 경우에 ( 정렬 중간에 정렬이 완료되지 않을 경우 ) 에는 flag는 아무 역할도 하지 못해 리소스만 낭비하게 될 수도 있다. 하지만 거의 정렬된 배열의 경우에는 커다란 효과를 보게된다.



  6. bubble sort ( 버블 정렬 ) 의 최적화


    void bubbleSort( int a[], int n ){
    int i,j,temp;
    bool Ischange;
    for ( i = 0; i < n-1 ; i++ ){
    Ischange = false;
    for ( j = 1 ; j < i-1 ; j ++){
    if( a[j-1] > a[j] ){
    temp = a[j-1];
    a[j-1] = a[j];
    a[j] = temp;
    Ischange = true;
    }
    if(Ischange == false)
    break;
    }
    }
    }



'secret note > algorithm' 카테고리의 다른 글

bubble sort ( 버블 정렬 )  (24) 2010.09.05
Insertion Sort ( 삽입정렬 )  (1) 2010.09.03
이전 댓글 더보기
Favicon of http://cdptth1.vov.vn/page.aspx BlogIcon jordan 5 black | 2013.09.24 13:50 | PERMALINK | EDIT/DEL | REPLY
Attractive section of content. I just stumbled upon your weblog and in accession capital to assert that I get actually enjoyed account your blog posts. Any way I抣l be subscribing to your augment and even I achievement you access consistently rapidly. ,jordan 5 bel air,http://www.aivietnam.net/web.aspx tnxz,jordan 5 fire red http://www.aivietnam.net/web.aspx, nojh
ATeeseEscal | 2014.12.22 00:00 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
BlogIcon Lizhuzhubuik | 2014.12.23 01:56 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Xleignsd | 2014.12.23 13:43 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Xleignsd | 2014.12.23 14:08 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
BlogIcon Lizhuzhuburm | 2014.12.23 21:43 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Xleignsd | 2014.12.24 02:37 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
BlogIcon Lizhuzhubusj | 2014.12.24 07:21 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
BlogIcon Lizhuzhubuna | 2014.12.29 18:58 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
BlogIcon Lizhuzhubuek | 2014.12.30 09:39 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Favicon of http://www.hhpz.org/mobile/cf/ugg.asp BlogIcon weiweirln | 2014.12.31 07:28 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Favicon of http://www.hhpz.org/mobile/cf/ugg.asp BlogIcon weiweiyqr | 2014.12.31 07:59 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Favicon of http://www.taylormali.com/photo/bags.php BlogIcon weiweimuh | 2015.01.05 04:10 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Favicon of http://www.taylormali.com/photo/bags.php BlogIcon weiweisrt | 2015.01.05 04:32 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Favicon of http://www.taylormali.com/photo/bags.php BlogIcon weiweihbc | 2015.01.05 20:42 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Favicon of http://www.taylormali.com/photo/bags.php BlogIcon weiweitrh | 2015.01.06 06:20 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
BlogIcon BonnieSash | 2015.01.12 03:29 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Favicon of http://www.northshoreband.org/map/mall.php BlogIcon weiweiliq | 2015.01.19 13:43 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Favicon of http://www.northshoreband.org/map/mall.php BlogIcon weiweijjm | 2015.01.19 14:25 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
BlogIcon LaurenSep | 2015.01.26 03:40 | PERMALINK | EDIT/DEL | REPLY
이용약관위배로 관리자 삭제된 댓글입니다.
Name
Password
Homepage
Secret