[algorithm] 주로 정렬 된 데이터에 가장 적합한 정렬 알고리즘은 무엇입니까? [닫은]
주로 정렬 된 데이터에 가장 적합한 정렬 알고리즘은 무엇입니까?
답변
애니메이션 GIF 를 보는 매우 과학적인 방법을 바탕으로 Insertion 및 Bubble 정렬이 좋은 후보라고 말합니다.
답변
몇 개의 항목 만 => 삽입 열
항목은 대부분 이미 정렬되어 있습니다 => INSERTION SORT
최악의 시나리오에 대한 우려 => HEAP SORT
좋은 평균 사례 결과에 관심이 있음 => QUICKSORT
조밀 한 우주에서 아이템을 추출 함 => 버킷 소트
가능한 적은 코드를 작성하고 싶음 => 삽입 SORT
답변
팀 소트
Timsort 는 ” 다양한 부분 정렬 배열 (lg (N!) 비교가 필요하지 않고 N-1만큼 적음)의 초자연적 성능 “을 갖춘 “적응 형의 안정적이고 자연스러운 병합 정렬 “입니다. 파이썬 내장sort()이 알고리즘을 한동안 사용해 왔으며 결과는 좋았습니다. 특히 실제 데이터 세트에서 발생하는 입력에서 부분적으로 정렬 된 하위 시퀀스를 감지하고 활용하도록 설계되었습니다. 실제로는 목록에서 항목을 바꾸는 것보다 비교가 훨씬 더 비싼 경우가 종종 있습니다. 일반적으로 포인터를 바꾸는 것만으로도 종종 팀 소트를 탁월한 선택으로 만듭니다. 그러나 비교가 항상 매우 저렴하다는 것을 알고 있다면 (예를 들어 32 비트 정수를 정렬하기 위해 장난감 프로그램 작성) 성능이 더 좋은 다른 알고리즘이 있습니다. timsort를 이용하는 가장 쉬운 방법은 물론 Python을 사용하는 것이지만 Python은 오픈 소스이므로 코드를 빌릴 수도 있습니다. 대안 적으로, 위의 설명은 자신의 구현을 작성하기에 충분한 세부 사항을 포함합니다.
답변
다음과 같은 동작으로 삽입 정렬 :
k슬롯의 각 요소 에 대해1..n먼저 여부를 확인하십시오el[k] >= el[k-1]. 그렇다면 다음 요소로 이동하십시오. (첫 번째 요소는 생략하십시오.)- 그렇지 않은 경우 요소에서 이진 검색
1..k-1을 사용하여 삽입 위치를 확인한 다음 요소를 스쿠 트하십시오. (경우에만이 작업을 수행 할 수있는k>T곳T, 작은 일부 임계 값이k이 과잉이다.)
이 방법은 비교 횟수를 최소화합니다.
답변
내성적 인 정렬을 시도하십시오. http://en.wikipedia.org/wiki/Introsort
그것은 퀵 정렬을 기반으로하지만, 퀵 정렬이 거의 정렬 된 목록에 대해 최악의 행동을 피합니다.
이 정렬 알고리즘은 빠른 정렬이 최악의 모드로 전환되는 경우를 감지하고 힙 정렬 또는 병합 정렬로 전환하는 경우입니다. 거의 정렬되지 않은 파티션은 기본이 아닌 일부 파티션 방법으로 감지되며 작은 파티션은 삽입 정렬을 사용하여 처리됩니다.
더 많은 코드와 복잡성으로 인해 모든 주요 정렬 알고리즘을 최대한 활용할 수 있습니다. 또한 데이터의 모양에 관계없이 최악의 상황이 발생하지 않도록 보장 할 수 있습니다.
C ++ 프로그래머라면 std :: sort 알고리즘을 확인하십시오. 내부적으로 이미 내성 정렬을 사용하고있을 수 있습니다.
답변
Splaysort 는 스플레이 트리를 기반으로하는 모호한 정렬 방법입니다 적응 이진 트리 유형 인 입니다. Splaysort는 부분적으로 정렬 된 데이터뿐만 아니라 부분적으로 역 분류 된 데이터 또는 실제로 어떤 종류의 기존 순서를 가진 데이터에도 적합합니다. 일반적인 경우에는 O (nlogn)이고 데이터가 어떤 방식으로 (정방향, 역방향, 오르간 파이프 등) 정렬 된 경우에는 O (n)입니다.
삽입 정렬에 비해 큰 장점은 데이터가 전혀 정렬되지 않은 경우 O (n ^ 2) 동작으로 되돌아 가지 않기 때문에 데이터를 사용하기 전에 데이터가 부분적으로 정렬되어 있는지 확실하게 알 필요는 없습니다 .
단점은 필요한 스플레이 트리 구조의 추가 공간 오버 헤드와 스플레이 트리를 구축하고 파괴하는 데 필요한 시간입니다. 그러나 데이터 크기와 예상되는 사전 정렬 된 양에 따라 오버 헤드가 속도를 높이는 데 가치가있을 수 있습니다.
splaysort에 용지가 연습 및 경험 – 소프트웨어에 출판되었다.
답변
삽입 또는 쉘 정렬!
