정렬(선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬, 병합 정렬, Tim sort)

1. 선택 정렬(Selection Sort)

정의

• 각 단계에서 남은 부분 중 가장 작은 원소를 선택해, 해당 위치에 배치하는 정렬 알고리즘
• 제자리 정렬(In-place Sort)로 추가 메모리 공간을 거의 사용하지 않고, 배열 내에서 정렬함
• 안정 정렬이 아니기 때문에 동일한 값의 순서가 변경될 수 있음

 

 

시간 복잡도

• 최악/최선/평균: $O(N²)$

 

 

정렬 단계

1. 가장 작은(또는 큰) 원소 선택
   • 배열에서 아직 정렬되지 않은 부분 중에서 가장 작은(또는 큰) 원소를 찾음
2. 가장 앞의 원소와 교환
   • 찾은 원소를 현재 정렬되지 않은 부분의 첫 번째 원소와 교환함
3. 다음 위치로 이동
   • 다음 위치로 이동하여 1~2단계를 반복
4. 전체 배열이 정렬될 때까지 반복
   • 배열이 모두 정렬될 때까지 위 과정을 반복

 

 

장점 및 단점

장점

• 알고리즘이 직관적이고 구현이 쉬움
• 한 번에 한 번씩만 교환하므로 다른 $O(N²)$ 알고리즘보다 교환 횟수가 적음

 

단점

• $O(N²)$로, 데이터 양이 많을수록 비효율적
• 정열의 상태와 상관없이 항상 같은 시간 복잡도를 가짐

 

 

 

2. 삽입 정렬

정의

• 모든 원소를 차례대로 앞쪽의 정렬된 부분에서 알맞은 위치에 삽입하는 알고리즘
• 제자리 정렬(In-place Sort)로 추가 메모리 공간을 거의 사용하지 않고, 배열 내에서 정렬함
• 안정 정렬(Stable Sort)로 동일한 값의 원소들 간의 순서를 유지
• 새로운 데이터를 즉시 처리하여 정렬 가능한 온라인 알고리즘이다

 

 

시간 복잡도

• 최악/평균: $O(N²)$ (거의 역순일 때)
• 최선: $O(N)$ (이미 정렬된 경우)

 

 

정렬 단계

1. 첫 번째 원소는 이미 정렬된 것으로 간주
   • 두 번째 원소부터 비교를 시작
2. 현재 원소를 앞의 정렬된 부분과 비교
   • 두 번째 원소부터 시작하여, 앞에 있는 이미 정렬된 원소들과 비교
3. 비교하며 위치 찾기
   • 현재 원소가 앞의 정렬된 원소들보다 작으면, 해당 원소가 더 작은 위치로 한 칸씩 이동함
4. 올바른 위치에 삽입
   • 현재 원소보다 작은 값을 만날 때까지 비교한 후, 그 자리에 현재 원소를 삽입함
5. 다음 원소로 이동
   • 그다음 원소로 이동하여 같은 과정을 반복
6. 전체 배열이 정렬될 때까지 반복
   • 배열의 마지막 원소까지 위 단계를 계속 진행함

 

 

장점 및 단점

장점

• 알고리즘 구조가 이해하기 쉽고 직관적
• 거의 정렬된 데이터에서 효율적이며 최선의 경우 $O(N)$의 성능을 발휘
• 데이터가 적을 때 성능이 좋음

 

단점

• $O(N²)$로, 데이터 양이 많을수록 비효율적

 

 

 

3. 버블 정렬

정의

• 인접한 두 원소를 비교하고 교환하는 것을 반복하여 정렬하는 알고리즘
• 제자리 정렬(In-place Sort)로 추가 메모리 공간을 거의 사용하지 않고, 배열 내에서 정렬함
• 안정 정렬(Stable Sort)로 동일한 값의 원소들 간의 순서를 유지

 

 

시간 복잡도

• 최악/평균: $O(N²)$ (모든 원소를 비교하고 교환)
• 최선: $O(N)$ (배열이 이미 정렬된 경우)

 

 

정렬 단계

1. 첫 번째 원소부터 시작
   • 배열의 첫 번째 원소와 두 번째 원소를 비교
2. 인접한 원소끼리 비교 후 교환
   • 두 원소를 비교하여 앞 원소가 더 크면 교환 (오름차순 기준)
3. 다음 인접한 원소로 이동
   • 첫 번째 비교가 끝나면 다음 두 인접한 원소로 이동하여 다시 비교하고 필요 시 교환
4. 가장 큰 원소가 끝에 위치
   • 배열 끝까지 비교가 끝나면 가장 큰 원소가 배열의 마지막 위치에 놓임
5. 위 과정 반복
   • 다음 반복에서 배열의 끝에서 두 번째까지 비교를 진행하며, 남은 원소들을 계속 비교하고 교환함
6. 배열이 정렬될 때까지 반복
   • 위 과정을 배열이 정렬될 때까지 반복

 

 

장점 및 단점

장점

• 알고리즘이 직관적이고 구현이 쉬움
• 거의 정렬된 데이터에서 효율적
• 데이터가 적을 때 성능이 좋음

 

단점

• $O(N²)$로, 데이터 양이 많을수록 비효율적
• 필요 없는 교환이 많아 다른 정렬 알고리즘에 비해 성능이 떨어짐

 

 

 

4. 퀵 정렬

정의

• 분할 정복(divide and conquer) 알고리즘을 통해 정렬하는 알고리즘으로 피벗(pivot)을 기준으로 배열을 분할하고, 각 부분을 재귀적으로 정렬하는 알고리즘
• 제자리 정렬(In-place Sort)로 추가 메모리 공간을 거의 사용하지 않고, 배열 내에서 정렬함
• 안정 정렬이 아니기 때문에 동일한 값의 순서가 변경될 수 있음

 

 

시간 복잡도

• 평균: $O(N \log N)$
• 최악: $O(N²)$ (나쁜 피벗 선택 시)

 

 

정렬 단계

1. 피벗 선택
   • 배열에서 하나의 원소를 피벗(pivot)으로 선택함
   • 피벗은 배열의 첫 번째, 마지막, 중간 원소 또는 랜덤하게 선택할 수 있음
2. 피벗 기준으로 분할
   • 배열에서 두 개의 포인터를 사용하여, 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 차음
   • 두 값을 찾으면 서로 교환함 → 이렇게 하면 피벗보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 이동
   • 이 과정을 포인터들이 교차할 때까지 반복
3. 피벗 위치 결정
   • 교차가 완료되면 피벗을 그 위치에 놓고, 피벗을 기준으로 왼쪽과 오른쪽 부분 배열로 분할됨
4. 재귀적으로 정렬
   • 피벗을 기준으로 나뉜 왼쪽 부분 배열과 오른쪽 부분 배열에 대해 같은 과정을 재귀적으로 반복함
   • 즉, 각각의 부분 배열에 대해 새로운 피벗을 선택하고, 다시 분할하여 정렬함
5. 정렬 완료
   • 배열이 더 이상 분할되지 않을 때(부분 배열의 크기가 1이 되거나 빈 배열일 때) 재귀 호출이 끝나고, 배열이 모두 정렬됨

 

 

장점 및 단점

장점

• 평균 시간 복잡도가 $O(N \log N)$으로 효율적
• 데이터 양이 많을 때도 빠르게 동작

 

단점

• 나쁜 피벗을 선택하면 성능이 급격히 저하될 수 있음
• 재귀 호출이 깊어지면 스택 오버플로가 발생할 수 있음

 

 

 

5. 합병 정렬

정의

• 하나의 리스트를 두개의 균등한 크기로 재귀적으로 나누고, 분할된 부분 리스트를 정렬 후 다시 합병하여 정렬하는 알고리즘
• 분할 정복 알고리즘: 리스트를 절반으로 계속 분할하고, 분할된 리스트를 다시 합병하면서 정렬
• 안정 정렬(Stable Sort)로 동일한 값의 원소들 간의 순서를 유지
• 정렬을 위해 추가적인 메모리 공간 ($O(N)$)이 필요함

 

 

시간 복잡도

• 최선/최악/평균: $O(N \log N)$

 

 

정렬 단계

1. 리스트를 계속 반으로 나누기
   • 주어진 리스트를 두 개의 균등한 크기로 분할
   • 나눈 리스트를 재귀적으로 계속 분할하여, 리스트의 크기가 1이 될 때까지(혹은 0이 될 때까지) 반복
2. 부분 리스트 정렬
   • 리스트가 크기 1이 되면 더 이상 분할하지 않고, 이미 정렬된 상태로 간주함
   • 이제 병합(합치기) 단계로 넘어감
3. 부분 리스트 병합(합치기)
   • 두 리스트에서 가장 작은 값부터 선택해가면서 하나의 정렬된 리스트로 합병함
     • 여기서 중요한 것은 두 리스트가 이미 정렬돼 있어야함
     • 예를 들어, [4, 7]과 [1, 3]을 병합하면 [1, 3, 4, 7]이 됩니다.
4. 재귀적으로 병합 반복
   • 이 과정을 재귀적으로 수행하며, 병합된 리스트들이 다시 병합되어 최종적으로 정렬된 하나의 리스트가 완성됨
5. 정렬 완료
   • 모든 분할된 리스트가 병합되면 전체 리스트가 정렬됨

 

 

장점 및 단점

장점

• 평균 시간 복잡도가 $O(N \log N)$으로 효율적
• 데이터 양이 많을 때도 빠르게 동작

 

단점

• 작은 데이터셋에서는 삽입 정렬 등 다른 알고리즘에 비해 비효율적일 수 있음
• 재귀 호출이 깊어지면 스택 오버플로가 발생할 수 있음

 

 

 

6. Tim Sort 정렬

정의

• 삽입 정렬과 병합 정렬을 결합하여, 실생활 데이터에서 효율적으로 동작하도록 설계된 하이브리드 정렬 알고리즘
• Tim Sort는 데이터를 작은 런(run)으로 나눈 후, 각 런에 대해 삽입 정렬을 사용해 정렬한 뒤, 정렬된 런을 병합 정렬 방식으로 병합해 전체 리스트를 정렬
• 안정 정렬(Stable Sort)로 동일한 값의 원소들 간의 순서를 유지

 

 

시간 복잡도

• 최선: $O(N)$ (이미 거의 정렬된 경우)
• 평균/최악: $O(N \log N)$

 

 

장점 및 단점

장점

• 실제 사용되는 데이터 패턴에 최적화되어 매우 빠르게 동작
• 거의 정렬된 데이터에서 최선의 성능($O(N)$)을 보임

 

단점

• 병합 정렬과 삽입 정렬을 결합한 알고리즘이므로 구현이 복잡함
• 병합 정렬 기반이므로 추가 메모리 공간($O(N)$)을 필요로 함