알고리즘 - 5 정렬 알고리즘의 개요 및 선택 정렬과 버블 정렬

정렬 알고리즘

1. 정렬이란?

2. 정렬의 에

3. 정렬 방식 구분

 

정렬

- 알고리즘에서 설계와 분석, 생각하는 방법 등을 훈련하기 위한 적합한 주제

- 알고리즘 분야에서 사용하는 여러 기술부분들이 상당 부분 정렬에 포함되 있어, 정렬을 잘 이해하면 알고리즘 과정에서 다른 주제를 이해하는데 큰 도움 될 것!

 

정렬의 정의

- 순서 없이 배열된 자료를 오름차순이나 내림차순으로 나열한 것

- 컴퓨터 공학을 포함한 모든 과학기술분야에서 가장 기본적이고 중요한 알고리즘 중 하나

- 자료 탐색에 있어서 필수 적임 : 만약 영어 사전에서 단어들이 알파벳 순으로 정렬되어 있지 않다면?

 

 

정렬의 대상

- 일반적으로 정렬시켜야 할 대상 = 레코드

- 레코드는 보다 작은 단위인 필드로 구성

- 키 필드로 레코드 식별

 

 

 

 

정렬 방식 구분

- 정렬은 실행 방법과 정렬 장소를 기준으로 아래 표와 같이 구분할 수 있음

기준	정렬 방식	설명
실행 방법	비교식 정렬	비교할 키 값을 한 번에 두 개씩 비교하고, 교환하여 정렬하는 방식
	분배식 정렬	키값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식(divide and conquer)
정렬 장소	내부 정렬	컴퓨터의 주기억 장치에서 정렬  - 입력의 크기가 주기억장치의 공간보다 크지 않은 경우 수행
	외부 정렬	주기억 장치 뿐만아니라 보조기억장치도 이용하여 정렬 - 입력의 크기가 주기억장치의 공간보다 큰 경우에 수행 - 보조 기억 장치에서 입력을 여러번 나누어 주기억장치로 읽어 들인 후 정렬하여 보조기억장치에서 다시 저장
안정성	안정 정렬	동일한 값에 대해 기존의 순서가 유지되는 정렬 방식
	불안정 정렬	ㄷㅇ