python_day16_합병정렬, 랜덤합병정렬

*** 합병정렬

 

- 분할 정복기법

- 제자리 정렬이 가능하다.

 

 

-> divide함수를 이용해 주어진 리스트를 나누어준다.

-> // 연산을 이용해 나머지값을 버린 중앙값 mid를 구한다.

-> mid값을 기준으로 배열을 나눈다.

-> 리스트의 길이가 3개이상일 경우 다시 divide함수를 이용해 계속 나눈다.

-> 합병정렬을 이용해 left리스트, right리스트의 원소가 소모될때 까지 진행한다.

-> 0번째 인덱스를 비교한뒤 최소값은 nlists에 저장한뒤 remove를 이용해 지워준다.

-> nlists는 임시로 저장하는 곳이라고 생각하자 merge함수가 불러질때마다 []로 초기화되는것에 주의한다.

-> left와 right의 첫번째 원소들을 모두비교한뒤 한쪽 원소가 모두 비어지면 반대쪽 원소들을 nlists에 추가한다. 

 

# 결과

 

 

*** 합병정렬 랜덤

 

 

-> 랜덤합병정렬은 기존의 합병정렬에 random함수를 이용해 ulists를 랜덤으로 만드는 것이다.

-> 필요한 코드로는 import random을 이용해 random함수를 불러오고

-> random.shuffle(ulists)를 이용해 1부터100까지 순차적으로 작성된 리스트를 랜덤으로 섞는다.

 

# 결과