[정렬]정렬

정렬

정렬(sorting)
핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업

• 데이터를 정렬하면 검색을 더 쉽게 할 수 있다.
• 오름차순(ascending order) : 키 값이 작은 데이터를 앞에 놓는 정렬 방식
• 내림차순(descending order) : 키 값이 큰 데이터를 앞에 놓는 정렬 방식

 

▶︎ 정렬 알고리즘의 안정성

1. 안정된(stable) 알고리즘: 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것
2. 안정되지 않은(unstable) 알고리즘: 같은 값의 키를 가진 요소의 순서가 정렬 전후에 달라지는 것

 

▶︎ 내부 정렬과 외부 정렬

1. 내부 정렬 (internal sorting)

• 하나의 배열에서 작업할 수 있는 경우에 사용된다.
• 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용
• 교환 : 선택, 버블 퀵
• 삽입 : 삽입, 쉘
• 선택 : heap, tree
• 병합 :

2. 외부 정렬 (external sorting)

• 하나의 배열에서 작업할 수 없는 경우에 사용된다
• 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용
• 외부 정렬을 구현하려면 작업을 위한 파일 등이 필요하고 알고리즘도 복잡하다.

 

▶︎ 정렬 알고리즘의 핵심 요소 : 교환, 선택, 삽입

 

 

 

[자료출처:www.notion.so/b1afde9993c6462892ad9ec8fc176103]