병합정렬
재귀 용법을 사용한 알고리즘.
<원리>
1) 특정 리스트를 두개로 쪼갠다.
2) 쪼개진 각각의 리스트를 합병 정렬을 이용해 정렬시킨다.
3) 정렬된 리스트를 다시 합병 시킨다.
크게 2가지로 나눠보자.
첫번째, 리스트 쪼개기 함수 익히기
우선 리스트를 쪼개는 기본 원리를 익히기 위해
다음과 같이 medium이라는 리스트의 중간 지점을 찾고 해당 기준점을 기준으로 좌,우로 리스트를 쪼개는 원리를 익혀보자.
병합정렬 스타일의 리스트 쪼개기로 변환
병합정렬은 특정 리스트를 반으로 쪼개고 또다시 계속 쪼개면서 길이가 1개만 존재할 때 까지 지속적으로 쪼개는 것이 특징이다.
따라서 단발성으로 한 번만 쪼개는 것이 아니므로 재귀 용법을 적용시켜 1개만 남을 때 까지 쪼개줘야 한다.
다음과 같이 !
위에서 medium 포인트를 잡고 쪼갠 것은 동일하나 한 번만 쪼개고 말 것이 아니므로 남은 리스트를 같은 원리를 적용해 쪼개줄 터이니 mergetSplit 함수를 지속적으로 호출한다.
쪼개진 리스트 정렬 후, 합치기 !!
한 개가 남을 때 까지 왼쪽,오른쪽 리스트를 쪼개다 보면 왼쪽 리스트, 오른쪽 리스트 각각에는 길이가 1개씩만 존재하는 리스트 "몇"개가 존재할 것이다.
따라서 몇개의 리스트가 왼쪽과 오른쪽에 존재하는지 모르니
크게 경우의 수 3가지로 나눠 코드를 입력한다.
1) 왼쪽 오른쪽 동일한 개수의 리스트가 존재하는 경우
위와 같이 왼쪽 2개, 오른쪽 2개 인 경우
2) 왼쪽에만 존재하는 경우
3) 오른쪽에만 존재하는 경우
비교 원리는 다음과 같다.
0번 인덱스 (왼쪽part) 와 2번인덱스 (오른쪽 part) 를 비교 후
왼쪽 그러니깐 0번 인덱스가 더 작으면 빈 리스트에 append 시켜주고 왼쪽 입장에서는 하나 어펜드 시켰으니 다른 아이를 처리하기 위해 인덱스를 + 1 시켜주고 오른쪽은 처리한게 없으니 인덱스를 그대로 유지시킨다.
그러고 나서 1번 인덱스와 2번 인덱스를 비교하는데 여기서 2가지로 나뉜다.
왼쪽 인덱스가 이번에도 작으면 왼쪽 인덱스의 숫자를 append 시켜준다 그러면 위에서 언급한 3)의 경우 즉 오른쪽에만 존재하는 경우가 발생되니 남은 오른쪽 ( 이미 왼쪽보다 큰게 증명된 숫자들 ) 을 차례대로 append 시켜준다.
하지만 오른쪽 인덱스가 더 "작으면" 오른쪽 인덱스를 어펜드 시켜주고 오른쪽 리스트 인덱스를 +1 시키고 왼쪽 리스트와 비교하는 것이다.
핵심은 append가 되면 인덱스를 하나씩 올리면서 작은 값을 빈 리스트에 꾸겨 넣는 것이다.
따라서 위와 같이 쪼개진 리스트를 merge 할 것 이다.
파라미터로 쪼개진 왼쪽,오른쪽 리스트를 받고
merged = list() 로 빈 리스트 객체를 생성시킨다.
그리고 앞서 언급했다 시피 append가 되면 인덱스를 하나씩 올려줘야 하므로 왼쪽 오른쪽 파트마다 인덱스 포인트의 변수로 left,right_point를 0으로 설정한다.
그리고 나서 왼쪽 리스트의 길이가 인덱스 크고 오른쪽 리스트의 길이가 오른쪽 인덱스의 숫자보다 크다는 조건이 만족되면
앞서 말한 원리를 적용시켜 작은 값을 찾고 빈 리스트에 어펜드 시키고 인덱스를 하나씩 올리면 되는 것이다.
결과
