파이썬 #12 (정렬 알고리즘)

# 코드 페스티벌 파이썬 100제 풀기

 

<문제 51>

병합 정렬(merge sort)을 만드는 문제이다.

기존에 주어진 코드에 빈칸을 채워서 병합 정렬을 완성하면 된다.

 

병합 정렬에 대해 간단히 소개하자면

1. 리스트의 길이가 0 or 1이면 이미 정렬된 것으로 본다.

2. 그 외에 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

3. 각 부분 리스트를 재귀(Recursion)적으로 합병 정렬을 이용해 정렬한다.

4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

종료 조건은 리스트의 길이가 0 또는 1이면 리스트 값을 반환하고 종료한다.

리스트의 길이를 반으로 나누어서 재귀 함수로 그룹 1과 2를 만들어준다.

나중에 병합을 할 result 리스트를 만들어준 다음에 pop 함수로 result에 하나씩 값을 저장할 while 문을 작성해준다.

여기서 group_one = [180, 145, 165, 45] / group_two = [170, 175, 173, 171]가 된다.

인덱스 0번째 위치인 180과 170을 비교하고 각 if, else문에 찾아 들어가서 result에 값을 append 시켜준다.

제일 상단의 while문을 그냥 지나게 되면 나머지 리스트에 남은 값들을 검사해서 append 시켜주는 while문도 2개 만들어준다.그렇게 하면 차례대로 리스트의 값이 정렬됨을 볼 수 있다.

 

이것 외에 또 다른 병합 정렬 알고리즘을 보려고 한다.일반적인 병합 정렬 알고리즘이라고 해서 위의 알고리즘과 정렬 원리는 같지만, return 값이 없고리스트 안의 자료 순서를 직접 바꾸는 차이점을 가진 병합 정렬 알고리즘이 있다.

종료 조건은 자료 개수가 한 개 이하면 정렬할 필요가 없다.

재귀 호출로 그룹 1과 2를 정렬하고 두 그룹을 하나로 병합하기 위해 r1, r2, ra를 만들어준다.

각 그룹의 길이보다 커질 때까지 반복하는 while문을 만들어준 다음에,

두 그룹의 인덱스를 0부터 비교해서 리스트 x에 다시 저장시켜준다.

저장시킨 다음에 인덱스 숫자를 1씩 증가시켜주고, while문 2개를 만들어서 남아 있는 자료들을 결과에 추가시켜준다.

위, 아래 모두 같은 결과를 올바르게 출력되었다.

 

중요한 것은 병합 정렬의 계산 복잡도는 O(n ·logn)으로 선택 정렬이나 삽입 정렬의 계산 복잡도 O(n^2) 보다 낮다.그래서 정렬할 자료의 개수가 많을수록 병합 정렬이 선택, 삽입 정렬보다 훨씬 더 빠른 정렬 성능을 나타낸다.

 

<문제 52>

퀵 정렬(quick sort)을 빈칸을 채워 완성하는 문제이다.퀵 정렬은 그룹을 둘로 나눠 재귀 호출하는 방식으로 병합 정렬과 같지만,기준점을 미리 만들어서 기준점과 비교해서 나눈다는 점이 다르다.

퀵 정렬에서 좋은 기준을 정하는 것이 중요한데 좋은 기준을 정하는 방법이 어렵다고 한다.

그래서 문제에서는 간단하게 인덱스의 중간 지점을 기준점으로 잡은 것 같다.

v 리스트 내의 중간 지점인 170을 기준으로 잡은 다음에

170보다 작으면 group_one 리스트에, 크면 group_two 리스트에 append를 시켜준다.

return 값으로 재귀 호출을 시켜주면 그룹 1과 2 내에서 값들이 퀵 정렬로 정렬되고,

출력 값으로 기준점인 result를 포함해서 돌려준다.

문제 51번과 같은 리스트를 입력했기 때문에 출력 값은 동일하다.

 

참고로 퀵 정렬도 대부분의 경우 평균적으로 병합 정렬과 같은 계산 복잡도인 O(n ·logn)를 가진다.

 

이번 게시글은 정렬 문제를 묶어서 설명했다.

이어서 다음 문제부터 다음 게시글에 설명하도록 하겠다.

 

모두 수고하셨습니다 : )