알고리즘 - 정렬 1.0 기본 개념

정렬의 정의

: 주어진 데이터를 값의 크기 순서(기준)에 따라 재배치 하는 것.

오름차순과 내림차순으로 정렬 할 수 있음

 

정렬은 두가지로 구분할 수 있는데 정렬 수행 시점에 데이터가 어디에 저장되어 있는가에 따라 내부 정렬과 외부 정렬로 나뉜다.

 

내부 정렬 

- 전체 데이터를 주 기억장치에 저장한 후 정렬을 수행하는 방식

 

외부 정렬

- 모든 데이터를 주기억장치에 젖아할 수 없는 경우. 모든 데이터를 보조기억장치에 저장해두고 그중 일부 데이터만을 반복적으로 주기억장치로 옮겨 정렬을 수행하는 방식

 

내부 정렬의 방식으론 비교 기반 알고리즘과 데이터 분포 기반 알고리즘으로 나뉜다.

 

비교 기반 알고리즘의 종류로는

-선택 정렬 
-버블 정렬
-삽입 정렬
-셸 정렬
-퀵 정렬
-합병 정렬
-힙 정렬

 

안정적 정렬이란

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

제자리 정렬이란

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

 

데이터 분포 기반 알고리즘으로는

- 계수 정렬

- 기수 정렬

- 버킷 정렬

등이 있다.