IT-garden

병합정렬은 하나의 리스트를 같은 크기의 두개로 분할합니다.

분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합해 전체 정렬을 시킵니다.

각각의 부분 리스트를 정렬하기 위해 순환 호출하는 식으로 실행됩니다.

병합정렬은 분할 정복 방법에 바탕을 둡니다.

병합정렬에서 정렬이 이루어지는 시점은 두 개의 리스트를 병합하는 시점입니다. 

병합과정에서는 두 개의 리스트 요소들을 처음부터 비교해서 두 개의 리스트 요소 중 더 작은 요소를 리스트에 넣어줍니다.

두 리스트 중 하나가 끝날 때까지 이 과정을 반복합니다.

하나의 리스트가 먼저 끝나면 나머지 리스트의 요소들을 리스트에 넣어줍니다.

2 > 1 이기 때문에 1을 먼저 첫번째 위치에 넣어줍니다.

2 < 3 이기 때문에 2를 두번째 위치에 넣어줍니다.

4 > 3 이기 때문에 3을 세번째 위치에 넣어줍니다.

4 < 6 이기 때문에 4을 네번째 위치에 넣어줍니다.

5 < 6 이기 때문에 5를 다섯번째 위치에 넣어줍니다.

왼쪽 리스트가 끝났기 때문에 오른쪽 리스트의 나머지 요소들(6, 7)을 리스트에 넣어줍니다.

병합정렬의 파이썬 코드입니다.

def merge_sort(a):
    if len(a) <= 1:
        return

    mid = len(a) // 2   
    one = a[:mid] 
    two = a[mid:]
   
    merge_sort(one)  # 왼쪽 정렬
    merge_sort(two)  # 오른쪽 정렬

    i = 0
    j = 0
    c = 0

    while i < len(one) and j < len(two):
        if one[i] < two[j]:
            a[c] = one[i]
            i += 1
        else:
            a[c] = two[j]
            j += 1
            
        c += 1 

    while i < len(one):
        a[c] = one[i]
        i += 1
        c += 1

    while j < len(two):
        a[c] = two[j]
        j += 1
        c += 1
     
b = [5, 2, 4, 6, 1, 7, 3]
merge_sort(b)

# 결과>>[1, 2, 3, 4, 5, 6, 7]
print(b)

퀵정렬은 리스트의 한 요소를 선택해 피벗(pivot)으로 선택합니다.

피벗은 리스트의 첫 번째 요소나 마지막 요소 혹은 아무거나 선택 가능합니다.

혹은 리스트 내의 값 중에 크기순으로 중간 값을 선택하는 경우도 있습니다.

피벗을 중심으로 피벗보다 작은 요소들은 왼쪽에 구성되고 피벗보다 큰 요소들은 오른쪽에 구성됩니다.

그리고 왼쪽에 있는 요소들을 가지고 피벗을 선택하고 정렬을 합니다. 마찬가지로 오른쪽에 있는 요소들도 피벗을 선택해 정렬을 합니다.

즉, 퀵정렬은 부분 리스트에 대해 순환 호출하는 식으로 실행됩니다.

더이상 부분 리스트가 분할이 불가능할 때까지 실행하면 전체를 정렬할 수 있습니다. 

퀵정렬은 평균적으로 빠른 수행 속도를 자랑하는 정렬 방법입니다.

하지만 리스트가 불균형하게 나눠질 경우 시간 복잡도는 나빠집니다.

피벗은 마지막 요소로 설정하였습니다.

2 < 3 이기 때문에 5와 2를 교환해줍니다.

1 < 3 이기 때문에 5와 1을 교환해줍니다.

피벗보다 작은 요소들을 왼쪽에 구성하기 위해 리스트의 앞자리부터 순서대로 교환해줍니다.

피벗보다 작은 요소들은 2, 1이기 때문에 다음 리스트의 값과 피벗값을 바꿔줍니다.

첫번째 과정을 통해 3은 정렬 완료 되었습니다.

퀵정렬의 파이썬 코드입니다.

def quick_sort(a, start, end):

    if start >= end:
        return 

    pivot = a[end]
    i = start
    
    for j in range(start, end):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i = i + 1
    
    a[i], a[end] = a[end], a[i]
    
    quick_sort(a, start, i - 1) # pivot보다 작은 그룹
    quick_sort(a, i + 1, end)  # pivot보다 큰 그룹

 
def quick_sorted(a):
    quick_sort(a, 0, len(a) - 1)

b = [5, 2, 4, 6, 1, 7, 3]
quick_sorted(b)

# 출력>>[1, 2, 3, 4, 5, 6, 7]
print(b)

버블정렬은 이웃하는 숫자를 비교하여 작은 수를 앞으로 이동시키는 과정을 반복합니다.

이를 한번 진행하면 가장 큰 수가 리스트의 오른쪽 끝으로 이동합니다. 그럼 오른쪽 리스트는 정렬된 상태가 됩니다.

이 과정을 리스트 크기- 1 까지 반복하면 전체를 정렬할 수 있습니다.

작은 수를 앞으로 이동시키는 과정이 물속에서 버블(거품)이 떠오르는 것과 유사하여 버블정렬이라는 이름을 사용합니다. 

3 > 2 이기 때문에 3과 2를 교환해줍니다.

3 은 5보다 크지 않기 때문에 교환하지 않습니다.

5 > 4 이기 때문에 5와 4를 교환해줍니다.

5 > 1 이기 때문에 5와 1를 교환해줍니다.

첫번째 과정을 통해 5는 정렬 완료 되었습니다.

다음 반복때는 5를 제외하고 정렬합니다.

버블정렬의 파이썬 코드입니다.

a = [3, 2, 5, 4, 1]

for i in range(len(a)-1):
    for j in range(len(a)-1-i):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
        
# 출력>>[1, 2, 3, 4, 5]
print(a)

삽입정렬은 리스트나 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눕니다.

그 후 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입해 정렬되도록 합니다.

이 과정을 정렬되지 않은 부분이 없어질 때까지 반복하면 전체를 정렬할 수 있습니다.

삽입 정렬은 리스트의 상태에 따라 시간복잡도가 달라질 수 있습니다.

삽입 정렬은 거의 정렬이 되어 있는 경우에 새로운 원소를 추가할 때 다른 정렬 방법들보다 유용합니다.

삽입정렬의 파이썬 코드입니다.

a = [3, 2, 5, 4, 1]

for i in range(1,len(a)):
    key = a[i]
    
    j = i - 1

    while j >= 0 and a[j] > key:
        a[j+1] = a[j]
        j = j - 1

    a[j+1] = key
 
# 출력>>[1, 2, 3, 4, 5]
print(a)

선택정렬은 리스트나 배열 전체에서 최솟값을 선택해서 리스트의 첫 번째 원소와 자리를 바꿉니다.

그 후 첫번째 요소를 제외한 나머지 요소들 중 가장 작은 값을 선택해 이를 두 번째 원소와 자리를 바꿉니다.

이 과정을 계속 리스트 크기- 1 까지 반복하면 전체를 정렬할 수 있습니다.

리스트 외에 다른 추가 메모리를 요구하지 않아 제자리 정렬(in-place sorting)이라고도 합니다.

리스트가 대체적으로 정렬되어 있던, 역으로 정렬되어 있던 항상 일정한 시간 복잡도를 나타낸다는 특징이 있습니다.

따라서 다른 정렬 알고리즘에 비해 효율성이 많이 떨어집니다.

선택정렬의 파이썬 코드입니다.

a = [2, 3, 5, 4, 1]

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

# 결과>>[1, 2, 3, 4, 5]
print(a)

정렬은 물건을 오름차순이나 내림차순으로 나열하는 것을 의미합니다.

정렬은 모든 과학 기술 분야에서 사용되는 기본적이고 중요한 알고리즘입니다.

예를 들어 사람을 키 순서대로 세우기, 인터넷 가격 비교 사이트에서 제품을 가격순으로 나열하는 것이 있습니다.

정렬 알고리즘은 여러 가지이지만 모든 경우에 있어서 최상의 성능을 보여주는 알고리즘은 존재하지 않습니다.

실행 프로그램에 가장 알맞은 정렬 알고리즘을 선택해서 사용해야 합니다.

정렬 알고리즘은 크게 2가지로 나눠집니다.

첫 번째는 단순하지만 비효율적인 정렬 알고리즘이고 나머지는 복잡하지만 효율적인 정렬 알고리즘입니다.

단순하지만 비효율적인 정렬 알고리즘 - 선택 정렬, 삽입 정렬, 버블 정렬

복잡하지만 효율적인 정렬 알고리즘 - 퀵 정렬, 히프 정렬, 합병 정렬