삽입의 효율성 정렬 대 버블 정렬 대 선택 정렬?

Question

삽입 정렬이 버블 정렬보다 빠르며 모든 3의 실행 시간이 O (n^2) 인 선택 정렬보다 빠릅니다. 그러나 이들을 서로 비교하기 위해 무엇을 말할 수 있습니까?

Answer 1

은 다음과 같은 기준에 따라 정렬 알고리즘 비교할 수 있습니다

1. 시간 복잡성 (빅 - 오 표기법). 최상의 경우, 최악의 경우 및 평균 실행 시간은 서로 다른 시간 복잡성을 가질 수 있습니다. 예를 들어 Bubble Sort의 경우 가장 좋은 경우는 O (n)이며, 원래 목록이 대부분 순서대로 정렬되어있을 때 Selection Sort보다 빠릅니다 (많은 요소가 부재 함).
2. 메모리 복잡성. n이 커지면 목록을 정렬하는 데 얼마나 많은 메모리가 필요합니까?
3. 안정성. 정렬은 동등한 정렬 값을 갖는 요소의 상대적 순서를 보존합니까? 예를 들어 카탈로그 항목을 가격순으로 정렬하는 경우 일부 요소의 가격이 동일 할 수 있습니다. 카탈로그가 원래 항목 이름별로 알파벳 순으로 정렬 된 경우 선택한 정렬 알고리즘은 각 가격이 같은 그룹 내에서 사전 순 정렬을 유지합니까? 항목 수)
4. 최상/최악/애버리징 비교 수가 필요합니다. 비교 연산이 비싼 경우 중요합니다. (예 : 효율성이 일부 시뮬레이션 또는 복잡한 계산을 통해 계산되는 대체 설계의 효율성 비교).
5. 최고/최악/평균 필요한 스왑 작업 수. 스왑 작업이 많은 경우 중요합니다. (예 : 선박 갑판에서 물리적으로 이동해야하는 선적 컨테이너 정렬)
6. 코드 크기. 버블 정렬은 작은 코드 풋 프린트로 알려져 있습니다.

Answer 2

삽입/선택/버블 정렬이 모두 n^2 시간에 실행되는 것을 보는 방법은 여러 가지가 있습니다.

• 그들은 중첩 루프를 사용 : 외부 루프 N, 그리고에서 N/2 내부 - 루프 각각 평균 ​​
• 들은 모든 요소 쌍 비교 : * (N-1)/2 쌍
N 개의 존재를

다음은 실행중인 insertion/selection/bubble sort에 대한 몇 가지 상세 분석입니다.