버블 정렬

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '버블 정렬'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2016년 11월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

버블 정렬

버블[1] 정렬의 정적 시각화
학급	정렬 알고리즘
data 구조	어레이
최악의 경우 성능	${\displaystyle O}$( ${\displaystyle {n\mathrm{}}^{}}$ 2$$) { $displaystyle$O ( $n$^ {$2$} } 비교$$,${\displaystyle }O{\displaystyle }$ ( ${\displaystyle {}^{}{2\mathrm{}}^{}}$) { $display style$O ( $n$^ {2} $)$스왑$$
베스트 케이스 성능	$)$ {$displaystyle$ O$(n$$)}$ 비교$$, $O{\displaystyle }$(1)${\displaystyle }${$displaystyle$ O(1)}$스왑$
평균 성능	${\displaystyle O}$( ${\displaystyle {n\mathrm{}}^{}}$ 2$$) { $displaystyle$O ( $n$^ {$2$} } 비교$$,${\displaystyle }O{\displaystyle }$ ( ${\displaystyle {}^{}{2\mathrm{}}^{}}$) { $display style$O ( $n$^ {2} $)$스왑$$
최악의 경우 공간의 복잡성	${\displaystyle O}$(${\displaystyle n}$ )$${ $displaystyle$O ($n$ ) }합계$$${\displaystyle ,}$ $O{\displaystyle }$ ( ${\displaystyle 1}$)$${ $displaystyle$O (1$)$}보조$$

버블 정렬(싱킹 정렬이라고도 함)은 목록을 반복하여 단계별로 이동하고, 인접한 요소를 비교하고, 순서가 잘못된 경우 스왑하는 단순한 정렬 알고리즘입니다.목록이 정렬될 때까지 목록 통과가 반복됩니다.비교 정렬인 알고리즘은 더 작거나 더 큰 요소가 목록의 맨 위로 "버블"되는 방식을 위해 명명되었습니다.

이 단순한 알고리즘은 실제 사용에서는 성능이 떨어지고 주로 교육 도구로 사용됩니다.QuickSort, timsort 또는 Marge sort와 같은 보다 효율적인 알고리즘은 Python이나 ^[2][3]Java와 같은 인기 있는 프로그래밍 언어에 내장된 정렬 라이브러리에서 사용됩니다.

분석.

버블 정렬의 예입니다.리스트의 선두부터, 인접하는 모든 페어를 비교하고, 순서가 올바르지 않은 경우는 그 페어의 위치를 바꿉니다(후자의 페어가 앞의 페어보다 작습니다.각 반복 후 비교할 요소가 더 이상 없을 때까지 비교할 요소(마지막 요소)가 하나 줄어듭니다.

성능

버블 정렬은 O${\displaystyle }$($$ 2) { $displaystyle$O ( $n$^ {$$$2$} )의 $최악$의 경우 평균 복잡도를 가집니다.$여기서$n { $displaystyle$ n$$}은$$ 정렬되는 항목의 수입니다.대부분의 실용적인 정렬 알고리즘은 최악의 경우 또는 평균적인 복잡도가 상당히 우수합니다${\displaystyle (\mathrm{종종}}$ O(n log${\displaystyle n}$n )$$\ $display$ $style$ O$(n\$$log$n )$$。$삽입$ 정렬 등의 다른 O($n$2)${\displaystyle }$정렬 알고리즘도 일반적으로 버블 정렬보다 빠르게 실행되며 복잡하지 않습니다.이러한 이유로 버블 정렬은 실제로 거의 사용되지 않습니다.

삽입 정렬과 마찬가지로 버블 정렬은 적응성이 뛰어나 빠른 정렬과 같은 알고리즘보다 유리합니다.즉, 평균 케이스의 시간 복잡성이 더 심하지만 목록이 이미 대부분 정렬된 경우(반전 횟수가 적음)에는 이러한 알고리즘을 능가할 수 있습니다.예를 들어, 이미 정렬된 목록에서 버블 $정렬$은 O${\displaystyle }$(${\displaystyle n}$) \ $displaystyle O$( ${\displaystyle n}$ ) \ $displaystyle$ O $( n$ ) \ $n }$ 의$$$$ 정렬 $프로세스{\displaystyle }$ 전체가 실행됩니다${\displaystyle .}$

정렬 알고리즘은 실행 전에 목록을 확인하는 것만으로 사전 정렬 목록에서 O$)\displaystyle$ O$(n)$로 $만들{\displaystyle }$ 수 있지만 거의 정렬된 목록에서 향상된 성능을 복제하기가 어렵습니다.

토끼와 거북이

요소가 서로 다른 속도로 서로 다른 방향으로 이동하기 때문에 정렬 중에 요소가 이동해야 하는 거리와 방향에 따라 거품 정렬의 성능이 결정됩니다.목록의 끝으로 이동해야 하는 요소는 연속적인 스왑에 참여할 수 있기 때문에 빠르게 이동할 수 있습니다.예를 들어 목록에서 가장 큰 요소가 모든 스왑을 이기므로 시작 부근에서 시작하더라도 첫 번째 패스에서 정렬된 위치로 이동합니다.반면 목록의 선두로 이동해야 하는 요소는 통과당 한 단계보다 빠르게 이동할 수 없기 때문에 요소가 선두로 이동하는 속도가 매우 느립니다.가장 작은 요소가 목록의 끝에 있는 경우, 처음 요소로 이동하려면 n${\displaystyle }$- $({displaystyle n-1})$ 패스가$$ $필요$합니다.이로 인해 이솝 우화인 거북이와 토끼의 이름을 따 토끼와 거북이라는 이름이 붙여졌다.

거품 정렬 속도를 높이기 위해 거북이를 제거하기 위한 다양한 노력이 이루어지고 있다.칵테일 정렬은 처음부터 끝까지 진행되며, 그 후 거꾸로 진행되어 처음부터 끝까지 진행되는 양방향 버블 정렬입니다.거북이를 꽤 잘 움직일 수 있지만${\displaystyle ,}$ 최악의 경우$$ O$(n$2${\displaystyle {}^{}}$의 복잡성을 $유지$합니다.빗 정렬은 큰 갭으로 구분된 요소를 비교하여 작은 갭으로 이동하기 전에 거북이를 매우 빠르게 이동시켜 목록을 부드럽게 만듭니다.평균 속도는 퀵소트와 같은 빠른 알고리즘에 버금간다.

단계별 예시

숫자 "5 1 4 2 8"의 배열을 선택하고 버블 정렬을 사용하여 배열을 가장 작은 수부터 가장 큰 수까지 정렬합니다.각 단계에서 굵은 글씨로 표시된 요소를 비교합니다.3번의 패스가 필요하다.

퍼스트 패스

( 5 1 4 2 8 ) → ( 1 5 4 2 8 )여기서 알고리즘은 처음 두 요소를 비교하고 5 > 1 이후 스왑합니다.

( 1 5 4 2 8 ) → ( 1 4 5 2 8 ) 、 5 > 4 。

( 1 4 5 2 8 ) → ( 1 4 2 5 8 ) 、 5 > 2 。

( 1 4 2 5 8 ) → ( 1 4 2 5 8 ) 。이러한 요소는 이미 순서(8 > 5)이므로 알고리즘은 이들을 스왑하지 않습니다.

세컨드 패스

( 1 4 2 5 8 ) → ( 1 4 2 5 8 )

( 1 4 2 5 8 ) → ( 1 2 4 5 8 ) 、 4 > 2 。

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

현재 어레이는 이미 정렬되어 있지만 알고리즘은 어레이가 완료되었는지 여부를 알 수 없습니다.알고리즘이 정렬되었는지 확인하기 위해서는 스왑 없이 1개의 추가 전체 패스가 필요합니다.

서드 패스

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

실행

의사 코드의 실장

의사 코드에서 알고리즘은 (0 기반 배열)로 나타낼 수 있습니다.

절차. 버블소트(A : 목록. 의 정렬 가능한 항목들)     n := 길이(A)     따라하다         스왑했다 := 거짓의         위해서 i := 1 로. n-1 포괄적 하다             /* 한다면 이것. 짝 이 나가. 의 주문 */             한다면 A[i-1] > A[i] 그리고나서                 /* 바꾸다 그들. 그리고. 기억하세요. 뭔가 변경되었다. */                 바꾸다(A[i-1], A[i])                 스왑했다 := 진실의             끝. 한다면         끝. 위해서     까지 것은 아니다. 스왑했다 끝. 절차. 

버블 정렬 최적화

버블 정렬 알고리즘은 n번째 패스가 n번째로 큰 요소를 찾아 최종 위치에 배치하는 것을 관찰함으로써 최적화할 수 있습니다.따라서 내부 루프는 n번째 실행 시 마지막 n-1 항목을 보는 것을 피할 수 있습니다.

절차. 버블소트(A : 목록. 의 정렬 가능한 항목들)     n := 길이(A)     따라하다         스왑했다 := 거짓의         위해서 i := 1 로. n - 1 포괄적 하다             한다면 A[i - 1] > A[i] 그리고나서                 바꾸다(A[i - 1], A[i])                 스왑했다 := 진실의             끝. 한다면         끝. 위해서         n := n - 1     까지 것은 아니다. 스왑했다 끝. 절차. 

일반적으로 여러 요소가 단일 패스의 최종 위치에 배치될 수 있습니다.특히 통과될 때마다 마지막 스왑 이후의 모든 요소가 정렬되므로 다시 확인할 필요가 없습니다.이를 통해 많은 요소를 건너뛸 수 있으므로 최악의 경우 비교 카운트가 50% 정도 향상됩니다(스왑 카운트는 개선되지 않음). 또한 새 코드에는 "스왑" 변수가 포함되므로 복잡성은 거의 없습니다.

이것을 의사 코드로 실현하려면 , 다음과 같이 기술할 수 있습니다.

절차. 버블소트(A : 목록. 의 정렬 가능한 항목들)     n := 길이(A)     따라하다         인식하다 := 0         위해서 i := 1 로. n - 1 포괄적 하다             한다면 A[i - 1] > A[i] 그리고나서                 바꾸다(A[i - 1], A[i])                 인식하다 := i             끝. 한다면         끝. 위해서         n := 인식하다     까지 n ≤ 1 끝. 절차. 

칵테일 셰이커 정렬과 같은 대체 수정은 인접한 항목을 반복적으로 비교 및 교환하는 동일한 생각을 유지하면서 버블 정렬 성능을 개선하려고 시도합니다.

사용하다

버블 정렬목록은 각 점(x, y)이 y 값이 지수 x에 저장되었음을 나타내는 데카르트 좌표계로 표시되었습니다.그런 다음 모든 픽셀 값에 따라 버블 정렬별로 목록이 정렬됩니다.가장 큰 끝부분이 먼저 정렬되고 작은 요소가 올바른 위치로 이동하는 데 시간이 걸립니다.

버블 정렬은 이해하고 구현하는 가장 간단한 정렬 알고리즘 중 하나이지만, O(n²)의 복잡성으로 인해 적은 수의 요소 목록에서 효율성이 크게 저하됩니다.단순한 O(n²) 정렬 알고리즘에서도 삽입 정렬과 같은 알고리즘이 일반적으로 훨씬 더 효율적입니다.

버블 정렬은 단순하기 때문에 컴퓨터 과학 입문생에게 알고리즘 또는 정렬 알고리즘의 개념을 소개하기 위해 자주 사용됩니다.하지만, 오웬 아스트라찬과 같은 일부 연구원들은 버블 정렬과 컴퓨터 과학 교육에서 버블 정렬의 지속적인 인기를 폄하하기 위해 더 이상 ^[4]버블 정렬을 배우지도 말 것을 권고했다.

보고소트를 "전형적이고 (sic) 비뚤어질 정도로 끔찍한 알고리즘"이라고 부르는 것으로 유명한 Jonesm File은 또한 버블 정렬을 "일반적인 나쁜 알고리즘"^[5]이라고 부릅니다.컴퓨터 프로그래밍의 예술에서 도널드 크누스는 "거품 정렬은 기억하기 쉬운 이름과 그것이 몇 가지 흥미로운 이론적인 문제로 이어진다는 사실 외에는 그것을 추천할 만한 것이 없는 것 같다"고 결론내렸고, 그 중 몇 가지는 그가 ^[6]논의했다.

버블 정렬은 최악의 경우 삽입 정렬까지의 실행 시간에서 점근적으로 동일하지만 필요한 스왑 횟수는 두 알고리즘이 크게 다릅니다.또한 Astrachan과 같은 실험 결과에서도 삽입 정렬이 랜덤 목록에서 훨씬 더 잘 수행된다는 것을 알 수 있었습니다.이러한 이유로 많은 최신 알고리즘 교과서는 삽입 정렬을 위해 버블 정렬 알고리즘을 사용하지 않습니다.

버블 정렬은 최신 CPU 하드웨어와도 잘 연동되지 않습니다.삽입 정렬보다 최소 2배 많은 쓰기, 2배 많은 캐시 누락 및 점근적으로 더 많은 분기 예측 ^{[citation needed]}오류를 생성합니다.Java에서 Astrachan 정렬 문자열에 의한 실험에서는 버블 정렬이 삽입 정렬의 약 1/5, ^[4]선택 정렬의 70%로 나타났습니다.

컴퓨터 그래픽스에서는 버블 정렬이 거의 정렬되지 않은 어레이에서 매우 작은 오류(예: 2개 요소의 스왑)를 검출하여 선형 복잡도(2n)만으로 수정할 수 있는 기능으로 널리 사용되고 있습니다.예를 들어 폴리곤 채우기 알고리즘에서 사용되며, 폴리곤 채우기 알고리즘에서는 경계선이 특정 스캔 라인(x축에 평행한 라인)에서 x좌표로 정렬되고 y가 증가하면 2개의 라인의 교차점에서만 순서 변경(2개의 요소가 교환됨)이 발생합니다.버블 정렬은 삽입 정렬과 같은 안정적인 정렬 알고리즘입니다.

바리에이션

• 홀수 짝수 정렬은 메시지 전달 시스템을 위한 버블 정렬의 병렬 버전입니다.
• 패스는 왼쪽에서 오른쪽으로가 아니라 오른쪽에서 왼쪽으로 할 수 있습니다.이것은 정렬되지 않은 항목이 끝에 추가된 목록의 경우 더 효율적입니다.
• 칵테일 쉐이커 정렬은 왼쪽 패스와 오른쪽 패스를 번갈아 가며 진행합니다.
• 정렬이 버블 정렬의 잘못된 버전으로 보이지만 삽입 ^[7]정렬과 유사한 방식으로 작동한다는 것을 공식적으로 증명할 수 있다는 것을 믿을 수 없습니다.

이름을 둘러싼 논쟁

버블 정렬은 때때로 "싱크 정렬"^[8]이라고 불립니다.

예를 들어, Donald Knuth는 원하는 위치에 값을 삽입하는 것은 "[값]이 적절한 수준으로 안정되도록 하는 것"이라며 "이 정렬 방법은 때때로 체 또는 침하 기술이라고 ^[9]불립니다.

이 논의는 두 가지 다른 관점에서 이 알고리즘을 쉽게 검토할 수 있도록 함으로써 지속된다.

1. 값이 클수록 무거워지기 때문에 리스트의 맨 아래까지 서서히 내려가는 것으로 보입니다.
2. 값이 작을수록 가벼워지기 때문에 리스트의 선두까지 버블이 점등합니다.

대중문화에서

2007년 에릭 슈미트 전 구글 최고경영자(CEO)는 인터뷰 도중 버락 오바마 당시 대선 후보에게 100만 정수를 분류하는 가장 좋은 방법에 대해 물었고 오바마는 잠시 멈춘 뒤 "버블 분류는 잘못된 ^[10][11]방법이라고 생각한다"고 답했다.

메모들

레퍼런스

• 토마스 H. 코먼, 찰스 E. 리저슨, 로널드 L. 리베스트, 클리포드 스타인.알고리즘 소개, 제2판MIT Press and McGraw-Hill, 2001.ISBN 0-262-03293-7.문제 2-2, 페이지 40.
• 분기 예측 및 캐시가 있는 경우의 정렬
• Ellis Horowitz, Sartaj Sahni 및 Susan Anderson-Freed ISBN 81-7371-605-6에 의한 데이터 구조의 기초
• 오웬 아스트라찬입니다버블 정렬: 고고학적 알고리즘 분석
• Spasic PhD, Srdic MSc, Open Source, 1987년 컴퓨터 통합 제조[1]

외부 링크

Wikibook Algorithm 구현에는 다음 항목에 대한 페이지가 있습니다.

Wikimedia Commons에는 버블 정렬과 관련된 미디어가 있습니다.

Wikdiversity에는 버블 정렬에 대한 학습 리소스가 있습니다.

• Martin, David R. (2007). "Animated Sorting Algorithms: Bubble Sort". Archived from the original on 2015-03-03. – 그래픽 데모
• "Lafore's Bubble Sort". (Java 애플릿 애니메이션)
• OEIS 시퀀스 A008302(정렬 중에 k개의 쌍 스왑이 필요한 [n]의 순열 수에 대한 표(통계량))