[알고리즘] 2장_1

📌 정렬

: 여러 개의 원소를 순서대로 재배치하는 것

✅ 내부 정렬

: 모든 원소의 리스트가 주기억장치에 있는 경우의 정렬

비교 기반 정렬 알고리즘

• 선택 정렬
• 버블 정렬
• 삽입 정렬
• 쉘 정렬

✅ 외부 정렬

: 대부분의 자료가 외부 기억장치에 존재하는 경우

✅ 용어 정리

• 레코드: 일반적으로 여러 가지 정보(각각 필드)를 포함

• 키: 레코드를 대표하는 것, 레코드 간의 순서를 나타내는 자료(ex. 학번, 이름)

⭐ 안정적 정렬

: 동일한 키를 갖는 레코드쌍의 상대적인 위치가 정렬 후에도 그대로 유지되는 것

ex. 20 25 30 20 40 15
    15 20 20 25 30 40

✅ 제자리 정렬

: 입력 배열 이외의 별도 메모리에 저장되는 원소의 개수가 상수개를 넘지 않는 정렬 알고리즘

✅ 분할 정복 알고리즘

: 문제를 작은 2개의 문제로 분리하고 각각을 해결함 ➡ 결과를 모아서 원래의 문제를 해결하는 전략임

• 평균적으로 매우 빠른 정렬 속도를 자랑함
• 퀵 정렬