퀵 정렬이 안정성이 없다고 알려져있습니다.
하지만 위 그림과 같이, 1. pivot과 같은 원소들을 따로 저장(sav, O(n)) 2. before-pivot, after-pivot를 따로 생성 3. before-pivot + sav + after-pivot을 연결
을 하게 되면 안정성이 유지되는 것이 아닌가 싶습니다.
이렇게 하면 안정성이 유지가 되지만(아마도) 1번에서 O(n)의 연산이 추가로 수행되어 퀵정렬의 이점이 사라지게 되긴 합니다.
이에 대해 어떻게 생각하시나요?
뭐지소트 씁시다
나무위키 보면 알겠지만 인덱스를 저장하면 O(n)의 메모리를 소모하여 Stable한 퀵소트를 구현할 수 있다고 써있음
윗댓 말대로 메모리 추가로 써서 안정성 가질수 있음