정렬의 stability

안정정렬과 불안정정렬을 예시를 들어 정리해봤다.

 

정렬 전 데이터베이스

	이름	학년
1	가케니	3
2	다스탠	3
3	라카트먼	3
4	나버터스	2
5	마카일	1

이름을 오름차순으로 처음 정렬할때

어떤 정렬기법을 사용하든 결과는 똑같다.

 

첫번째 이름 기준 정렬 결과

	이름	학년
1	가케니	3
2	나버터스	2
3	다스탠	3
4	라카트먼	3
5	마카일	1

 

 

하지만 여기서 학년 기준 오름차순으로 한번 더 정렬한다면

사용한 정렬기법에 따라 결과가 바뀐다.

 

case 1. 불안정 정렬 ex )선택정렬, 퀵정렬

(아래는 첫번째 정렬결과에 추가로 학년기준 선택정렬을 한 것이다. 3학년들의 정렬 상태를 확인해보자 )

	이름	학년
1	마카일	1
2	나버터스	2
3	다스탠	3
4	라카트먼	3
5	가케니	3

학년은 잘 정렬이 됐으나 이름정렬을 다시해야하게 생겼다.

 

case 2. 안정 정렬 ex )삽입정렬, 병합정렬

(삽입,병합정렬을 사용하면 학년이 a>b인 경우에만 순서가 바뀐다. (오름차순의 경우)

달리말해서 a<=b 이면 순서가 바뀌지 않으므로 같은 학년의 경우 이름또한 정렬된 상태로 유지된다.

 ) 

	이름	학년
1	마카일	1
2	나버터스	2
3	가케니	3
4	다스텐	3
5	라카트먼	3

이름과 학년이 잘 정렬됐다.

 

사용할 정렬을 선택할때 stability도 고려하자!