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

퀵 정렬

기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘

시간복잡도 O(NlogN)

---

실버 5

11004번 K번째 수

11004번: K번째 수

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
arr = list(map(int,input().split()))

def merge_sort(arr):

    if len(arr) <= 1: 
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    i,j,k = 0,0,0

    while i < len(left) and j < len(right):

        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1

        else:
            arr[k] = right[j]
            j += 1
        
        k += 1

    if i == len(left):
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

    elif j == len(right):
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
            
    return arr

arr = merge_sort(arr)

print(arr[K-1])

---

병합 정렬

데이터를 분할하고 분할한 집합을 정렬하며 합친다.

병합 원리 --> 투 포인터 이용 / 각 묶음의 앞을 가르키는 두 포인터에서 작은 값을 가져옴

재귀 함수 형태로 구현

시간복잡도 O(NlogN)

---

실버 5

2751번

2751번: 수 정렬하기 2

from sys import stdin
N = int(stdin.readline())
Nlist = [0]
for i in range(N):
    Nlist.append(int(stdin.readline()))
Mlist = [0]*(N+1)

def Mergesort(s, e): # 병합 정렬 / 오름차순
    if s == e: #가장 작은 덩어리부터 정렬시작
        return
    m = (s+e)//2
    Mergesort(s, m) # 두 덩어리로 나누기 / 재귀함수
    Mergesort(m+1, e)  
    for i in range(s, e+1): # 임시 리스트에 복사 / A가 정렬되는 리스트
        Mlist[i] = Nlist[i]

    #본정렬
    r = s # r은 정렬된 리스트의 인덱스
    point1 = s
    point2 = m+1
    while point1 <= m and point2 <= e: # 두 묶음 중 하나가 끝날때까지
        if Mlist[point1] < Mlist[point2]:
            Nlist[r] = Mlist[point1]
            point1 += 1
        else:
            Nlist[r] = Mlist[point2]
            point2 += 1
        r += 1

    while point1 <= m: # point1이 끝까지 못 갔다면
        Nlist[r] = Mlist[point1]
        point1 += 1
        r += 1
    while point2 <= e: # point2가 끝까지 못 갔다면
        Nlist[r] = Mlist[point2]
        point2 += 1
        r += 1


Mergesort(1,N)

for i in range(1,N+1):
    print(Nlist[i])