[자료구조] sort 정렬 알고리즘

자료구조나 알고리즘 공부를 다시 하려고 합니다.

그 중 기본이 되는 여러 알고리즘 중 sort(정렬)에 대해 정리하고자 합니다.

 

1. 정렬이란?

 - 배열에서 특정 기준에 따라 데이터를 데이터를 늘어놓는 알고리즘

 

 

2. 버블정렬

• 인접한 리스트 비교해서  정렬 진행
• 구현이 쉽다. But 효율성이 떨어진다.(시간복잡도 n^2)

#버블정렬 (bubbleSort)
def bubble_Sort(arr):
    n = len(arr)

    for i in range(n):
        for j in range(0,n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr
    
    arr = [4, 3, 7, 1, 9, 2]
    #result
    Sorted array:  [1, 2, 3, 4, 7, 9]

3. 선택정렬

• 가장 작은 데이터를 선택해서정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법입니다.
• 시간복잡도는 n^2 이다.

def Selection_Sort(arr):
    n = len(arr)

    for i in range(n):
        min_idx = i

        for j in range(i+1,n):
            if arr[min_idx] > arr[j]:
                min_idx = j

        arr[min_idx], arr[i] = arr[i], arr[min_idx]

    return arr
    
    
    arr = [4, 3, 7, 1, 9, 2]
    #result
    Sorted array:  [1, 2, 3, 4, 7, 9]

4. 삽입정렬

• key 값 뒤에 있는 원소와 비교해 정렬
• 데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는 방법
• 시간복잡도는 최선의 경우 n  최악의 경우  n^2 이다.

def Insertion_Sort(arr):
    n = len(arr)

    for i in range(1,n): #두번째 요소부터 시작
        for j in range(i, 0, -1): 
            if arr[j] < arr[j-1]: 
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break

    return arr
    
    arr = [4, 3, 7, 1, 9, 2]
    #result
    Sorted array:  [1, 2, 3, 4, 7, 9]

5. 퀵정렬

• 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와 비교하며 정렬하는 비교정렬에 속한다.
• 분할 정복 알고리즘의 하나로 다른 정렬 알고리즘 중에서도 빠른편에 속한다.
• 기준 p값을 정한 후, p기준으로 분할/정렬 수행
• 시간복잡도는 평균적으로 (NlogN) 이다.
• But 병합정렬과 다르게 최악의 경우 (시간복잡도 N^2) 이라는 단점이 있다.
  * 이 때문에 p값을 배열의 중간이나 값을 랜덤 값으로 잡습니다.

def Quick_Sort(arr, start, end):

    if start >= end:
        return arr

    pivot = start
    left = start +1
    right = end

    while left <= right:
        while left <= end and  arr[left] <= arr[pivot]:
            left += 1

        while right > start and arr[right] >= arr[pivot]:
            right -= 1

        if left > right:
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else:
            arr[left], arr[right] = arr[right], arr[left]

    Quick_Sort(arr, start, right-1)
    Quick_Sort(arr, right+1, end)

    return arr
    
    
    arr = [4, 3, 7, 1, 9, 2]
    #result
    Sorted array:  [1, 2, 3, 4, 7, 9]

6. 병합정렬

• 분할정복 기법과 재귀 알고리즘을 이용해서 배열의 원소가 하나만 있을 때까지 쪼개고 다시 크기 순으로 재배열하는 방식입니다.
• 병합을 진행할 때 추가 배열을 요구
• 시간복잡도는 모든 경우 (NlogN)으로, 안정적이고 일정한 것이 장점이다.
• 다만 배열 크기가 매우 크면 별로 좋지 않습니다. 
• 분할 - 인접리스트를 분할 리스트로 '분할'
• 정복 - 부분 리스트에  대해 정렬
• 병합 - 정렬된 부분 리스트 병합(결합)

* 과정

각 요소가 1개의 리스트로 분할하고 이에 대해 정복을 통해 점차 결합하여 정렬을 진행하는 방식

def Merge_Sort(arr):
    if len(arr) <= 1:
        return arr
    
    #배열 중앙 2분할
    mid = len(arr)//2
    low_arr = Merge_Sort(arr[:mid])
    high_arr = Merge_Sort(arr[mid:])

    merged_arr = []
    l = h = 0

    while l < len(left) and h < len(right):
        if left[l] < right[h]:
            merged_arr.append(left[l])
            l += 1

        else:
            merged_arr.append(right[h])
            h += 1
    #병합
    merged_arr += left[l:]
    merged_arr += right[h:]

    return merged_arr
    
    arr = [4, 3, 7, 1, 9, 2]
    #result
    Sorted array:  [1, 2, 3, 4, 7, 9]

7. 계수정렬(Counting Sort)

• 특정한 값을 가지는 데이터의 개수를 '카운트'하는 방법입니다.
• 데이터의 크기가 한전되어 있는 경우에만 사용이 가능하지만, 매우 빠릅니다.
• 시간복잡도는 O(N + K)이며, K는 데이터 중에서 가장 큰 양수를 의미합니다.

#리스트 활용
def counting_sort(arr):
    max_arr = max(arr)
    count = [0] * (max_arr + 1)
    sorted_arr = list()
    
    for i in arr:	# 카운팅
        count[i] += 1

    for i in range(max_arr + 1):
        for _ in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr
    
    
#딕셔너리
def counting_sort(arr):
    count = dict()
    sorted_arr = list()
    
    for i in arr:
        if i in count:
            count[i] += 1
        else:
            count[i] = 1

    for i in sorted(count.keys()):
        for _ in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr
    
    
    arr = [4, 3, 7, 1, 9, 2]
    #result
    Sorted array:  [1, 2, 3, 4, 7, 9]

* 파이썬 기본 정렬 알고리즘 (.sort( ))

파이썬 내부에 있는 "sort", "sorted" 함수는 최악의 경우에도  (NlogN)의 시간복잡도를 보장해줍니다.

따라서 계수 정렬을 통해 매우빠른 정렬을 해야하는 케이스가 아니라면 해당 함수를 사용하는 것이 가장 합리적이다.