[정렬] 합병정렬 / 퀵 정렬

합병정렬

1) 최소 단위로 나누는 과정 (>mergesort)
2) 합병 과정 필요함 (>merging)

import sys
def merging(left, right):
  result = []
  while left and right:
    if left[0]<=right[0]:
      result.append(left.pop(0))
    else:
      result.append(right.pop(0))
  while left:
    result.append(left.pop(0))
  while right:
    result.append(right.pop(0))
  return result
  
def mergeSort(arr):
  n = len(arr)
  if n<=1:
    return arr
  mid = n//2
  l = mergeSort(arr[:mid])
  r = mergeSort(arr[mid:])
  return merging(l,r)
  
if __name__=='__main__':
  n = int(sys.stdin.readline())
  numbers = list(map(int, sys.stdin.readline().split()))
  sortedList = mergeSort(numbers)
  for i in sortedList:
    print(i, end = ' ')
    

퀵 정렬

1) pivot을 기준으로하여 정렬
2) pivot을 따로 빼두고, Left, right로 나눈 다음 left 값이 pivot보다 작을때까지 Left+=1
3) right값이 pivot값보다 클때까지 right-=1
4) left, right가 크로스된 경우 -> pivot값 교환
5) 엇갈리지 않으면 right, left 값 교체

import sys
def quickSort(arr,s,e):
  if s>=e:
    return
  pivot = s
  left = s+1
  right = e
  while left<=right:
    while left<=e and arr[left]<=arr[pivot]:
      left+=1
    while right>s and arr[right]>=arr[pivot]:
      right-=1
    if left>right:
      arr[right], arr[pivot] = arr[pivot], arr[right]
    else:
      arr[right], arr[left] = arr[left], arr[right]
  quickSort(arr,s,right-1)
  quickSort(arr,right+1,e)

if __name__=='__main__':
  n = int(sys.stdin.readline())
  numbers = list(map(int, sys.stdin.readline().split()))
  quickSort(numbers, 0,n-1)
  for i in numbers:
    print(i, end = ' ')