STABLE SORT

Q. 정렬(sort) 에 대해 알아보자.

정렬 알고리즘이란,

" 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. "

(위키백과:정렬 알고리즘)

라고 나와 있습니다.

쉽게 풀어 얘기하면,

이름순으로 순서를 매긴다던가, 나이순으로 순서를 매기는,

이러한 일정한 조건에 의해서 순서를 매기는 일을 정렬이라고 합니다.

그렇다면, 왜 정렬을 하는 것일까 ??

바로 빨리 찾기(탐색) 위해서 입니다.

이름을 가나다순으로 순서를 매긴다면,

김씨는 가장 앞에서 부터 찾으면 되고,

이씨는 중간 부분에서 부터 찾으면 되고,

황씨는 가장 끝에서 부터 찾으면 됩니다.

위에 써있는대로 일정한 조건의 순서대로 정렬이 되어 있기 때문에,

쉽게 찾을수 있는 것입니다.

정렬 알고리즘은,

컴퓨터의 역사 초창기부터 지금까지도 진행중인 주제라고 합니다.

간단할것 같지만, 그것을 효율적으로 풀어내기가 어렵기 때문입니다.

(속도는 빠르게, 사용된 자원은 적게)

최초로 연구된 거품(버블) 정렬은 1956년에 분석되었고,

그로부터 지금까지 계속 정렬 알고리즘은 발명되고 있습니다.

(최근 : 2004년 라이브러리 정렬이 발표됨)

정렬은 특징에 따라 분류하는데,

안정 정렬(stable sort)과 불안정 정렬(unstable sort)로 구분합니다.

안정 정렬과 불안정 정렬의 차이는 중복되는 값이 있을 때

그 중복된 값의

순서가 바뀌지 않으면 안정 정렬(stable sort)

순서가 바뀌면 불안정 정렬(unstable sort)

로 구분 합니다.

 

좀더 이해를 돕자면, 아래 표에 중복값 3 이 빨강, 파랑 순으로 정렬되어 있는데,

정렬 후에도  빨강, 파랑 순으로 정렬되어 있느냐? 아니냐? 입니다.

빨강, 파랑의 순서가 바뀌지 않으면, 안정 정렬

빨강, 파랑의 순서가 바뀌면, 불안정 정렬

이렇게 구분 되는것입니다.

2, 5, 1, 3, 4, 3	1, 2, 3, 3, 4, 5	1, 2, 3, 3, 4, 5
초기값	안정 정렬 (순서 변화X)	불안정 정렬 (순서 변화O)

그럼 안정 정렬과 불안정 정렬에는 무엇이 있는지 알아보겠습니다.

자세한 사항은 차차 포스팅으로 이어 가겠습니다.

※ 안정 정렬(stable sort)

정렬	주소
삽입 정렬 (insertion sort)	http://blog.naver.com/kiho0530/150140003926
거품 정렬 (bubble sort)	http://blog.naver.com/kiho0530/150142854413
합병 정렬 (merge sort)
기수 정렬 (radix sort)

※ 불안정 정렬(unstable sort)

정렬	주소
선택 정렬 (selection sort)
셸 정렬 (shell sort)
힙 정렬 (heap sort)
퀵 정렬 (quick sort)

참고1 : 위키백과:정렬 알고리즘

참고2 : http://entireboy.egloos.com/3516993

출처 : http://blog.naver.com/kiho0530/150140002244