정렬

목차:

0. sort 활용

1. 병합

2. 퀵

 

백준 문제풀이: 단어정렬

https://bdbest.tistory.com/71?category=963504 

백준 문제풀이: 수의 정렬 1,2,3

https://bdbest.tistory.com/70?category=963504 

 

 

 

0. python sort 활용

sort 기초:

https://wikidocs.net/16041

 

두개 이상의 조건 sort:

https://hyun-am-coding.tistory.com/entry/key%EC%99%80-lambda%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EC%A0%95%EB%A0%AC

data = ["나라","가구","봄","가을","도토리","낫","혹","가을 아침","나는 밥을 먹고 있다."]
data.sort(key = lambda x:(len(x),x))
#글자 길이가 우선, 그리고 글자 길이가 같다면 가나다, abc 순으로 정렬
print(data)

 

 

 

 

1. 병합

설명:

https://stricky.tistory.com/184

https://ratsgo.github.io/data%20structure&algorithm/2017/10/03/mergesort/

def merge_sort(array):
    if len(array)<=1:
        return array
    
    # 재귀함수를 이용해서 끝까지 분할
    mid = len(array)//2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])

    i,j,k = 0,0,0

    # 분할된 배열끼리 비교
    while i<len(left) and j <len(right):
        if left[i]<right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k+=1
    
    # 먼저 끝났을 때 
    if i==len(left):
        while j < len(right):
            array[k] = right[j]
            j+=1
            k+=1
    elif j==len(right):
        while i < len(left):
            array[k] = left[i]
            i+=1
            k+=1
    return array

출처: https://assaeunji.github.io/python/2020-05-06-bj2751/

 

2. 퀵 정렬

from typing import MutableSequence


def qsort(a: MutableSequence, left: int, right: int) -> None:
    pl = left
    pr = right
    x = a[(left+right)//2]

    while pl <= pr:
        while a[pl] < x:
            pl += 1
        while a[pr] > x:
            pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1

    if left < pr:
        qsort(a, left, pr)
    if pl < right:
        qsort(a, pl, right)


def quick_sort(a: MutableSequence) -> None:
    qsort(a, 0, len(a)-1)


if __name__ == '__main__':
    num = int(input())  # 원소 숫자
    x = [None] * num

    for i in range(num):
        x[i] = int(input())

    quick_sort(x)

    for i in range(num):
        print(x[i])