[항해99] 정렬 ( quick, merge)

Quick Sort? 

퀵소트는 기준(파티션) 을 정한 뒤정해진 기준보다 작으면 파티션의 왼쪽, 크면 오른쪽에 배치하고(분할)

파티션 기준 왼쪽과 오른쪽 배열을 다시 퀵소트를 해서(정복)

재귀적으로 정렬하는 정렬방식이다.

 

파티션과 원소들의 위치를 서로 왔다갔다 바꾸면서 정렬하기때문에, 원래 배열의 순서를 유지하지 못한다. 그래서 Unstable 정렬방식이다. 

 

파티션을 정하는 방법은 lomuto식이 있고 Hoare식이 있는데, 여기선 lomuto식을 이용했다. 

def quicksort(lst, start, end):
    def partition(part, ps, pe):
        pivot = part[pe]
        i = ps - 1
        for j in range(ps, pe):
            if part[j] <= pivot:
                i += 1
                part[i], part[j] = part[j], part[i]

        part[i + 1], part[pe] = part[pe], part[i + 1]
        return i + 1

    if start >= end:
        return None

    p = partition(lst, start, end)
    quicksort(lst, start, p - 1)
    quicksort(lst, p + 1, end)
    return lst


lst = list(map(int, input().split()))
for i in lst[::-1]:
    print(i)

Merge Sort?

Merge Sort는 한 정렬을 엄청나게 잘게 쪼갠 뒤(분할)

쪼개진 하나하나를 병합할 때 순서를 맞게 병합해서(정복)

구현하는 정렬방식이다. 

def merge(arr1, arr2):
    result = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[i]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result


def mergesort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    L = lst[:mid]
    R = lst[mid:]
    return merge(mergesort(L), mergesort(R))

Sort Colors

https://leetcode.com/problems/sort-colors/

Sort Colors - LeetCode

정렬 문제지만, 포인터 세개를 가지고 푸는 문제.

왼쪽을나타내는 left와 오른쪽을 나타내는 right를 가지고, 왼쪽에 0을 배치하고 left를 늘려주고, 오른쪽에 2를 배치하고 right를 줄여주는 식으로 현재 위치를 나타내는 count는 0과 1일때는 증가하고, 2일떄는 증가하지 않는다.

( 가져온 원소에 대한 판단을 안 했으니까 ) 

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        left = count = 0
        right = len(nums)-1
        while count <= right:
            if nums[count] == 2:
                nums[count], nums[right] = nums[right], nums[count]
                right -= 1
            elif nums[count] == 0:
                nums[count], nums[left] = nums[left], nums[count]
                left += 1
                count += 1
            else:
                count += 1

Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

Merge Two Sorted Lists - LeetCode

연결리스트를 병합하는 문제다.

연결리스트에 대한 이해와, 병합 정렬에 대한 이해가 둘 다 있어야 풀 만한 문제.

# Definition for singly-linked list.
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.head = None
        self.val = val
        self.next = next


class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        new_l= dummy = ListNode()
        while (list1 and list2):
            if list1.val < list2.val:
                new_l.next = list1
                list1 ,new_l = list1.next, list1
            else:
                new_l.next = list2
                list2, new_l = list2.next, list2
        
        if list1 or list2:  # 둘 중 하나는 남아있을거니까.
            new_l.next = list1 if list1 else list2
        return dummy.next

백준 1181 단어정렬

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

병합정렬의 추가문제로 나왔기에 파이썬 라이브러리로 풀어보고 병합정렬로 다시 풀어봤다.

병합 시 길이가 같은 원소에 대해서 판단을 해 주어야 한다.

# 라이브러리 사용
import sys

T = int(input())

lst = sys.stdin.readlines()
lst = list(set(lst))
lst.sort()
lst.sort(key=lambda x: len(x))

for i in lst:
    print(i.rstrip())

# 병합정렬


def merge(L, R):
    result = []
    i = j = 0
    while i < len(L) and j < len(R):
        # 길이가 다른 경우 or 길이가 같은 경우
        if len(L[i]) < len(R[j]) or (len(L[i]) == len(R[j]) and L[i] <= R[j]):
            result.append(L[i])
            i += 1
        elif len(R[j]) < len(L[i]) or (len(L[i]) == len(R[j]) and L[i] > R[j]):
            result.append(R[j])
            j += 1

    while i < len(L):
        result.append(L[i])
        i += 1
    while j < len(R):
        result.append(R[j])
        j += 1
    # 디버그용
    # print("L : ", L)
    # print("R : ", R)

    return result

def mergeSort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    L = lst[mid:]
    R = lst[:mid]
    return merge(mergeSort(L), mergeSort(R))


T = int(input())
lst = []

for i in range(T):
    lst.append(input())
lst = mergeSort(list(set(lst)))

for i in range(len(lst)):
    print(lst[i])

백준 10814 나이순 정렬

https://www.acmicpc.net/problem/10814

10814번: 나이순 정렬

힙소팅의 추가 문제로 나온 문제.

나이와 이름만 힙에 넣으면 될 거라고 생각했는데, 파이썬에서 힙큐는 받는원소가 리스트면 원소의 모든 값을 보고 배열한다.

# 예제입력
3
21 Junkyu
21 Dohyun
20 Sunyoung

예제 입력을 받은 그대로 힙소트로 넣는다면, 21살의 Junkyu 와 21살의 Dohyun의 위치는 Dohyun이 먼저 오기 때문에, 넣는 원소에 언제 넣었는 지를 나타내는 인덱스를 넣어줬다. 

import heapq

T = int(input())
heap = []

for idx in range(T):
    a, b = input().split()
    a = int(a)
    # heappush하니까 리스트를 넣으면 lst[0] lst[1] lst[2]에 대해서 heap이 넣음
    # 리스트의 모든 요소에 대해서 정렬된 힙이 만들어짐.
    # 그래서 idx를 넣어주면 넣은 순서대로 출력가능
    heapq.heappush(heap, [a, idx, b])

while heap:
    a = heapq.heappop(heap)

    print(a[0], a[2])

백준 11650 좌표 정렬하기

https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

퀵소트 하위 문제로 나와있어서, 퀵소트로 풀다가 왜 안될까 고민을 많이 한 문제이다.

퀵소트는 대표적인 Unstable 알고리즘인데, 그 말은 즉슨, 정렬후에 같은 값의 위치가 보장되지 않는 알고리즘이다. ( 같을 수도 있고 다를 수도 있다)

1 2 3 3 3 4 5 를 정렬한다하더라도 3에다가 꼬리표를 단다면 같은 위치로 보장되지 않는다.

 

처음에는 y좌표를 가지고 먼저 퀵소트 한 뒤에 x좌표를 가지고 퀵소트를 하면 x좌표가 증가하는 순으로, 만약 x좌표가 같다면 y좌표가 증가하는 순으로 출력 될 것이라 생각했지만, 퀵소트는 unstable알고리즘이라, x좌표를 가지고 두번째 퀵 소팅을 할 때 같은 x좌표지만 y좌표는 정렬되어있을 때 그 순서가 보장되지 않는다.

autoCP 실행결과

오류코드

def quicksort(lst, start, end, idx):

    def partition(part, ps, pe):
        pivot = part[pe][idx]
        i = ps - 1
        for j in range(ps, pe):
            if part[j][idx] <= pivot:
                i += 1
                part[i], part[j] = part[j], part[i]
        part[i + 1], part[pe] = part[pe], part[i + 1]

        return i + 1

    if start >= end:
        return None

    p = partition(lst, start, end)
    quicksort(lst, start, p - 1, idx)
    quicksort(lst, p + 1, end, idx)
    return lst


T = int(input())
lst = []
for _ in range(T):
    a, b = map(int, input().split())
    lst.append([a, b])

quicksort(lst, 0, len(lst)-1, 1)
quicksort(lst, 0, len(lst)-1, 0)
for i in lst:
    print(i[0], i[1])
    

 

sort()이용한 풀이

T = int(input())
lst = []
for _ in range(T):
    a, b = map(int,input().split())
    
    lst.append((a,b))
    
lst.sort(key= lambda x:x[1])
lst.sort()
for i in lst:
    print(i[0], i[1])

백준 2751 수 정렬하기

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

마찬가지로 퀵정렬 이용해봤는데 Recursion 에러 떠서 그냥 sort이용했다.

sort()만세

 

import sys

T = int(input())
lst = []
for i in range(T):
    lst.append(int(sys.stdin.readline().rstrip()))

lst.sort()
for i in range(T):
    print(lst[i])

 

오늘 회고

소팅 알고리즘 좀 어려운 개념을 접했는데, 소팅알고리즘 자체는 면접에서 구현 물어보는 식으로 많이들 물어본다고 한다. 

 

문제에 직접 적용해서 푼다기 보단, 어떻게 작동하는지를 잘 알아두도록 하자 .

 

and I also sort() 좋아.