정렬: 버블 정렬/선택 정렬/삽입 정렬/퀵 정렬/병합 정렬/기수 정렬

버블 정렬 (bubble sort)

두 인접한 데이터의 크기를 비교하여 정렬하는 방법

- 루프를 돌면서 인접한 데이터 간의 크기를 비교 후 swap 연산을 수행하여 정렬한다.

: 비교 연산이 필요한 루프 범위 설정 → "인접 데이터 비교 & swap 연산" 루프 범위까지 반복

→  정렬된 데이터는 정렬 영역으로 넘어감 → 정렬 영역을 제외하고 다음 루프를 실행

→ 비교 대상이 없을 때까지 반복

 

선택 정렬 (selection sort)

최솟값 or 최댓값을 찾아 남은 정렬 부분의 가장 앞의 데이터와 swap하는 방법

: 남은 정렬 부분에서 최솟값 or 최댓값을 찾음 → 남은 정렬 부분의 가장 앞의 데이터와 선택된 데이터를 swap

→ 남은 정렬 부분이 없을 때까지 반복

 

삽입 정렬 (insertion sort)

선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 방법

: 선택한 데이터가 정렬된 데이터 범위(sorted subarray)에 삽입될 위치를 탐색

→ 선택한 데이터를 넣음 (-1 씩 이동하는 for문을 이용하여 shift하면 된다)

→ 전체 데이터가 정렬될 때까지 (선택할 데이터가 없을 때까지) 반복

※ 삽입 위치 탐색 시, 이진 탐색 등의 탐색 알고리즘으로 시간 복잡도를 줄일 수 O

 

퀵 정렬 (quick sort)

기준값(pivot)을 선정하여, 해당 값과의 대소비교를 기준으로 2개의 집합으로 분류하는 방식을 반복하여 정렬하는 방법

- pivot 선정 방식이 시간 복잡도에 많은 영향을 미친다.

: pivot 선정 → pivot 값보다 작은 요소와 큰 요소의 집합을 분리

→ 분리된 집합의 크기가 1이 될 때까지 반복

: 이 부분은 어떻게 코드가 작성되는지 와닿지가 않아서, 예시 코드를 좀 더 찾아보았는데 재귀함수를 활용하여 반복하는 것 같다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

# Test the function
arr = [3,6,8,10,1,2,1]
print(quick_sort(arr))  # Output: [1, 1, 2, 3, 6, 8, 10]

 

 

병합 정렬 (merge sort)

분할 정복 방식을 사용하여 데이터를 분할하고, 분할한 집합을 정렬하여 합치는 알고리즘

: 가장 작은 데이터 집합으로 분할 → 병합하면서 정렬 → 분할된 집합이 없을 때까지 반복

 

- 2개의 그룹을 병합하는 과정 (투 포인터 개념을 사용)

: 왼쪽 포인터와 오른쪽 포인터의 값을 비교 → 작은 값을 결과 배열에 추가 후 해당 포인터를 오른쪽으로 1칸 이동

 

기수 정렬 (radix sort)

값을 직접 비교하는 것이 아닌, 비교할 자릿수를 정하여 해당 자릿수만 비교하는 방법

- 시간 복잡도가 가장 짧은 정렬로, 정렬해야 하는 데이터의 개수가 너무 많을 때 활용하면 좋다.

- 10개의 큐를 이용하며, 각 큐는 값의 자릿수를 대표한다.

: 일의 자릿수를 기준으로 데이터를 저장 → 일의 자릿수를 기준으로 정렬된 데이터 (큐는 선입선출이므로 pop)

→ 십의 자릿수를 기준으로 데이터를 저장하여 최종 정렬 데이터를 얻음