알고리즘 3강 (정렬)

학습개요

1. 이번 강의부터 앞으로 3번의 강의에 걸쳐서 다양한 정렬 알고리즘에 대해서 학습한다. 이번 시간은 정렬의 첫 번째 강의로서 정렬의 기본 개념과 관련 용어를 우선 살펴보고, 정렬할 데이터의 개수가 작을 때 간단히 사용될 수 있는 기초적인 성능의 비교 기반의 내부 정렬 알고리즘으로서 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬에 대해서 살펴본다.

 학습목표

1. 정렬과 관련된 기본적인 개념과 용어들을 이해할 수 있다.
2. 기초적인 성능의 내부 정렬 알고리즘으로서, 선택 정렬, 버블 정렬, 삽입 정렬 및 셸 정렬의 원리와 수행 과정을 이해할 수 있다.
3. 기초적인 정렬 알고리즘의 성능을 분석하고 장단점을 이해할 수 있다.

 주요용어

1. 내부 정렬(internal sort)
   - 정렬할 모든 데이터를 주기억장치에 저장한 후 정렬하는 방식
2. 안정적 정렬(stable sort)
   -같은 값을 갖는 여러 개의 데이터에 대한 정렬 전의 상대적 순서가 정렬 후에도 그대로 유지되는 정렬
3. 제자리 정렬(in-place sort)
   -입력 배열 이외에 별도로 필요한 저장 공간이 상수 개를 넘지 않는 정렬
4. 비교 기반 정렬(comparison-based sort)
   - 두 데이터의 값 전체를 직접적으로 비교하여 어떤 값이 큰지 또는 작은지를 결정하여 정렬하는 방식
   - 예: 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬, 퀵 정렬, 합병 정렬, 힙 정렬
5. 선택 정렬(selection sort)
   -주어진 배열에서 가장 작은 값부터 차례대로 선택해서 나열하는 방식의 정렬 알고리즘
6. 버블 정렬(bubble sort)
   -왼쪽(또는 오른쪽)에서부터 모든 인접한 두 데이터를 차례대로 비교해서 왼쪽 데이터가 더 큰 경우에는 오른쪽 데이터와 자리를 바꾸는 과정을 반복해서 정렬하는 방식의 알고리즘
7. 삽입 정렬(insertion sort)
   -주어진 데이터를 하나씩 뽑은 후, 이미 나열된 데이터가 항상 정렬된 상태를 유지하도록 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방식의 정렬 알고리즘
8. 셸 정렬(shell sort)
   -삽입 정렬의 단점을 보완하기 위해 처음에는 멀리 떨어진 두 데이터를 비교․교환하고, 점차 가까운 위치의 데이터를 비교․교환한 뒤, 맨 마지막에는 인접한 두 데이터를 비교․교환하는 방식의 정렬 알고리즘

정리하기

1. 1. 기본 개념
   ⦁ 내부 정렬 → 정렬할 전체 데이터를 주기억장치에 저장한 후 정렬하는 방식
   ⦁ 비교 기반 정렬 vs 데이터 분포 기반 정렬
   - 비교 기반 정렬 → 두 데이터의 값 전체를 직접적으로 비교하여 어떤 값이 큰지 또는 작은지를 결정하여 정렬하는 방식 → 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬, 합병 정렬, 퀵 정렬, 힙 정렬
   - 데이터 분포 기반 정렬 → 데이터의 분포 정보를 활용하여 정렬을 수행하는 방식 → 계수 정렬, 기수 정렬, 버킷 정렬
   ⦁ 안정적 정렬 → 같은 값을 갖는 데이터에 대한 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식
   ⦁ 제자리 정렬 → 입력 데이터를 저장하는 공간 이외에 추가적인 저장 공간을 상수 개만 사용하는 정렬 방식
2. 2. 선택 정렬
   ⦁ 입력 배열에서 가장 작은 값부터 순서대로 선택해서 나열하는 방식 → 미정렬 부분에서 최솟값을 찾은 후, 이 최솟값과 미정렬 부분의 첫 번째 데이터와 위치를 교환하는 과정을 반복
   ⦁ O(n2), 불안정적, 제자리
   ⦁ 입력 데이터의 순서에 민감하지 않음 → 언제나 동일한 시간 복잡도를 가짐
3. 3. 버블 정렬
   ⦁ 왼쪽(또는 오른쪽)에서부터 모든 인접한 두 값을 비교하여 왼쪽의 데이터가 더 큰 경우에는 오른쪽 데이터와 자리를 바꾸는 과정을 반복해서 정렬하는 방식
   ⦁ O(n2), 안정적, 제자리
   ⦁ 인접한 두 데이터의 비교 횟수와 처리 단계의 수를 줄이도록 개선 가능 → 개선된 알고리즘의 경우에는 입력 데이터의 상태에 따라 성능이 달라짐 → 데이터가 원하는 순서대로 이미 정렬되었을 때 O(n), 역순으로 정렬되었으면 O(n2)
   ⦁ 선택 정렬에 비해 데이터 교환이 많이 발생
4. 4. 삽입 정렬
   ⦁ 주어진 데이터를 하나씩 뽑은 후, 나열된 데이터들이 항상 정렬된 상태를 갖도록 바른 위치를 찾아 뽑은 데이터를 삽입해서 나열하는 방식
   ⦁ O(n2), 안정적, 제자리
   ⦁ 입력 데이터의 원래 순서에 민감 → 역순의 경우에는 O(n2), 제 순서대로 거의 정렬되었으면 O(n)
5. 5. 셸 정렬
   ⦁ 삽입 정렬의 단점 보완 → 데이터가 삽입될 위치에서 멀리 떨어져 있어도 한 번에 한 자리씩만 이동해서 제자리를 찾아가야 함
   ⦁ 처음에는 멀리 떨어진 두 원소를 비교/교환하고, 점차 가까운 위치의 원소를 비교/교환한 뒤, 맨 마지막에는 인접한 원소를 비교/교환하는 정렬 방식 → 개념적으로는 입력 배열을 부분배열로 나누어 삽입 정렬을 수행하는 과정을 부분배열의 크기와 개수를 줄여가면서 반복적으로 수행
   ⦁ O(n2), 불안정적, 제자리
   ⦁ 사용하는 순열에 따라 성능이 달라짐 → 각 순열값은 부분배열의 개수이며, 동시에 각 부분배열 내에서 이웃한 데이터 간의 거리를 의미