[ICPC-신촌] Ch.03 Sorting

mrnglory·2020년 8월 8일
0

ICPC-신촌

목록 보기
3/5

01. STL 정렬

정렬이란?
데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일

정렬시간복잡도
정렬의 구현 방법마다 다르지만, C++과 파이썬에서 제공하는 기본 정렬O(nlog(n))O(nlog(n))을 보장한다.


Q. 기본값이 오름차순이구나, 그렇다면 내림차순은 어떻게 하지?
A. 내림차순으로 정렬하는 방법

1. 오름차순으로 정렬 후 반대로 뒤집기
2. 처음부터 내림차순으로 정렬
3. 오름차순으로 정렬 후 역순으로 출력하기 (꼼수)
4. 부호 뒤집어 입력 받고 정렬, 부호 뒤집어 출력 (꼼수)

미리요약 (C++)

  • algorithm 헤더의 sort를 이용하면 O(nlog(n))O(nlog(n)) 정렬을 할 수 있다.
  • 원하는 순서대로 정렬을 하고 싶다면 비교 함수를 작성하거나 lambda를 이용한다.
  • sortstable이 보장되지 않으므로 stable이 필요하다면 index를 추가하거나 stable_sort()를 사용한다.

미리요약 (파이썬)

  • 리스트를 직접 정렬한다면 sort를 이용한다.
  • sorted는 리스트, 딕셔너리, 튜플, 문자열 등을 정렬하여 새로운 리스트를 만든다.
  • sort, sorted 둘 다 시간복잡도는 O(nlog(n))O(nlog(n))이다.
  • 원하는 순서대로 정렬을 하고 싶다면 key 옵션에서 lambda를 이용한다.
  • sortstable이 보장된다.

02. 정렬의 종류 및 특징

C++, 파이썬에서 제공하는 정렬 기능을 사용해보았다. 정렬의 기본적인 구현 방법들에는 무엇이 있을까?

2.1 Bubble Sort

O(n2)O(n^2) | 가장 간단한 정렬 방법

2.2 Insertion Sort

O(n2)O(n^2) | n2n^2 중에서 그나마 빠름

2.3 Quick Sort

O(n2)O(n^2) | 최악의 경우는 O(n2)O(n^2), 하지만 평균은 가장 빠른 O(nlog(n))O(nlog(n))

2.4 Merge Sort

O(nlog(n))O(nlog(n)) | 분할 정복의 좋은 예시. 메모리는 눈물.

2.5 Heap Sort

O(nlog(n))O(nlog(n)) | Max Heap 또는 Min Heap 자료구조를 이용한 정렬

  Heap SortBuild Heap은 왜 O(n)O(n)인가?


그래서 우리가 쓰고 있는 sort는 무엇인가?

  • C++ sort
Intro Sort: Insertion Sort + Quick Sort + Heap Sort
if n <= 16 Insertion Sort;
else Quick Sort;

하지만 만약 재귀 깊이가 2log(n)2log(n)보다 크고 해당 영역이 1616 초과라면 Heap Sort - not stable


  • 파이썬 sort
Tim Sort: Merge Sort + Insertion Sort
이미 정렬된 데이터 영역 run들을 확보한다.
너무 작은 크기의 run은 Insertion Sort로 정렬하여 더 크게 묶는다.
확보한 run들을 Merge Sort 한다.

2.6 다루지 않았지만 알아보면 재밌는 정렬들

2.6.1 Selection Sort

2.6.2 Radix Sort

2.6.3 Counting Sort


03. BOJ - 관련 문제

3.1 [2750] 수 정렬하기

# list.sort(): 리스트 내에서 직접 수정
import sys
input = sys.stdin.readline

n = int(input())
arr = []

for i in range(n):
	arr.append(int(input())
arr.sort()

for i in arr:
	print(i)
# sorted(list): 리스트 외부에서 정렬함. 즉, 새로운 정렬 리스트를 생성함.
import sys
input = sys.stdin.readline

n = int(input())
arr = []

for i in range(n):
	arr.append(int(input())

print("\n".join(map(str, sorted(arr))))
# 혹은 print(*sorted(arr))
# 한 줄로도 가능
print(*sorted([int(input()) for _ in range(int(input()))]))

3.2 [11931] 수 정렬하기 4

# reverse 옵션
import sys
input = sys.stdin.readline

n = int(input())
arr = []

for i in range(n):
	arr.append(int(input())
    
print(*sorted(arr, reverse = True))
# key 옵션 + lambda
import sys
imort functools
input = sys.stdin.readline

n = int(input())
arr = []

for i in range(n):
	arr.append(int(input())
    
print(*sorted(arr, key = lambda x:(-x)))

3.3 [10825] 국영수

import sys
input = sys.stdin.readline

n = int(input())
arr = []

for i in range(n):
	n, k, e, m = input().split()
    arr.append([n, int(k), int(e), int(m)])
    
arr.sort(key = lambda x:(-x[1], x[2], -x[3], x[0]))

for i in arr:
	print(i[0])

3.4 [10814] 나이순 정렬

 key가 같은 원소들이 정렬 후에도 입력된 순서를 유지하는 것을 stable 하다고 일컫는다. 이 문제는 stable정렬을 요구하고 있으며, stable의 여부는 정렬 구현 방법에 따라 다르다.

  • C++STL 정렬stable이 보장되지 않는다. 그렇다면 어떻게 stable하게 정렬할 수 있을까?
1. index도 원소로 추가한다.
2. stable_sort()를 사용한다.
  • 파이썬의 정렬은 stable이 보장된다.
profile
espresso martini

0개의 댓글