정렬(Sorting)-선택정렬, 버블정렬, 삽입정렬, 병합정렬

1. 선택 정렬(Selection Sort)

매 단계에서 '아직 처리되지 않은 가장 작은 원소를 선택'해서 앞으로 보내는 정렬 방법

• 앞으로 보내진 원소는 더 이상 위치가 변경되지 않음
• 선형 탐색: 매 단계에서 가장 작은 것 선택하는데 약 N번의 연산 필요
• 시간 복잡도: O(N²) → 비효율적

[동작방식]

1. 각 단계에서 가장 작은 원소를 선택

2. 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치 교체

선택정렬 예시

 

 

2. 버블 정렬(Bubble Sort)

버블: 서로 인접한 두 원소를 비교하는 형태가 거품과 같다고해서 붙여진 이름이다.

 

인접한 두 원소를 확인해서 정렬이 안되어 있다면 위치를 서로 변경

→ 각 단계를 거칠 때마다 가장 큰 값을 하나씩 확실하게 결정함!(즉, 오른쪽부터 차례대로 정렬됨)

[동작 방식]

1. 첫 번째 인덱스 원소와 두 번째 인덱스 원소 비교

2. 두 번째 인덱스 원소와 세 번째 인덱스 원소 비교

...

→ 한 번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동한다.(그 다음 단계에서는 맨 뒤로 이동한 데이터는 정렬에서 제외함)

버블정렬 예시

 

 

3. 삽입 정렬(Insertion Sort)

각 숫자를 적절한 위치에 삽입하는 정렬 기법

• 시간복잡도
  • 최선의 경우: O(N)
  • 최악의 경우: O(N²) → 비효율적
• 이미 정렬되어 있는 경우는 빠르게 수행 가능(선택, 버블과 달리 속도가 빠름)

[동작 방식]

1. 각 단계에서 현재 원소가 삽입될 위치를 찾음

2. 적절한 위치에 도달할 때까지 반복적으로 왼쪽으로 이동

﹡삽입 정렬 처음에 첫 번째 원소를 정렬이 되어있다고 가정

삽입 정렬 예시

 

 

4. 병합(=합병) 정렬

전형적인 분할정복(divide and conquer) 알고리즘 중 하나

• 빠른 정렬 알고리즘 중 하나
  • 분할(divide): 큰 문제를 작은 부분 문제(쉬운 문제)로 분할
  • 정복(conquer): 작은 부분 문제를 각각 해결
  • 조합(combine): 해결한 부분 문제의 답을 이용해서 다시 큰 문제를 해결
• 큰 문제 쪼개기 → 작은 문제 각각 해결 → 다시 합쳐 큰 문제 해결
• 재귀함수 이용해서 구현(더 이상 쪼갤 수 없는 크기가 될 때까지 계속해서 분할)
  → 이럴 경우 오버 헤드(overhead)로 이어져 메모리 소모가 큼
• 시간 복잡도: O(NlogN)
• 직관적으로 생각했을 때, 높이가 O(logN)이고, 너비가 O(N)인 정사각형과 유사
• 장점: 최악의 경우에도 O(NlogN)을 보장할 수 있음
• 단점: 일반적인 경우, 정복 과정에서 임시 배열 필요

[동작 방식]

병합정렬 예시

1. 분할: 정렬할 배열(큰 문제)을 같은 크기의 부분 배열(작은 문제)2개로 분할 → 단순히 배열의 크기를 절반으로 쪼개는 것

2. 정복: 부분 배열을 정렬 → 작은 문제 해결(두 개의 부분 배열을 '정렬된 하나의 배열'로 만든다)

정복 아이디어
- 각 부분 배열은 이미 정렬된 상태로 봄
- 각 부분 배열에 대해 첫번째 원소부터 시작해서 하나씩 확인
- 총 원소의 개수가 N개일 때, O(N)의 시간 복잡도가 요구됨

 

3. 조합: 정렬된 부분 배열을 하나의 배열로 다시 병합