모두의 알고리즘 문제 10. 병합 정렬 연습 문제

10-1 교재의 병합정렬은 오름차순인데 이를 내림차순으로 바꾸려면 어디를 바꿔야할까?

 

def merge_sort(a): #리스트a를 입력으로 받음
  n=len(a)

  if n<=1:  #재귀함수를 위한 종료조건. 
    return a   #정렬할 리스트의 자료 개수가 한 개 이하면 정렬할 필요 없음
    
  #그룹을 나누어 각각 병합정렬을 호출
  mid=n//2   # 중간을 기준으로 두 그룹을 나눔
  g1 = a[:mid]
  g2 = a[mid:]
  merge_sort(g1) #재귀호출로 두 그룹을 정렬
  merge_sort(g2)
  #두 그룹을 하나로 병합
  i1=0  # g1의 원소 번호
  i2=0  # g2의 원소 번호
  ia=0  # 입력받은 리스트a의 원소번호

  while i1 < len(g1) and i2 < len(g2):  # 두 그룹 중 한 그룹이라도 자료가 남아있으면 실행
    if g1[i1] > g2[i2]:  # g1의 원소가 더 크면
      a[ia] = g1[i1]  #리스트a에 g1의 원소를 덮어씌움
      i1 += 1  #g1 원소번호 1 증가
      ia += 1  #리스트a 원소번호 1 증가
    else:
      a[ia] = g2[i2]  #리스트a에 g2의 원소를 덮어씌움
      i2 += 1  #g2원소번호 1 증가
      ia += 1  #리스트a 원소번호 1 증가

  # 두 리스트 중 아직 자료가 남은 리스트의 자료를 결과에 추가
  while i1 < len(g1):
    a[ia] = g1[i1]
    i1 += 1
    ia += 1
  while i2 < len(g2):
    a[ia] = g2[i2]
    i2 += 1
    ia += 1


d = [6, 8, 3, 2, 1, 9, 4, 5, 10, 7]
merge_sort(d)
print(d)

위 코드의 첫번째 while문의 if문은 교재에선 'if g1[i1] < g2[i2]: '이지만 이를 등호만 바꿔서 'if g1[i1] > g2[i2]: '이렇게 작성하면 내림차순으로 변한다.

 

위 코드의 결과는 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 이다.