220318_TIL

퀵 정렬

퀵 정렬이란 기준점 (pivot)을 정하여 기준점보다 작은 데이터는 왼쪽 , 큰 데이터는 오른쪽으로 모으는 것을 반복하여 정렬하는 정렬 방식이다. 함수는 왼쪽 + 기준점 + 오른쪽 리스트를 합쳐서 리턴한다.

• 알고리즘 구현

1. 리스트 갯수가 한개이면 해당 리스트를 리턴함
2. 리스트 갯수가 한개 이상이면 리스트의 맨 앞의 데이터를 기준점(pivot)으로 놓기
3. left와 right 리스트 변수를 만든다
4. 맨 앞의 데이터를 뺀 나머지 데이터를 기준점과 비교하고 피봇보다 작으면 left.append , 피봇보다 크면 right.append
5. return 값은 함수(left) + pivot + 함수(right)로 재귀 호출

import random

def qsort(data):
	if len(data) <= 1 :
		return data

	left, right = list(), list()
	pivot = data[0]
	
	for index in range(1, len(data)):
		if pivot > data[index]:
			left.append(data[index])
		else:
			right.append(data[index])
	return qsort(left) + [pivot] + qsort(right)
	
data_list = random.sample(range(100),10)

qsort(data_list)

100까지의 수 중에서 10개를 랜덤하게 뽑아 정렬되었다.

더 간결한 코드는 list comprehension을 사용하면 된다.

def qsort(data):
	if len(data) <= 1:
		return data

	pivot = data[0]
	
	left = [ item for item in data[1:] if pivot > item ]
	right = [ item for item in data[1:] if pivot <= item ]

	return qsort(left) + [pivot] + qsort(right)

이 알고리즘의 시간복잡도는 O(n log n) 이다.

병합 정렬

병합 정렬은 재귀용법을 활용한 정렬 알고리즘으로 리스트가 있을 때 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나누고 각 부분 리스트를 재귀함수를 이용해 합병 정렬을 하는 알고리즘이다. 그래서 split 하는 함수와 merge하는 함수 두개가 필요하다.

1. mergesplit 함수

   리스트 갯수가 한개이면 값 리턴하고 그렇지 않으면 리스트를 두개로 나눈다.

   left = mergesplit(앞), right = mergesplit(뒤)

   return merge(left, right)

2. merge 함수

   sorted라는 리스트 변수를 하나 만들고 left_index와 right_index를 0으로 둔다.

   왼쪽 리스트와 오른쪽 리스트를 비교하면서 작은 값들을 sorted에 저장하고 해당 인덱스를 1씩 증가시킨다. 끝까지 순회하면 정렬이 끝난다.

• 최종 코드

import random

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    # case1 - left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    # case2 - left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    # case3 - right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged

def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

data_list = random.sample(range(100), 10)
mergesplit(data_list)

병합 정렬 알고리즘의 시간 복잡도는 O(n log n)이다.

백준 알고리즘 - 수 정렬하기2

병합 정렬을 이용하여 푸는 문제였다. 오늘 배운 병합정렬이 실제 문제에서 어떻게 활용되는지 배웠다. 핵심은 left와 right로 리스트를 slicing하고 각 리스트의 인덱스를 0으로 놓아 비교한 후에 인덱스 값을 증가시키면서 정렬하는 것이었다. 그런데 실제 코테에서는 파이썬 라이브러리에 있는 sorted() 이용하면 7줄이면 끝나더라 ㅎㅎ