4가지 정렬 방법

1. 삽입정렬(insertion sort) :

정의: 주어진 수열에서 맨 앞에 있는 원소가 정렬되어 있다고 하고 2번째 원소부터 정렬된 수열에서 오름차순으로 자기 위치를 찾아간다.

Python

Insertion sort

1. 외부 루프(for i in range(1, len(arr)):)는 리스트의 첫 번째 원소를 제외한 모든 원소를 순회합니다. 첫 번째 원소는 이미 '정렬된' 부분으로 간주하기 때문입니다.
2. 각 단계에서, key 변수는 현재 정렬되지 않은 부분의 첫 번째 원소를 저장합니다.
3. 내부 루프(while j >=0 and key < arr[j] :)는 key보다 큰 모든 요소를 오른쪽으로 한 칸씩 이동시킵니다. 이 과정은 key를 올바른 위치에 삽입할 공간을 만듭니다.
4. key가 최종적으로 정렬된 부분의 적절한 위치에 삽입됩니다. (arr[j+1] = key)

2. 선택정렬(selection sort) :

정의: 주어진 수열에서 가장 작은 값을 찾아 첫번째 원소와 교체한다. 이것을 패스(pass) 혹은 단계라 한다. 다음 패스는 정렬되지 않은 나머지 수열에 대해서 같은 방식으로 적용한다. 정렬되지 않은 수열이 있으면 정렬이 완료될 때 까지 재귀적으로 적용한다.

Python

Selection sort

1. 외부 루프(for i in range(1, len(arr)):)는 리스트의 첫 번째 원소를 제외한 모든 원소를 순회합니다. 첫 번째 원소는 이미 '정렬된' 부분으로 간주하기 때문입니다.
2. 각 단계에서, key 변수는 현재 정렬되지 않은 부분의 첫 번째 원소를 저장합니다.
3. 내부 루프(while j >=0 and key < arr[j] :)는 key보다 큰 모든 요소를 오른쪽으로 한 칸씩 이동시킵니다. 이 과정은 key를 올바른 위치에 삽입할 공간을 만듭니다.
4. key가 최종적으로 정렬된 부분의 적절한 위치에 삽입됩니다. (arr[j+1] = key)

3. 힙정렬(heap sort) : 

정의 : 수열을 먼저 힙(배열)에 배치한 다음, 이를 힙의 성질(min tree을 활용하여 최소값이 root에 오도록 함)을 만족하도록 heap 구축과정을 실행한다. 이 과정이 완료되면 힙의 초기 상태가 된다. 이 힙에서 root의 값을 출력하면 수열의 최소값을 얻을 수 있다. root에 원소가 삭제되면 다시 힙의 성질을 만족하지 못하므로 힙을 재구축해야 한다. 이를 updateHeap()이라 한다. 이 과정은 수열이 정렬이 완료될 때까지 재귀적으로 적용된다.

Python

1. heapify 함수를 이용하여 주어진 배열을 최대 힙으로 구성합니다. 이 과정은 배열의 마지막 비-리프 노드부터 시작하여 루트 노드까지 순차적으로 진행됩니다.
2. 배열의 마지막 요소와 힙(배열)의 루트 요소를 교환합니다. 교환 후, 가장 큰 요소(힙의 루트)가 정렬될 위치에 배치됩니다.
3. 배열의 크기를 하나 줄인 뒤, 나머지 배열에 대해 heapify 함수를 호출하여 힙의 성질을 유지합니다. 이 과정은 배열의 모든 요소가 정렬될 때까지 반복됩니다.

4. 퀵정렬(quick sort) : 

정의 : 주어진 수열의 맨 앞에 오는 원소를 피봇(pivot)으로 한다. 이 pivot를 기준으로 작은 값은 왼쪽배열로 pivot보다 큰 값은 배열의 오른쪽에 온다. 이런 수행을 위해서 수열의 앞쪽에서 뒷쪽으로 이동하면서 pivot보다 큰 값을 선택하고, 뒷쪽에서 앞쪽으로 오면서 pivot보다 작은 값을 찾아서 앞에서 찾은 값과 교환한다. 더 이상 교환할 원소가 없으면 pivot과 pivot 보다 작은 값 중에 가장 오른쪽에 있는 원소와 바꾸어 pivot의 제자리를 찾는다. 여기까지가 하나의 패스가 된다. 분할된 리스트에 대해서는 이전의 pivot보다 작은 값을 가지는 리스트 먼저 수행한다.

Python

Quick sort

1. 배열의 길이가 1이하면, 그 배열은 이미 정렬되었다고 판단하고 그대로 반환합니다.
2. 배열의 첫 번째 요소를 피벗으로 선택합니다.
3. 피벗보다 작은 요소, 피벗과 같은 요소, 피벗보다 큰 요소로 배열을 나눕니다.
4. 나눈 작은 배열에 대해서 각각 재귀적으로 같은 과정을 반복합니다.
5. 최종적으로 정렬된 부분 배열들을 합쳐 결과 배열을 만들어 반환합니다.

삽입 정렬 (Insertion Sort)

• 특징: 각 숫자를 적절한 위치에 삽입하는 방식으로, 이미 정렬된 배열에 새 원소를 올바른 위치에 삽입해 나가면서 정렬하는 방법입니다.
• 시간 복잡도: 최악의 경우 (O(n^2)), 최선의 경우 (O(n))
• 공간 복잡도: (O(1))
• 장점: 데이터가 거의 정렬된 상태라면 매우 효율적입니다.
• 단점: 평균적으로 (O(n^2))의 시간 복잡도를 갖기 때문에 대량의 데이터에 대해서는 비효율적입니다.

선택 정렬 (Selection Sort)

• 특징: 전체 원소 중에서 최소값을 찾아 첫 번째 위치로 옮긴 다음, 나머지 원소를 대상으로 같은 작업을 반복합니다.
• 시간 복잡도: 항상 (O(n^2))
• 공간 복잡도: (O(1))
• 장점: 구현이 간단합니다. 어떤 상황에서도 (O(n^2))의 시간 복잡도를 가집니다.
• 단점: 비교적 효율이 낮은 편이며, 큰 데이터셋에는 부적합합니다.

Heap 정렬

• 특징: 이진 힙 트리 구조를 이용하여 정렬을 수행하는 알고리즘입니다.
• 시간 복잡도: 평균 및 최악의 경우 모두 (O(n \log n))
• 공간 복잡도: (O(1)) (In-place 정렬)
• 장점: 일정한 시간 복잡도를 보장합니다.
• 단점: 안정적인 정렬(Stable sort)이 아닙니다.
• 구현: 힙을 구성하여 최대 힙(Max Heap) 또는 최소 힙(Min Heap)의 루트를 배열 끝으로 옮기고, 배열의 크기를 줄여가며 반복적으로 힙을 재구성하는 방식으로 정렬합니다.

퀵 정렬 (Quick Sort)

• 특징: 분할 정복 알고리즘의 하나로, 분할된 두 개의 작은 문제를 재귀적으로 해결해 나가면서 전체 리스트를 정렬합니다.
• 시간 복잡도: 평균적으로 (O(n \log n)), 최악의 경우 (O(n^2))
• 공간 복잡도: (O(\log n)) (재귀의 깊이)
• 장점: 대부분의 경우 가장 빠른 수행 시간을 보여줍니다.
• 단점: 최악의 경우 시간 복잡도가 (O(n^2))까지 올라갈 수 있으며, 이는 pivot의 선택에 따라 달라집니다.

Bubble 정렬

• 특징: 인접한 두 원소를 비교하여 순서에 맞지 않으면 서로 자리를 바꾸는 과정을 반복하는 방식으로 정렬을 진행하는 알고리즘입니다.
• 시간 복잡도: 최악의 경우 (O(n^2)), 최선의 경우 (O(n)) - 이미 정렬된 경우
• 공간 복잡도: (O(1))
• 장점: 간단하고 코드가 직관적입니다.
• 단점: 정렬되지 않은 큰 데이터 집합에 대해서는 매우 비효율적인 정렬 방법입니다.