정렬 (Sort)

정렬(Sort)은 데이터를 특정 기준에 따라 순서대로 정렬하는 것을 의미한다. 정렬은 다양한 알고리즘과 기법을 사용하여 구현할 수 있으며, 프로그래밍 언어에서도 정렬을 위한 내장 함수나 라이브러리를 제공한다.

Baekjoon - Sorting

Algorithms Visualized - Sorting

from functools import cmp_to_key

arr = [(3, 6), (2, 4), (4, 5)]

# arr 요소의 순서를 바꾸지 않음
sorted_arr = sorted(arr, key = lambda x: x[1], reverse = False)

# arr 요소의 순서를 바꿈
arr.sort(key = lambda x: x[1], reverse = False)

# 정렬 방식 선언
def sort_function(x1, x2):
    if x1[1] > x2[1]: return 1
    elif x1[1] == x2[1]: return 0
    else: return -1

arr.sort(key = cmp_to_key(sort_function))

Bubble Sort

1. 리스트의 첫 번째 원소부터 시작한다.

2. 현재 원소와 그 다음 원소를 비교한다.

3. 만약 현재 원소가 다음 원소보다 크다면, 두 원소를 교환한다.

4. 다음 원소로 이동하여 2번과 3번 과정을 반복한다.

5. 리스트의 끝까지 도달했을 때, 가장 큰 원소가 맨 뒤로 이동하게 된다.

6. 정렬되지 않은 부분 리스트(마지막 원소를 제외한 나머지)에 대해 1부터 5까지의 과정을 반복한다.

7. 정렬이 완료될 때까지 위의 과정을 반복합니다.

Selection Sort

1. 주어진 리스트에서 최솟값을 찾는다.

2. 최솟값을 현재 정렬 범위의 가장 왼쪽 값과 교환한다.

3. 정렬 범위를 한 칸 오른쪽으로 이동한다.

4. 위의 과정을 정렬 범위가 리스트의 끝까지 이동할 때까지 반복한다.

Insertion Sort

1. 리스트의 두 번째 요소부터 시작한다. 첫 번째 요소는 이미 정렬된 부분 리스트로 간주한다.

2. 현재 요소를 정렬된 부분 리스트와 비교한다. 이를 위해 현재 요소를 임시 변수에 저장한다.

3. 정렬된 부분 리스트의 끝부터 시작하여 현재 요소와 비교한다. 현재 요소보다 큰 값이 나타나면 그 뒤로 모든 요소를 오른쪽으로 한 칸씩 이동시킨다.

4. 비교한 요소보다 작은 값을 만나거나 정렬된 부분 리스트의 시작에 도달하면, 임시 변수에 저장된 값을 그 위치에 삽입한다.

5. 리스트의 다음 요소로 이동하여 위의 과정을 반복한다.

6. 리스트의 모든 요소를 반복하면 정렬이 완료된다.

Quick Sort

1. 피벗(Pivot) 선택: 리스트에서 하나의 요소를 선택한다. 이를 피벗으로 설정한다. 피벗은 리스트를 기준으로 작은 값과 큰 값으로 분할하는 역할을 한다.

2. 분할: 피벗을 기준으로 리스트를 두 개의 하위 리스트로 분할한다. 피벗보다 작은 값은 피벗의 왼쪽에 위치하고, 큰 값은 피벗의 오른쪽에 위치하도록 한다. 피벗은 최종적으로 자신이 위치해야 할 인덱스를 찾는다.

3. 재귀적 정렬: 피벗을 기준으로 분할된 두 개의 하위 리스트에 대해 재귀적으로 퀵 정렬을 수행한다. 각 하위 리스트에 대해 분할과 재귀적 정렬을 반복하면서 전체 리스트를 정렬한다.

4. 합병: 분할된 하위 리스트들이 정렬된 후에는 하위 리스트들을 합병하여 최종적인 정렬된 리스트를 얻는다.

Merge Sort

1. 분할(Divide): 정렬되지 않은 리스트를 반으로 나눈다. 이 과정은 재귀적으로 수행되며, 리스트가 더 이상 나눌 수 없을 때까지 계속된다.

2. 정복(Conquer): 나뉜 리스트를 정렬한다. 리스트가 더 이상 나눠지지 않을 때, 각각의 작은 리스트는 단일 요소로 간주되어 정렬된다.

3. 병합(Merge): 정렬된 작은 리스트를 다시 하나의 정렬된 리스트로 병합한다. 이 단계에서는 정렬된 리스트를 순서대로 비교하여 병합하면서 최종 정렬된 리스트를 만든다.

Tree Sort

1. 정렬되지 않은 원소들로 이진 탐색 트리를 생성한다. 이진 탐색 트리는 각 노드가 왼쪽 서브트리의 값보다 크고 오른쪽 서브트리의 값보다 작은 조건을 만족한다.

2. 원소들을 이진 탐색 트리에 삽입한다. 이때, 삽입 순서에 따라 트리의 구조가 결정된다.

3. 이진 탐색 트리를 중위 순회하면서 원소들을 정렬된 순서로 출력한다. 중위 순회는 왼쪽 서브트리를 순회한 뒤 현재 노드를 출력하고, 오른쪽 서브트리를 순회하는 방식으로 수행된다.

Heap Sort

1. 주어진 배열을 힙으로 변환한다. 배열을 힙으로 변환하기 위해서는 배열의 요소를 하나씩 힙에 삽입하면서 힙의 조건을 만족하도록 조정해야 한다. 이 단계를 힙 구성(Heapify) 단계라고 한다.

2. 힙에서 최대값(또는 최소값)을 추출한다. 최대 힙(Max Heap)의 경우 최대값은 루트 노드에 위치하며, 최소 힙(Min Heap)의 경우 최소값은 루트 노드에 위치한다.

3. 추출한 최대값(또는 최소값)을 정렬된 배열의 뒷부분에 채운다.

4. 힙에서 루트 노드를 제거한 후, 남은 요소들을 다시 힙 조건을 만족하도록 조정한다.

5. 위 단계 2~4를 반복하여 정렬이 완료될 때까지 진행한다.

Counting Sort

1. 입력 데이터의 범위를 확인하여, 데이터의 최소값과 최대값을 알아낸다.

2. 최소값과 최대값의 범위를 기반으로, 범위만큼의 크기를 가지는 배열을 생성한다. 이 배열을 "계수 배열"이라고 한다.

3. 입력 데이터를 순회하면서, 각 데이터의 값과 일치하는 계수 배열의 인덱스에 해당하는 위치에 데이터 개수를 증가시킨다. 즉, 각 데이터의 개수를 계수 배열에 저장한다.

4. 계수 배열을 순회하면서, 각 인덱스의 값과 그 이전 인덱스들의 값의 합을 구한다. 이를 통해 각 데이터의 정렬된 위치를 알 수 있다.

5. 입력 데이터를 역순으로 순회하면서, 해당 데이터의 값을 계수 배열의 인덱스로 사용하여 정렬된 위치에 데이터를 배치한다.

6. 정렬된 데이터를 반환한다.

Radix Sort

1. 정렬하려는 수들 중에서 가장 큰 자릿수를 찾는다. 이를 통해 정렬할 횟수를 결정한다.

2. 0부터 9까지의 숫자를 기준으로, 각 자릿수에 해당하는 숫자들을 선형 큐(Linear Queue) 또는 버킷(Bucket)에 넣는다.

3. 가장 낮은 자릿수부터 큐에 있는 숫자들을 꺼내서 원래 순서대로 다시 배열한다. 이 과정을 가장 높은 자릿수까지 반복한다.

4. 모든 자릿수에 대한 반복이 끝나면, 최종적으로 정렬된 배열이 완성된다.