sort에서 stable sort에 관하여.

이런식으로 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬이 Stable Sort이다. 

그래서 merge sort를 직접 구현할때, 

else if(a[idx_A]<=b[idx_B]) c[i]=a[idx_A++]; 로 작성할때, 이때 <= 대신 <으로 작성하여도 정상적으로 답을 출력하지만, 

이때 =을 입력하느냐 안하느냐에 따라서 stable sort 로 구현하느냐 아니냐가 갈린다고 하였다. 

그래서 stable sort에 대해서 구분하게 되었고 여기서 내용이 나와서 정리해놓는다. 

이처럼 기존의 동일 원소의 순서를 변경하지 않는것이 stable sort이다. 

 

  Comments,     Trackbacks