[Sort] 정렬 알고리즘 : #1 정렬

 

정렬 ?

정렬이란

순서 없이 나열된 자료들을 

조건/기준을 가지고 일정한 순서가 되도록 재배열하는 것을 의미한다.

 

우리가 자료를 찾을 때 정렬이 되지 않은 상태에서는

탐색 자체가 어려울 뿐만 아니라 효율이 매우 떨어지게 된다.

그렇기 때문에 자료가 커질수록 반드시 효율적인 알고리즘의 사용이 필요하다!

정렬 알고리즘의 종류에 대해 알아보기 전에 용어와 고려사항에 대해 먼저 알아보자.

레코드(Record) ? 키 (Key) ?

 

레코드(record) 란,

리스트의 각 원소를 의미하며 필드로 구성된 정렬의 대상이다.

키(Key) 란,

레코드의 한 서브 필드로 정렬의 기준이 된다.

 

+)

예를 들어,

교실의 학생들을 일정한 순서로 정렬시키려고 하는 경우

이름이라는 필드를 키 값으로 정렬할 수 도 있고,

생년월일이라는 필드를 키 값으로 정렬할 수 도 있고,

혹은 신장이라는 필드를 키 값으로도 정렬할 수 있다.

(레코드의 필드를 정렬의 기준(Key)으로 사용!)

 

 

정렬 선택 시 고려사항

 

효율적인 정렬 알고리즘을 선택하기 위해서 고려해야할 몇가지가 있다.

미리 알아두자!

• 데이터의 양 (== 레코드의 크기)
• 초기 데이터의 배열 상태
• 키 값들의 분포 상태
• 소요 공간 및 작업 시간
• 사용 컴퓨터 시스템의 특성

 

#1

내부정렬과 외부정렬

 

정렬 알고리즘은 정렬해야하는 데이터의 양에 따라

'내부 정렬'이나 '외부 정렬'을 선택할 수 있다.

두 정렬은 정렬이 수행되는 장소에 따라 구분한다.

 

 

내부 정렬 (Internal Sort)  :  적은 자료 빠른 정렬 / 대용량 데이터 정렬 불가

 

내부 정렬은 데이터의 양이 적을 경우 사용할 수 있는 방식으로

정렬할 자료를 내부 메인 메모리(RAM)에 올려 정렬한다.

 

데이터 접근 속도가 빠르기 때문에 빠른 정렬을 할 수 있지만

메모리의 용량이 적기 때문에 정렬이 제한된다.

따라서 대용량 데이터는 정렬할 수 없다.

 

 

외부 정렬 (External Sort)  :  대용량 데이터 정렬  / 느린 정렬

 

외부 정렬은 메인 메모리에 올리기에는 데이터 양이 많을 경우 사용해야 하는 방식으로

정렬할 자료를 나누어 외부 보조기억장치(HDD)에 저장해 두고,

부분적으로 메인 메모리에 저장해 처리한 뒤 합쳐서 다시 정렬하는 방식으로 정렬한다.

 

내부 정렬에 비해 상대적으로 속도가 느리지만

대용량의 데이터를 정렬할 수 있다.

 

 

내부 정렬 방식

 

내부 정렬은 삽입 / 교환 / 선택 / 분배 / 병합의 방식을 통해 정렬한다.

다음 포스팅에서 삽입 방식의 내부 정렬 알고리즘에 대해 알아보자.

 

 

---

정렬 알고리즘 간에 비교를 시각적으로 잘 보여주는 사이트! 🤔

 

Sorting Algorithms Animations

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

 

⚠️ 아래 내용은 모두 개인적인 참고 / 기록을 위한 용도입니다. 참고해주시고 편안하게 봐주세요 :)  ⚠️

***    혹시라도 잘못된 정보가 있다면  언제든지 알려주시면 감사하겠습니다  !    ***