[알고리즘] 정렬 이란 ( 합병, 퀵, 힙 )

1. 합병 정렬

 

하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 알고리즘이다.

 

합병정렬 시각화

 

분할 정복 알고리즘의 하나이며, 분할 정복 알고리즘은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음,

결과를 모아서 원래의 문제를 해결하는 전략이다.

 

합병 정렬 구현 Python

def mergesort(array):
    if len(array)<=1:
        return array
    
    mid = len(array)//2
    left = array[:mid]
    right= array[mid:]

    left_array = mergesort(left)
    right_array = mergesort(right)
    return merge(left_array, right_array)

def merge(left, right):
    result = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    return result

 

분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

기본적으로 위의 구조를 따라가고, 왼쪽 부분과 오른쪽 부분으로 나누어주는 분할을 하는 merge_sort 함수와

정복과 결합을 하는 merge 함수를 이용한다.

---

 

2.  퀵 정렬

 

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘이다.

 

퀵정렬 시각화

 

일반적인 상황에서 가장 많이 사용된다.

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(피봇)으로 설정한다.

왼쪽에서 부터는 피봇볻 큰 데이터를 선택하고, 오른쪽에서부터는 피봇보다 작은 값을 선택해서

서로 바꾸어주면서 진행한다.

 

 

퀵 정렬 구현 Python

def quicksort(array,start,end):
    if start>=end:
        return
    pivot = start
    left = start+1
    right = end
    while(left<=right):
        while(left<=end and array[left] <= array[pivot]):
            left+=1
        while(right>start and array[right] >= array[pivot]):
            right-=1
        if(left>right):
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]
    quicksort(array, start, right-1)
    quicksort(array, right+1, end)

 

 

기준 데이터인 pivot과  이동하기 위한 left, right를 만들어주고 

left는 왼쪽에서부터 right는 오른쪽에서부터 해당하는 값이 나올때까지 찾고

서로 엇갈리면 작은 데이터와 피봇을 교체, 엇갈리지 않으면 작은 데이터와 큰 데이터를 교체한다.

 

그리고 분할된 이후에는 오른쪽, 왼쪽 부분 각각 정렬을 수행한다.

 

---

3. 힙 정렬

힙이란 완전 이진트리 기반의 트리형 자료구로조써 최댓값이나 최솟값을 찾아내기 위해 사용된다.

힙에는 최대 힙과 최소 힙이 존재한다. 최대 힙은 부모 노드의 키가 자식 노드의 키보다 같거나 큰 완전 이진트리이며,

최소 힙은 자식노드의 키가 부모 노드의 키보다 같거나 큰 완전 이진트리입니다.

 

어떤 부모 노드의 두 자식 중 크기가 더 큰 자식을 부모와 바꾸는 알고리즘이다.

힙정렬 시각화

힙 정렬은 불안정 정렬에 속한다.

불안정 정렬이란 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘을 뜻한다. 대표적으로 퀵, 선택, 계수 정렬이이 있다.

 

 

 

 

힙 정렬 구현 Python

def insertionsort(array):
    n=len(array)
    for i in range(n):
        for j in range(i,0,-1):
            if array[j-1] > array[j]:
                array[j-1], array[j] = array[j], array[j-1]
            else:
                break

전체 배열의 길이만큼 반복하면서, 뒤에서 부터 반복해 적절한 위치를 찾아서 정렬하는 방식이다.