C++ 정렬 알고리즘 정리!! STL!! #Insertion Sort#Selection Sort#Bubble Sort#Merge Sort#Quick Sort#Heap Sort

1. 삽입 정렬 (Insertion Sort)

 : 삽입 정렬은 요소를 하나씩 비교하면서 정렬된 부분 배열에 삽입하여 정렬을 수행합니다.
정렬되지 않은 요소가 하나씩 정렬된 배열의 적절한 위치에 삽입되어 정렬되는 과정을 반복하여, 정렬된 배열을 구성합니다.
삽입 정렬은 구현하기 쉬우며, 작은 데이터 세트에서는 효율적인 정렬 알고리즘이지만, 배열의 크기가 증가할수록 성능이 떨어집니다. 최악의 경우 O(n^2)의 시간 복잡도를 가지며, 최선의 경우 O(n)의 시간 복잡도를 가집니다.

예시 코드

 

2. 선택 정렬 (Selection Sort)

택 정렬은 배열에서 가장 작은 값을 찾아 배열의 맨 앞으로 이동시키고, 그 다음으로 작은 값을 찾아 배열의 두 번째 위치로 이동시키는 과정을 반복하여 정렬을 수행합니다.
정렬되지 않은 부분의 첫 번째 요소를 선택하여 나머지 요소들과 비교하여 가장 작은 값을 찾아 정렬된 부분의 맨 끝에 위치시키고, 다음으로 정렬되지 않은 부분의 첫 번째 요소를 선택하여 위 과정을 반복합니다.
선택 정렬은 구현하기 쉽지만, 배열의 크기가 증가할수록 성능이 떨어집니다. 최악의 경우 O(n^2)의 시간 복잡도를 가지며, 최선의 경우에도 O(n^2)의 시간 복잡도를 가집니다.

예시 코드

 

3. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소의 값을 비교하여 정렬하는 방식으로 동작합니다.
정렬되지 않은 부분에서 인접한 두 요소의 값을 비교하여 큰 값을 뒤로 이동시키며, 이 과정을 정렬되지 않은 부분의 마지막 요소까지 반복합니다. 이 과정을 반복하면 가장 큰 값이 배열의 가장 뒤로 이동하게 되고, 이후 다시 처음부터 같은 과정을 반복하여 정렬을 완료합니다.
버블 정렬은 구현하기 쉽지만, 배열의 크기가 증가할수록 성능이 떨어집니다. 최악의 경우 O(n^2)의 시간 복잡도를 가지며, 최선의 경우에도 O(n^2)의 시간 복잡도를 가집니다.

예시 코드

 

4. 합병 정렬 (Merge Sort)

합병 정렬은 배열을 반으로 나누어 각각을 정렬한 다음, 두 개의 정렬된 배열을 병합하여 하나의 정렬된 배열로 만듭니다. 이 과정을 반복하여 정렬을 수행합니다.
합병 정렬은 안정적인 정렬 알고리즘이며, 평균 시간 복잡도는 O(nlogn)입니다. 하지만 공간 복잡도가 O(n)으로 비교적 큰 편입니다.

예시 코드

5. 퀵 정렬 (Quick Sort)

퀵 정렬은 특정한 값(피벗(pivot))을 기준으로 작은 값과 큰 값으로 나누어 정렬하는 방식입니다. 퀵 정렬은 일반적으로 재귀적인 방식으로 구현되며, 배열을 반으로 나누어 각각을 정렬한 다음, 두 개의 정렬된 배열을 병합하지 않고 합칩니다.
퀵 정렬의 평균 시간 복잡도는 O(nlogn)이며, 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있습니다. 하지만 대부분의 경우 평균 시간 복잡도에 근접하게 수행되므로 실제로 매우 빠른 알고리즘 중 하나입니다.

예시 코드

 

6. 힙 정렬 (Heap Sort)

힙은 트리(tree) 자료구조의 일종으로, 부모 노드와 자식 노드간의 대소 관계가 정해져 있는 자료구조입니다. 이를 이용하여 힙 정렬은 다음과 같은 방식으로 수행됩니다.
1. 주어진 배열을 힙으로 변환합니다. 이때, 배열을 이진 트리로 생각하여 각 노드는 자신의 자식 노드들보다 큰 값을 가지도록 조정합니다. 이를 Max Heap이라고 합니다.
2. Max Heap에서 가장 큰 값을 가져와서 배열의 가장 마지막 값과 교환합니다.
Max Heap의 크기를 하나 줄입니다.
3. 1~3 과정을 반복하여 정렬이 완료될 때까지 수행합니다.
힙 정렬의 시간 복잡도는 항상 O(nlogn)입니다. 하지만 상수항이 매우 크기 때문에 퀵 정렬보다는 느린 편입니다. 또한, 힙 정렬은 입력 배열에 대해 in-place 정렬이 가능하기 때문에, 추가적인 메모리 공간을 필요로 하지 않는 장점이 있습니다.

예시 코드

 

이렇게 C++ STL 정리를 해봤습니다!!