[Algorithm] 정렬 알고리즘 with python

'정렬 알고리즘' 이란

정렬 알고리즘은 섞여있는 데이터를 순서대로 나열하는 것을 뜻합니다.

 

대표적인 정렬 종류

O(n²)의 시간 복잡도 (정렬할 자료의 수가 늘어나면 제곱에 비례해서 증가)

1. 버블 정렬(Bubble Sort)

2. 선택 정렬(Selection Sort)

3. 삽입 정렬(Insertion Sort)

 

O(n log n)의 시간 복잡도

1. 병합 정렬(Merge Sort)

2. 퀵 정렬(Quick Sort)

 

 

1. 버블 정렬 (Bubble Sort)

버블 정렬이란 인접한 두 수를 비교하며 정렬해 나가는 방법으로 O(n²)의 느린 성능을 가지고 있습니다.

구현은 쉽지만 효율성이 가장 떨어지는 알고리즘입니다.

 

버블정렬 예시

arr = [6,5,3,1,8,7,2,4]

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

print(arr)

 

 

2. 선택 정렬 (selection Sort)

선택 정렬이란 한 바퀴 돌 때 가장 작은 값을 찾아 맨 앞과 교환하는 방식의 정렬입니다.

맨 앞에서부터 정렬해가는 특성을 가지고 있어서 버블 정렬과 마찬가지로 최악의 성능을 가진 알고리즘입니다.

arr = [6,5,3,1,8,7,2,4]
# min 은 최소값을 찾기 위함
# index 는 가장 작은 원소의 위치
min = 9999
for i in range(len(arr)):
    min = 9999
    for j in range(i,len(arr)):
        if min > arr[j]:
            min = arr[j]
            index = j
    
    arr[i], arr[index] = arr[index], arr[i]
print(arr)

 

3. 삽입 정렬 (Insertion Sort)

다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 때만 위치를 바꾸게 됩니다.

삽입정렬 예시

arr = [6,5,3,1,8,7,2,4]

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


print(arr)

 

4. 병합 정렬 (Merge Sort)

병합 정렬은  분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 알고리즘으로 시간 복잡도는 

지금까지 설명했던 정렬들과 달리 O(nlong n)을 가진다.

하나의 배열 or 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분리스트를 정렬한다음, 두개의 정렬된 부분 리스트or 배열을

합쳐서 하나의 배열or리스트를 얻는 방식이다.

 

 

구조적 이미지 (출처는 이미지에 링크달아놨습니다)

 

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

    if n<= 1:
        return
    
    mid = n //2
    left_group = arr[:mid]
    right_group = arr[mid:]

    merge_sort(left_group)
    merge_sort(right_group)

    left = 0
    right =0
    now = 0

    while left < len(left_group) and right < len(right_group):
        if left_group[left] < right_group[right]:
            arr[now] = left_group[left]
            left += 1
            now +=1 
        else:
            arr[now] = right_group[right]
            right += 1
            now += 1
    
    while left < len(left_group):
        arr[now] = left_group[left]
        left +=1
        now +=1
    
    while right < len(right_group):
        arr[now] = right_group[right]
        right +=1
        now +=1
    
if __name__ == '__main__':
    
    arr = [6,5,3,1,8,7,2,4]
    merge_sort(arr)
    print(arr)

예제는 재귀 알고리즘이 포함되어 있으므로 함수형으로 짜보았습니다.

 

5. 퀵 정렬 (Quick Sort)

퀵 정렬은 병합 정렬과 마찬가지로 분할 정복 정략을 사용하는 재귀 알고리즘입니다.빠른 정렬에서 분할 정복 전략을 사용하는 방법은 병합 정렬과 약간 다른데,병합 정렬은 분할 단계에서 거의 아무것도 하지 않고, 모든 중요한 작업은 결합 단계에서 일어나는데,퀵 정렬은 반대로 모든 작업이 분할 단계에서 일어납니다.다른 정렬 알고리즘보다 빠르며 많은 언어의 정렬 내장 함수로 퀵 정렬을 수행합니다.

 

def quick_sort(arr):
    if len(arr) <=1:
        return arr
    pivot = len(arr)//2
    front_arr,pivot_arr,back_arr = [], [], []
    for value in arr:
        if value < arr[pivot]:
            front_arr.append(value)
        elif value > arr[pivot]:
            back_arr.append(value)
        else:
            pivot_arr.append(value)
    
    return quick_sort(front_arr) + quick_sort(pivot_arr) + quick_sort(back_arr)
 
if __name__ == '__main__':
    
    arr = [6,5,3,1,8,7,2,4]
    arr = quick_sort(arr)
    print(arr)