선택 정렬이 버블 정렬보다 빠른 이유는 무엇입니까?

제공 한 모든 복잡성은 사실이지만 제공됩니다. Big O 표기법 에서 모든 추가 값과 상수는 생략됩니다.

귀하의 질문에 답하려면 d는이 두 알고리즘에 대한 자세한 분석에 집중합니다. 이 분석은 손으로하거나 많은 책에서 찾을 수 있습니다. Knuth의 컴퓨터 프로그래밍 기술 의 결과를 사용하겠습니다.

평균 비교 횟수 :

• 버블 정렬 : $ \ frac {1} {2} (N ^ 2-N \ ln N-(\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• 삽입 정렬 : $ \ frac {1} {4} (N ^ 2-N) + N-H_N $
• 선택 정렬 : $ (N + 1) H_N-2N $

이제 이러한 함수를 플로팅하면 다음과 같은 결과를 얻을 수 있습니다.

보시다시피, 두 정렬 방법이 동일한 점근 적 임에도 불구하고 요소 수가 증가하면 버블 정렬이 훨씬 더 나빠집니다. 복잡성.

이 분석은 입력이 무작위라는 가정을 기반으로하며 항상 사실이 아닐 수도 있습니다. 그러나 정렬을 시작하기 전에 임의의 방법으로 입력 시퀀스를 변경하여 평균 사례를 얻을 수 있습니다.

구현에 따라 다르기 때문에 시간 복잡도 분석을 생략했지만 유사한 방법을 사용할 수 있습니다.

댓글

• "에 문제가 있습니다. 입력 시퀀스를 임의로 변경하여 평균 사례를 얻을 수 있습니다. ". 정렬하는 데 필요한 시간보다 더 빨리 수행 할 수있는 이유는 무엇입니까?
• $ N $가 시퀀스 길이 인 경우 $ N $ 시간이 걸리는 모든 숫자 시퀀스를 변경할 수 있습니다. ' 모든 비교 기반 정렬 알고리즘에는 최소한 $ \ mathcal O (N \ log N) $ 복잡성이 있어야하므로 $ N $를 추가하더라도 '의 복잡성은 크게 변경되지 않았습니다. ' 어쨌든 우리는 시간에 관한 것이 아니라 비교에 대해 이야기하고 있습니다. 시간 복잡성은 제가 답변에서 언급했듯이 구현 및 실행중인 시스템에 따라 달라집니다.
• 제가 졸린 것 같네요. 맞습니다. 시퀀스는 선형 시간으로 변경 될 수 있습니다. .
• $ H_N = \ Theta (log N) $ 이후 비교 범위가 선택 정렬에 맞습니까? ' 평균적으로 O (n log n) 비교를한다고 암시하는 것 같습니다.
• Gamma = 0.577216은 Euler-Mascheroni입니다. '의 상수. 관련 장은 " 프로그래밍 기술 " vol 3 섹션 5.2.2 페이지입니다. 109 and 129. 거품 정렬 케이스, 특히 O (sqrt (N)) 항을 정확히 어떻게 플로팅 했습니까? 그냥 무시 했습니까?

점근 비용 또는 $ \ mathcal O $-표기법, 인수가 무한한 경향이있는 함수의 제한 동작, 즉 성장률을 설명합니다.

함수 자체, 예 : 비교 및 / 또는 스왑의 수는 동일한 속도로 증가하는 경우 동일한 점근 비용을 가진 두 알고리즘에 대해 다를 수 있습니다.

더 구체적으로, 버블 정렬에는 평균 $ n / 4가 필요합니다. 항목 당 $ 스왑 (각 항목은 초기 위치에서 최종 위치로 요소별로 이동되고 각 스왑에는 두 항목이 포함됨) 반면 선택 정렬에는 $ 1 $ 만 필요합니다 (최소 / 최대 값을 찾으면 한 번만 스왑됩니다. 배열 끝까지).

비교 수 측면에서 버블 정렬에는 $ k \ times n $ 비교가 필요합니다. 여기서 $ k $는 항목의 초기 위치와 균등하게 분산 된 초기 값의 경우 일반적으로 $ n / 2 $보다 큰 최종 위치입니다. 그러나 선택 정렬에는 항상 $ (n-1) \ times (n-2) / 2 $ 비교가 필요합니다.

요약하면 점근 적 한계는 입력 크기와 관련하여 알고리즘 비용이 증가하는 방식에 대한 좋은 느낌을 제공하지만 동일한 세트 내에서 서로 다른 알고리즘의 상대적 성능에 대해서는 아무런 의미가 없습니다.

p>

댓글

• 아주 좋은 답변입니다
• 어떤 책을 선호하십니까?
• @GrijeshChauhan : 책은 취향의 문제이므로 권장 사항에 소금 한 알을 사용하십시오. 저는 개인적으로 Cormen, Leiserson 및 Rivest '의 " 알고리즘 소개 "를 좋아합니다. 다양한 주제와 Knuth '의 " 컴퓨터 프로그래밍 기술 시리즈는 특정 주제에 대해 더 많은 / 모든 세부 정보가 필요한 경우입니다. 책에 대한 질문이 이전에 여기에 있는지 확인하거나 ' t가없는 경우 해당 질문을 게시 할 수 있습니다.
• 당신의 대답은 실제 대답입니다. 다른 답변에 제공된 큰 입력에 대한 그래프가 아닙니다.

버블 정렬은 더 많은 스왑 시간을 사용합니다. 선택 정렬은 이것을 피합니다.

정렬 선택을 사용하면 최대 n 번 교체됩니다. 그러나 버블 정렬을 사용하면 거의 n*(n-1)를 바꿉니다. 그리고 분명히 읽는 시간은 메모리에서도 쓰는 시간보다 적습니다. 비교 시간 및 기타 실행 시간은 무시할 수 있습니다. 따라서 스왑 시간은 문제의 중요한 병목 현상입니다.

댓글

• Bartek의 다른 답변이 더 합리적이라고 생각하지만 투표 할 수는 없습니다. ' or comment … BTW 나는 여전히 쓰기 시간이 더 큰 영향을 미친다고 생각하며 그가 이것을보고 동의한다면 그가 이것을 고려할 수 있기를 바랍니다.
• 시간이있는 사용 사례가 있기 때문에 단순히 비교 횟수를 무시할 수 없습니다. 두 항목을 비교하는 데 소요되는 시간은 두 항목을 교환하는 데 소요되는 시간을 훨씬 초과 할 수 있습니다. 매우 긴 문자열 (각각 10 만자)의 연결 목록을 고려하십시오. 각 문자열을 읽는 것은 포인터 재 할당을하는 것보다 훨씬 더 오래 걸립니다.
• @IrvinLim 당신이 옳다고 생각하지만 마음을 바꾸기 전에 통계 데이터를 봐야 할 수도 있습니다.