인내 정렬 및 가장 길게 증가하는 서브 시퀀스 찾기

Question

HERE으로 설명되는 가장 길게 증가하는 서브 시퀀스를 찾는 알고리즘을 이해할 수 있습니다. 그러나 그것은 또한 인내 정렬과 관련이 있습니다. 저자가 말한 것처럼

보너스 : 인내심 정렬 기법을 부분적으로 배웠습니다 : :)

다른 장소에서 인내심을 읽으려고 시도했지만 어떻게 증가하는 부분 시퀀스 솔루션과 관련이 있는지 알 수 없습니다. 저는 리버스 엔지니어링을 시도하고 정렬 순서를 정렬하는 방법을 알고 있습니다. 누군가가 이것에 대한 조언을 제시 할 수 있습니까? 또한 인내 정렬의 목적과 이점은 무엇입니까?

Here은 정보를 공유하지만 다른 방법으로는 스택 오버플로 관련 질문입니다. 인내 정렬을 사용하여 가장 길게 증가하는 서브 시퀀스를 얻는 방법입니다.

Answer 1

인내 정렬은 또 다른 O (n) n 정렬 알고리즘입니다 (실제로 구현에 따라 다름). 전에 솔리테어를 해본 적이 있다면, 비슷한 일종의 카드 일 것입니다. 알고리즘은 각 스택이 내림차순으로 정렬 된 스택 목록을 유지합니다 (끝에서 끝까지). 숫자는 점진적으로 삽입됩니다.

숫자 x를 삽입하려면 맨 위의 요소가 x보다 큰 스택을 찾아 x를 누릅니다. 그러한 스택이 없다면 끝에 새로운 것을 만들고 그 위에 x를 누릅니다. 우리가 숫자를 삽입하는 방식은 스택의 최상위 요소가 증가하는 순서로 정렬됨을 의미하므로 가장 길게 증가하는 하위 시퀀스의 길이는 끝에있는 더미의 개수입니다.

일단 모든 숫자가 삽입되고 더미가 준비되면, 우리는 반복적으로 최소 숫자를 찾아서 출력하기를 원할 것입니다. 스택의 최상위 요소가 다시 정렬되도록 숫자를 가져온 스택을 새 위치에 삽입해야합니다. 이것은 힙을 사용하여 스택을 저장할 수 있습니다.

최소 요소를 찾고 공상 데이터 구조를 사용하지 않고 간단히 검색하면 알고리즘은 O (n sqrt (n))를 취합니다.이 값은 작은 n에도 좋지 않습니다.

이렇게하면 숫자 목록을 정렬하고 LIS 길이를 제공합니다 (그리고 약간의 보강으로 LIS가 제공됩니다).