파이썬 (합병 정렬과 이름 리스트 정렬하기)

합병 정렬은 전형적인 분할정복 알고리즘으로 볼 수 있으며 1945년에 존 폰 노이만이 개발하였고 아직까지도 많이 사용되고 있다. 분할 정복 알고리즘처럼 재귀적으로 가장 쉽게 설명할 수 있다.

1. 리스트의 길이가 0이나 1일 때 리스트는 이미 정렬된 상태이다.

2. 리스트에 한 개 이상의 요소가 들어있으면 리스트를  두 개의 리스트로 나눈 후에 합병정렬을  사용하여 나뉘어진 리스트를 정렬한다.

3. 결과를 합병한다.

우선 각 리스트의 첫 번째 요소를 보고 둘 중 작은 요소를 결과 리스트의 끝으로 옮기는 것이다. 만약 둘 중 하나의 리스트가 비게 되면, 남아있는 리스트의 요소들을 모두 결과 리스트에 옮기면 된다.

 

다음 코드는 두 개의 배치 함수를 정의하고 있으며 이 두 함수를 이용하여 두 가지 방법으로 리스트를 정렬하고 있다. 각 함수는 표준 파이썬 모듈 string을 가져와서 그 모듈의 split 함수를 사용한다. split의 인자는 두개의 문자열들이고 두번 째 인자는 문자열을 부분열로 나눌 때 사용하는 구분자를 나타낸다. 

# 이름 리스트 정렬하기
def merge(left, right, compare):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while (i < len(left)):
        result.append(left[i])
        i += 1
    while (j < len(right)):
        result.append(right[j])
        j += 1
    return result

import operator

def mergeSort(L, compare = operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L)//2
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        return merge(left, right, compare)
    
from string import *
def lastNameFirstName(name1, name2):
    name1 = name1.split(' ')
    name2 = name2.split(' ')
    if name1[1] != name2[1]:
        return name1[1] < name2[1]
    else : 
        return name1[0] < name2[0]
    
def firstNameLastName(name1, name2):
    name1 = name1.split(' ')
    name2 = name2.split(' ')
    if name1[0] != name2[0]:
        return name1[0] < name2[0]
    else:
        return name1[1] < name2[1]
    
L = ['Chris Terman', 'Tom Brady', 'Eric Grimson', 'Gisels Bundchen']
newL = mergeSort(L, lastNameFirstName)
print('Sorted by last name =', newL)
newL = mergeSort(L, firstNameLastName)
print('Sorted by first name =', newL)

L = [3, 5, 2]
D = {'a' : 12, 'c' : 5, 'b' : 'dog'}
print(sorted(L))
L.sort()
print(L)
print(sorted(D))

파이썬 함수 sorted은 리스트나 딕셔너리처럼 반복 가능한 객체를 첫 번째 인자로 받아서 정렬된 새로운 리스트를 반환한다.

 

출력 결과

Sorted by last name = ['Tom Brady', 'Gisels Bundchen', 'Eric Grimson', 'Chris Terman']
Sorted by first name = ['Chris Terman', 'Eric Grimson', 'Gisels Bundchen', 'Tom Brady']
[2, 3, 5]
[2, 3, 5]
['a', 'b', 'c']

sorted 함수를 딕셔너리에 실행하면 딕셔너리의 키 값으로 정렬한 리스트를 반환한다. list.sort 메소드와 sorted 함수 모두 두 개의 추가 매개변수를 사용할 수가 있다. key 매개변수는 합병정렬에서 compare와 같은 역할을 하는 것으로 비교 함수를 제공하기 위한 것이다. reverse 매개변수는 리스트가 오름차순인지 내림차순인지를 지정해준다. 다음 코드는 L의 요소들을 내림차순으로 정렬하여 출력한다.

L = [[1,2,3], (3,2,1,0), 'abc']
print(sorted(L, key = len, reverse=True))

출력 결과

[(3, 2, 1, 0), [1, 2, 3], 'abc']

list.sort 메소드와 sorted 함수는 안전 정렬 함수이다. 즉 비교할 때 두 개의 요소가 같다면 원래 리스트의 순서가 상대적으로 적용되어 최종 리스트에도 원래 순서로 유지가 된다.