무슨 버블이 좋을까요?

Question

가능한 중복 :
What is a bubble sort good for?

I'am 확인 모든 알고리즘은 장점과 단점이있다, 그래서 어떻게 다른 정렬 알고리즘에 비해 buble 종류는? (당연히 나는 대답이 "배우기 쉽지 않은"것이기를 바란다)

Answer 1

1. 당신은 항상 인접 노드를 교체하기 때문에 연결리스트에 대한 구현이 용이 왼쪽에서 오른쪽으로 반복적으로 이동합니다.
2. 버블 정렬은 안정적인 정렬입니다.

Answer 2

퍼포먼스 와이즈, 버블 정렬이 좋지 않다 (O (n^2)). 여기의 장점 중 일부는 다음과 같습니다

• 버블 정렬이 제대로 쓰기 매우 쉽게 (당신은 다음 그냥 버블 정렬을 사용하는 것이 더 쉬울 수 있습니다 신속하고 더러운 일을하는 경우). (이 배열 병합 정렬과는 달리, 인플레 이스 (in-place) 종류이기 때문에)

• 메모리 소비가 매우 낮다

Answer 3

사실 아주 작은 목록 이외의 용도로 사용하지 않습니다. 충분히 작은 목록을 위해 낮은 오버 헤드로 인해 더 멋진 유형으로 우위를 점할 수 있습니다. 나는 십여 개가 넘는 아이템을 위해 그것을 사용하지 않을 것입니다.

Answer 4

완전히 엉망으로 끝나지 않고 학교에서 게임을하기에 충분히 간단합니다. "왼쪽 이웃이 너보다 키가 큰 경우 장소를 전환하십시오."

Answer 5

프로그램하기가 더 쉽습니다. 노련한 프로그래머조차도 빠른 정렬, 힙 정렬 및 잘못된 정렬 병합을 수행합니다. 또한 스택 공간에서 O (n)에 여분의 로그 (n)을 소비하지 않습니다. 재귀 적으로 힙 정렬을 구현할 수 있지만.

기본적 알고리즘이

O (N^2) 최악의 성능을하다

기본적이 느리다 ....

• 삽입 O (N^2) 그러나 이미 정렬 된 목록에서 O (n)을 수행합니다.
• 버블 정렬 : 유사하지만 항상 이것을 허용하기 위해 초기 종료와 비슷하게 프로그래밍되지는 않습니다.일반적으로이 일을 토론하고 인터뷰에
• 선택 정렬을 던져 더 많은 인기를 한 것 같다 :이 항상 O를 필요하므로 일반적으로 더 일찍 출구가없는 (N^2)

O (N * LG 전자 (n)은)

일반적으로이 실제로 입증 된 당신이 입력에 대해 아무것도 몰라 일반적인 분류에 대한 가장 빠른 정렬 알고리즘() 입력에 대해 아무것도 모른 채 하한 정렬에있을 :

• 빠른 정렬 : 일반적으로 고속 알고리즘보다 빠르지 만 피벗을 잘못 선택하면 O (n^2)로 축소 될 수 있으며 스택을 소비하기 때문에 Bubble/Insertion/Selection을 말하는 것보다 나 빠지게됩니다. 공간. 캐시 지역성을보다 잘 활용하므로 일반적으로 다른 대안보다 성능이 우수합니다. 얼마나 잘 선회 하는가에 따라 호출을위한 공간은 LG (n) 공간에서 O (n) 공간까지 필요합니다.
• 병합 정렬 : O (n * log (n)) 성능이지만 O (n) 개의 추가 공간이 필요합니다. 일반적으로 빠른 정렬만큼 빠릅니다. 일반적으로 호출을위한 lg (n) 여분의 공간이 필요합니다 ...
  힙 정렬 : 추가 공간이 필요하지 않고 재귀 적으로 구현 될 수 있지만 배열 주위로 정렬되어 다른 것과 마찬가지로 캐시에서 좋지 않습니다. . 재귀 적으로 구현되는 경우 호출에 대해 lg (n) 여분의 공간이 필요합니다.

O는 당신이 당신의 입력에 대해 뭔가를 알고있는 경우 (n)은
를 정렬하면 O보다 더 자주 종류의 더 나은 수 (N * LG 전자 (N)). 기본적으로 기수 정렬, 버킷 정렬, 정렬 계산 등을 찾습니다. 많은 체계가 있습니다. 일반적으로 이들 중 하나를 사용하여 정렬 할 수 있다면 ...

** 기타 분류 : ** 다른 많은 종류가 있습니다. 셸 정렬 같은 것들은 위의 것들이 더 일반적입니다.

하지만 실제로는 더 빠른 알고리즘을 구현하는 것이 더 어렵습니다. 누군가 20 분 안에 도서관없이이 번호를 정렬하라고 말하면, 나는 선택 정렬을 쓸 것입니다. 더 복잡한 것들은 잘못되기 쉽습니다. 그리고 종종 추가적인 공간이 필요합니다. 복잡성, 공간 및 시간의 상충 관계를 평가해야합니다. 많은 프로그래밍 언어가 라이브러리 정렬에 내장되어 있습니다.

또 하나주의해야 할 것은 정렬이 안정적인지 아닌지입니다. 기본적으로 A, C, D, C, G, C가있는 경우 각각의 C가 순서대로 나타나거나 마지막 C가 다른 C의 앞에 나타납니다. 여러 필드를 정렬하는 경우이 작업이 중요합니다. 예를 들어 이름과 성으로 정렬하면 (Alex Rodriguez, Jane Rodriguez, Betty Rodriguez) ... 알렉스 R, 베티 R, 제인 R (R). 두 번째 정렬은 안정적이라면 Alex R, Betty R, Jane R을 얻을 수 있습니다. 안정적이지 않으면 순서를 얻을 수 있습니다. 일반적으로 버블 및 삽입은 안정적으로 구현하기 쉽습니다. 힙 정렬 및 빠른 정렬은 일반적으로 안정적이지 않습니다. 병합 정렬은 안정적으로 구현하기 쉽습니다. 이것은 선택의 요인이기도합니다 ....

또한 O (n) 표기법을 모르면 기본적으로 얼마나 많은 계산이 필요한지에 대한 상한입니다. O (n * 2)를 사용하여 약 400 개의 작업을보고있는 20 개의 항목을 정렬하려면 O * (n * lg (n))을 사용하여 약 20 개의 작업을보고 약 86 개의 작업을 수행합니다. 그리고 lg (n)은 약 4.3을보고 있습니다. 어쨌든 숫자가 클수록이 차이가 커집니다. 10000 개 항목은 n * lg (n)의 경우 133000 회 연산이고 n^2의 경우 100000000 회입니다. 느린 정렬을 사용하는 큰 목록의 경우 실용적이지 않습니다. 그리고 물론 O (n)은 단지 10,000입니다. 운영 횟수는 정확히 그 숫자가 아니지만 성장 속도에 대해 말합니다. 즉 lg (n)를 사용하면 4.3에서 20에서 133000으로 증가합니다.n을 사용하면 20에서 10000으로 성장하고 n은 86에서 133000으로, n^2는 400에서 100000000으로 커집니다. 기본적으로 목록이 커질수록 느린 항목은 수행 할 수없는 지점에 도달하게됩니다 그 (것)들 그러나 더 빠른 그들은 할 수있다. 구현하고 바로 얻을 수

1. 쉬운 :
   어쨌든 나는 버블 정렬에 다음과 같은 장점을 볼 맥락에서 모든 것을 넣어 데.
2. 는이 메모리 캐시
에 좋은 있도록
3. 그것은 배열을 순차적으로 읽어 낮은 메모리 환경을위한 정말 좋은 (재귀를 구현하지 않는 가정) 배열 또는 프로 시저 호출을 위해 여분의 공간을 사용하지 않습니다
4. 다른 사람이
5. 이 안정
6. 일부 면접관은 의심의 여지 라이브러리 빠른 정렬에

어쨌든 어느 시점에서이 문제를 언급하지 않습니다 쉽게 만들 수 있으며이 연결리스트를 정렬이 사용하기 쉬운 언급 찌르다 르 병합 정렬이 가장 인기있는 것 같습니다.

Answer 6

버블 정렬은 세 항목의 목록을 정렬하는 가장 빠른 방법입니다. 거의 예외는 아니지만 모든 종류가 버블 정렬 형태로 3 가지로 변합니다.

Answer 7

거품 정렬이 에 이것은 QuickSort보다 더 빠른 (그리고 거의 모든 다른 종류)는 이미 분류 목록 ;-)

QuickSort의 성능은 O입니다 최선의 경우 (N 로그 N), BubbleSort ' s는 O (N)입니다!

이 이국적인 것 외에도 Donald Knuth와 동의해야합니다. The Art of Computer Programming, Vol. 3 : 정렬 및 검색 : 한마디로

, 버블 정렬은 인기를 얻기 쉬운 이름을 제외한 추천하는 것은, 그것이 몇 가지 흥미로운 이론적 인 문제에 이르게한다는 사실이없는 것으로 보인다