https://github.com/kimdonwon/Algorithm
삽입정렬
시간 복잡도 n*n
n*n 정렬준 가장 효율이 좋음
정렬이 어느정도 되어있는 상태는 삽입 정렬이 가장 빠름
퀵 정렬
시간 복잡도 n*logn정렬 중에 평균적으로 가장 빠름 (logn은 거의 상수)
이미 정렬이 된 배열은 최악의 경우 n^2이 나옴
정렬이 어느정도 되어있으면 삽입 정렬이 더 빠름
-> 그냥 sort함수가 제일 빠름
1. 첫번 째 값을 기준으로 정함
2. 기준보다 큰 값을 왼쪽에서부터 찾음
3. 기준보다 작은 값을 오른쪽에서부터 찾음
4. 찾은 값들이 엇갈리지 않았으면 값 끼리 바꿈
5. 엇갈렸으면 작은값과 기준을 바꿈
6. 기준으로 왼쪽은 작은값 오른쪽은 큰값으로 정렬됨
7. 기준으로 왼쪽과 오른쪽을 다시 퀵 정렬
합병 정렬
시간 복잡도 n*logn 을 보장함
일단 반으로 쪼개고 나중에 합침
1. 배열의 요소가 1개가 될 때까지 반으로 계속 쪼갬
2. 배열의 두 덩어리를 비교하고 합침
3. 반복
힙 정렬
시간 복잡도 n*logn을 보장함
1. 힙 구조로 만든 후 첫번째 값과 마지막 값을 바꿈
2. 반복
힙 - 완전 이진트리에서 최대힙, 최소힙을 적용한 것
최대힙 - 부모가 자식보다 큼
최소힙 - 부모가 자식보다 작음
힙 생성 알고리즘 - 힙을 만들어줌, 전체에 절반만 확인하면 됨, logn
