[알고리즘] 정렬 관련 개념

1. 안정적 정렬

안정적인 정렬이란 동일한 값을 갖는 데이터가 여러개 있을 때 정렬전의 상대적위치가 정렬후에도 그대로 유지되는 정렬을 의미합니다.

 

예컨대 입력데이터가 아래와 같이 존재한다고 가정해 보겠습니다.

10,20,30,50,40,20,60

 

위에 정렬전 데이터에는 동일한 데이터인 20이 존재합니다. 앞의 20을 A 뒤의 20을 B라고 하겠습니다.

 

데이터를 정렬하면 아래의 두가지 케이스로 나뉠 수 있습니다.

10,20(A),20(B),30,40,50,60

 

10,20(B),20(A),30,40,50,60

 

위의 첫번째 케이스를 '안정적'이라고 하고 두번째 케이스를 '불안정적'이라고 합니다.

 

따라서 안정적인 정렬이란 첫번째 케이스처럼 정렬되는 것을 의미합니다.

 

2. 제자리 정렬

입력 배열이외의 별도로 필요한 저장공간이 상수개를 넘지않는 정렬을 의미합니다.

 

즉 입력크기 n이 증가함에도 불구하고 추가적인 저장공간은 증가하지 않습니다.