스플레이소트

컴퓨터 과학에서 splaysort는 splay 트리 데이터 구조를 기반으로 한 적응형 비교 정렬 알고리즘이다.^[1]

알고리즘.

알고리즘의 단계는 다음과 같다.

1. 빈 재생 트리 초기화
2. 입력 순서의 각 데이터 항목에 대해 재생 트리에 삽입하십시오.
3. 순서대로 splay 트리를 트래버스하여 데이터의 정렬 순서 찾기

따라서 알고리즘은 각 삽입 속도를 높이기 위해 splay 트리를 사용하여 삽입 정렬 또는 트리 정렬의 형태로 보일 수 있다.

분석

splay 트리의 상각 분석에 기초하여, 데이터 항목이 n개인 입력에서 splaysort의 최악의 경우 실행 시간은 O(n log n)로, 퀵소트, 힙 정렬, 병합 정렬과 같은 효율적인 비적응 알고리즘에 대한 시간 범위와 일치한다.

대부분의 항목이 정렬된 순서에 따라 이전 항목과 가깝게 배치되거나 소수의 다른 항목만 정렬되지 않은 입력 시퀀스의 경우, splaysort가 O(n log n)보다 빠를 수 있어 적응형 정렬임을 알 수 있다.이를 계량화하려면 d를_x 입력의 위치수(x)로 하고, i를_x 입력의 x의 한쪽과 출력에서 x의 반대쪽에 나타나는 항목수(x를 포함하는 반전수)로 한다.그 다음, splay 트리에 대한 동적 손가락 정리로부터 splaysort의 총 시간이 제한되는 것을 따른다.

${\displaystyle \sum _{x}\log d_{x}}$

그리고 에 의해

${\displaystyle \sum _{}}$ ${\displaystyle \underset{}{x}}$ ${\displaystyle \log }$ ${\displaystyle {}_{}{x}_{}}$ ${\$^[2]

또한 스플레이소트는 입력 시퀀스의 엔트로피에 적응하는 것으로 보일 수 있다.^[3]

실험결과

모팻, 에디 앤 피터슨(1996)의 실험에서, 무작위 숫자 표에서 splaysort는 1.5~2의 인수로 퀵소트보다 느렸고, 작은 인자에 의해 병합되는 것보다 느렸다.더 큰 기록으로 구성된 데이터의 경우, 다시 랜덤 순서로, 퀵소트에 의해 수행되는 추가 데이터 이동량은 포인터 기반 알고리즘에 비해 현저하게 느려졌고, splaysort와 mergesort에 대한 시간은 서로 매우 가까웠다.그러나, 거의 미리 정렬된 입력 시퀀스(데이터의 연속적인 모노톤 반복 횟수, 반전 횟수, 정렬된 반복을 만들기 위해 제거해야 하는 항목 수 또는 입력을 분할할 수 있는 비연속적인 모노톤 반복 횟수로 측정)의 경우, 플레이소트는 유의미해졌다.다른 알고리즘보다 ^[1]더 효율적이야

Elmasry & Hammad(2005)는 splaysort를 퀵소트뿐만 아니라 입력의 총 반전 횟수에 적응하는 몇 가지 다른 알고리즘과 비교했다.그들은 퀵소트보다 빠른 적응 알고리즘을 만들기에 충분한 역전이 거의 없는 입력에서 splaysort가 가장 빠른 알고리즘이라는 것을 발견했다.^[4]

변형

Saikkonen & Soisalon-Soininen(2012년)은 입력에서 연속적인 모노톤 반복 횟수에 더 강하게 적응하도록 splaysort를 수정하고, 이 조치에 따라 거의 전재되는 입력에서 결과 알고리즘이 더 빠르다는 것을 보여주는 실험을 보고한다.^[5]

참조