🧚‍♂️알고리즘🧚‍♂️ - 정렬 - 병합 정렬

병합 정렬

분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘.

그룹 병합하는 방법 -> 투 포인터를 사용하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 한 칸 이동시키며 병합

---

실버 5

2751번 수 정렬하기2

2751번: 수 정렬하기 2

재귀함수!!!

from sys import stdin

def mergeSort(Nlist):
  if len(Nlist)<=1: #재귀함수 끝 
    return Nlist
    
  mid = len(Nlist)//2

  #left는 Nlist리스트의 인덱스 0부터 mid전까지
  left = mergeSort(Nlist[:mid]) #정렬된 덩어리들 저장됨

  #right은 array리스트의 인덱스 mid부터 끝까지
  right = mergeSort(Nlist[mid:])

  i, j = 0, 0 #투 포인터
  temp = []
  
  # 정렬하는 부분 
  while i < len(left) and j < len(right): 
    if left[i] < right[j]:
      temp.append(left[i])
      i+=1
    else:
      temp.append(right[j])
      j+=1

#while문 빠져 나온 후, left혹은 right에 남은 요소들 temp에 넣어주기
  temp += left[i:] 
  temp += right[j:]
 
  return temp

N = int(stdin.readline())
Nlist = list()

for _ in range(N):
  Nlist.append(int(stdin.readline()))

Nlist = mergeSort(Nlist)

for i in Nlist:
  print(i)

정렬시킨(재귀) 두 덩어리 투 포인터 이용해서 정렬하기

포인터 값 비교해서 작은 것 새로 만든 리스트에 넣기

---

플래티넘 5

1517번 버블 소트

1517번: 버블 소트

버블버블 정렬을 그대로 할 시 시간초과 발생

병합 정렬에서 병합하는 과정 중 데이터가 앞으로 이동하면 swap 이 일어난 것과 같다는 것을 이용

글로벌 변수! global