정렬 알고리즘 개념 및 동작 원리 총 정리 - CCGrape

목차

버블 정렬(Bubble Sort)
삽입 정렬(Insertion Sort)
선택 정렬(Selection Sort)
퀵 정렬(Quick Sort)
병합 정렬(Merge Sort)
힙 정렬(Heap Sort)
계수 정렬(Counting Sort)

---

버블 정렬(Bubble Sort) 개념 및 동작 과정

개념

버블 정렬(Bubble Sort)의 핵심은 인접한 두 원소를 비교하고 교환하면서 큰 값을 뒤로 밀어내는 것입니다. 이 과정이 반복되면서 가장 큰 값이 맨 뒤로, 그 다음 큰 값이 그 앞에, 이런 식으로 정렬됩니다.

거품이 위로 떠오르듯이 큰 값들이 리스트의 끝으로 밀려가는 모습에서 버블(Bubble)이라는 이름이 붙었습니다.

동작 과정

인접한 두 원소를 반복적으로 비교하여, 큰 값을 뒤로 밀어내는 방식으로 정렬합니다.

1. 인접한 두 원소를 비교하여 앞의 원소가 더 크다면, 두 값을 교환합니다.
2. 리스트의 끝까지 이 과정을 반복합니다.
3. 한 번의 반복(라운드)이 끝나면 가장 큰 값이 리스트의 맨 뒤에 위치합니다.
4. 다음 라운드에서는 이미 정렬된 마지막 원소를 제외하고 반복합니다.
5. 모든 원소가 정렬될 때까지 과정을 반복합니다.

[더 자세한 버블 정렬 포스팅]

---

삽입 정렬(Insertion Sort) 개념 및 동작 과정

개념

삽입 정렬(Insertion Sort)은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬(Insertion Sort)이라고 부릅니다. 첫 번째 요소는 이미 정렬된 것으로 가정하고, 두 번째 요소부터 시작하여 각 요소를 왼쪽의 정렬된 배열 부분에 삽입하여 전체를 정렬된 상태로 만듭니다.

이 알고리즘은 직관적으로 사람들이 카드를 손에 쥐고 정렬하는 방법과 비슷합니다.

동작 과정

1. 배열의 두 번째 요소부터 시작합니다.
2. 현재 요소를 key로 저장하고 그 앞에 있는 요소들과 비교하여 알맞은 위치를 찾습니다.
3. key보다 큰 요소들은 한 칸씩 오른쪽으로 이동시킵니다.
4. key보다 작은 요소를 만나면 그 위치에 key 값을 삽입합니다.
5. 전체 배열이 정렬될 때까지 1~4 과정을 반복합니다.

[더 자세한 삽입 정렬 포스팅]

---

선택 정렬(Selection Sort) 개념 및 동작 과정

선택 정렬(Selection Sort)은 비교 기반의 단순 정렬 알고리즘입니다.
이 알고리즘은 주어진 리스트에서 가장 작은 원소를 찾고, 그것을 현재 정렬되지 않은 부분의 가장 앞에 있는 원소와 교환하는 과정을 반복합니다. 이 과정이 리스트의 처음부터 끝까지 순차적으로 이루어지며, 모든 원소가 정렬될 때까지 반복됩니다.

동작 과정

1. 배열의 첫 번째 위치부터 시작해, 정렬되지 않은 부분의 가장 작은 원소를 찾습니다.
2. 가장 작은 원소를 현재 위치의 원소와 교환합니다.
3. 다음 위치로 이동하여 위의 과정을 반복합니다.
4. 배열의 끝에 도달하면 정렬이 완료됩니다.

[더 자세한 선택 정렬 포스팅]

---

퀵 정렬(Quick Sort) 개념 및 동작 과정

개념

퀵 정렬은 피벗(pivot)을 기준으로 데이터를 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어 정렬하는 분할 정복(Divide and Conquer) 알고리즘입니다. 나눠진 부분 배열에 대해 같은 과정을 재귀적으로 반복하여 정렬을 완성합니다.

동작 과정

1. 분할(Divide)
   • 리스트에서 하나의 요소를 피벗(pivot)으로 선택합니다.
     • 일반적으로 리스트의 첫 번째 요소, 마지막 요소 또는 중간 요소를 피벗으로 선택할 수 있습니다.
   • 피벗을 기준으로 리스트를 두 부분으로 분할합니다.
   • 피벗보다 작은 요소들은 피벗의 왼쪽 부분으로, 피벗보다 큰 요소들은 피벗의 오른쪽 부분으로 이동합니다.
2. 정복(Conquer)
   • 피벗을 기준으로 분할된 두 개의 하위 리스트에 대해 재귀적으로 퀵 정렬을 수행합니다.
     • 이 과정은 리스트의 크기가 0 또는 1이 될 때까지 반복됩니다.
   • 리스트의 크기가 0 또는 1이면 이미 정렬된 상태로 간주합니다.
3. 결합(Combine)
   • 분할된 리스트들이 모두 정렬되면, 이들을 결합하여 최종 정렬된 리스트를 얻습니다.
   • 결합 과정이 따로 필요하지 않고 재귀 호출이 완료되면서 자연스럽게 리스트가 정렬됩니다.

[더 자세한 퀵 정렬 포스팅]

---

병합 정렬(Merge Sort) 개념 및 동작 과정

개념

Merge Sort는 효율적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 전략을 기반으로 합니다. 이 알고리즘은 큰 데이터 세트를 작은 데이터 세트로 나누고, 정렬한 후 다시 합치는 방식으로 동작합니다.

동작 과정

1. 분할 (Divide)
   • 배열을 중간 인덱스를 기준으로 두 개의 하위 배열로 나눕니다.
   • 이 과정을 반복하여 각 배열의 크기가 1이 될 때까지 계속 나눕니다.
2. 정복 (Conquer)
   • 크기가 1인 배열(즉, 더 이상 분할할 수 없는 상태)은 기본적으로 정렬된 상태입니다.
   • 이제 이 배열들을 차례대로 합쳐서 정렬된 배열을 만들기 시작합니다.
3. 병합 (Merge)
   • 두 개의 정렬된 배열을 비교하여 작은 요소부터 순서대로 새로운 배열에 추가합니다.
   • 한 배열의 모든 요소가 다 추가되면, 다른 배열에 남아 있는 요소들을 모두 추가합니다.

[더 자세한 병합 정렬 포스팅]

---

힙 정렬(Heap Sort) 개념 및 동작 과정

개념

힙 정렬(Heap Sort)은 비교 기반의 정렬 알고리즘으로, 데이터 구조인 힙(Heap)을 이용하여 정렬을 수행합니다. 주로 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 사용하여 구현됩니다.

힙은 완전 이진 트리의 형태를 가지며, 특정 성질을 만족합니다. 최대 힙의 경우, 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 하며, 최소 힙의 경우는 반대입니다.

동작 과정

최대 힙(Max Heap) 기준으로 설명하겠습니다.

1. 힙 생성
   • 주어진 배열을 최대 힙으로 변환합니다.
   • 이를 위해 배열의 중간 인덱스부터 0까지 역순으로 힙을 조정(Heapify)합니다.
2. 정렬
   • 최대 힙이 생성된 후, 루트 노드(최대값)를 배열의 마지막 요소와 교환합니다.
   • 그 후, 힙의 크기를 1 줄이고, 루트 노드부터 다시 힙을 유지하도록 조정합니다(Heapify).
   • 이 과정을 배열의 크기가 1이 될 때까지 반복합니다.

[더 자세한 힙 정렬 포스팅]

---

계수 정렬(Counting Sort) 개념 및 동작 과정

개념

계수 정렬(Counting Sort)은 정수로 표현된 데이터의 개수를 셈(count)하여 정렬하는 알고리즘입니다.
값의 범위가 제한된 경우에 매우 빠르게 동작하며, 비교 기반 정렬 알고리즘이 아니라는 특징이 있습니다. 주로 원소의 크기 범위가 좁을 때 유용합니다.

동작 과정

1. 입력 배열의 최대값을 찾기
   • 정렬할 데이터의 최대값을 기준으로 배열을 생성합니다.
2. 각 원소의 개수를 세기
   • 입력 배열의 원소가 등장하는 빈도를 기록한 카운트 배열(count array)을 만듭니다.
3. 카운트 배열을 누적합으로 변환
   • 누적합 배열로 변환하여 각 원소가 최종 배열에서 들어갈 위치를 계산합니다.
4. 입력 배열을 역순으로 순회하면서 정렬된 배열에 삽입
   • 입력 배열의 끝에서부터 순회하며 정렬된 결과 배열에 값을 넣습니다.
   • 이 과정에서 안정 정렬이 보장됨.

[더 자세한 계수 정렬 포스팅]

---

궁금한 점은 댓글로 남겨주세요.
감사합니다.