[알고리즘] 정렬 (버블, 선택, 삽입, 힙, 퀵, 트리, 병합, 하이브리드, 팀, 인트로)

유니·2022년 5월 22일
0

알고리즘

목록 보기
2/3

시간복잡도에 따른 정렬분류

O(n²)

  • 버블정렬(bubble sort)
    버블정렬
    인접한 인덱스끼리 비교하며 swap하여 큰 값부터 뒤로 쌓는다.

  • 선택정렬(selection sort)
    선택정렬
    남은 값 중에서 가장 작은 값을 탐색하여 앞으로 쌓는다.

  • 삽입정렬(insert sort)
    삽입정렬
    모든 요소를 앞부분에 이미 정렬된 배열부분과 비교하여 자신의 위치를 찾아 삽입한다.

O(nlogn)

  • 퀵정렬(quick sort)
    퀵정렬
    1️⃣pivot을 기준으로 pivot보다 작은 데이터와 pivot보다 큰 데이터로 구분하고 그 사이에 pivot을 위치시킨다.
    2️⃣pivot보다 작은 부분 / pivot보다 큰 부분에서 각각 재귀적으로 1️⃣을 다시 수행한다.

  • 힙정렬(heap sort)
    힙정렬
    힙 자료구조로 만들고 최상위 노드를 하나씩 뺀다.

  • 트리정렬(tree sort)
    트리정렬
    이진 탐색 트리(left child < parent < right child 로 정렬된 트리) 구조로 만들고
    left child - parent - right child 순으로 순회한다. (=중위순회, LVR순회)

  • 병합정렬
    병합정렬
    다 쪼갬 - 쪼갠애들중에 제일 앞 인덱스끼리 정렬하면서 병합

하이브리드 정렬(두가지 이상의 정렬을 쓰까놓은 것)

  • 팀정렬(tim sort)
    병합정렬 + 삽입정렬

    Q.삽입정렬은 O(n²)인데 섞으면 더 구려지는거 아닌가?
    삽입정렬은 인접한 메모리와의 비교를 반복하기에 참조 지역성의 원리를 잘 만족하므로 전체를 작은 덩어리로 잘라 각각을 삽입정렬한 뒤 병합정렬하면 빠르다고 한다.

  • 인트로정렬(intro sort)
    퀵정렬 + 힙정렬

정렬 특징 요약

요약

Q. 안정, 불안정?
같은 값을 정렬하는 경우 처음의 순서를 보장하는 정렬을 안정(stable)하다고 한다.

Q. tim sort는 안정할까 불안정할까?
tim sort는 병합(stable) + 삽입(stable) 이므로 역시 안정(stable)하다.

Q. O(nlogn)인 힙정렬이 O(nlogn ~ n²)인 퀵정렬보다 빠를까?
일반적으로 퀵정렬이 더 빠른데 그 이유
1. 퀵정렬은 평균 O(nlogn) 정렬중에 상수값이 가장 작다.
2. 힙 구조보다 배열구조가 원소끼리 인접 해 있기때문에 메모리상에서 참조하는 시간이 적게 든다.
3. 퀵정렬에서 pivot 선택 전략에서 어느정도의 휴리스틱을 가미하여 최악의 경우를 피할 수 있다.

내가 쓰는 언어의 빌트인 정렬은?

정렬언어
tim sortpython, Java SE 7, Android, Google chrome(v8), switft
intro sortC++(표준은 아님), C#
브라우저 엔진마다 다름js

Q. 보통 내장 sort 쓰니까 정렬을 직접 구현하라고 하진 않을텐데... 각 정렬마다 원리를 알 필요가 있을까 ??
정렬 알고리즘에서 사용되는 테크닉이 다른 문제 풀이에 응용될 수 있다. ex) 분할정복

사용자 정의 정렬

파이썬

  • lambda 표현식 사용
array.sort(key=lambda x : x[0]) # 첫번째 요소를 기준으로 내림차순 정렬
array.sort(key=lambda x : -x[1]) # 두번째 요소를 기준으로 오름차순 정렬
array.sort(key=lambda x : (x[0], x[1])) # 첫번째 요소를 기준으로 내림차순 정렬하고, 같은 겨우 두번째 요소로 내림차순 정렬
array.sort(key=lambda x : -sum([i for i,j in x])) # 원소 내의 첫번째 요소들의 합을 기준으로 오름차순 정렬
  • cmp_to_key 함수 사용
from functools import cmp_to_key

def compare(a, b):
	return a - b # 양수일때 swap

array.sort(key=cmp_to_key(compare))

자바스크립트

  • compare 함수 정의하여 사용
funtion compare(a,b){
	return a - b
}
array.sort(compare)
profile
추진력을 얻는 중

0개의 댓글