알고리즘 문제풀이/알고리즘
정렬 알고리즘 종류 정리
이제ise이제
2023. 12. 27. 12:52
참고자료
블로그
정렬 알고리즘의 종류
1번째부터 끝까지 훑어서 가장 작은 게 1번째, 2번째부터 끝까지 훑어서 가장 작은 게 2번째... 정렬이 끝날 때까지 반복한다. 이미 정렬되어 있는 자료구조에 삽입/제거 할 때나 배열이 작은 경우
velog.io
강좌
https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비 강의 - 인프런
C/C++ 프로그래밍 언어로 알고리즘 테스트를 준비하는 분들을 위한 강의입니다. 알고리즘 및 자료구조를 이용한 문제 해결력을 기르는 게 이번 강의의 목적입니다., IT기업 채용 코딩테스트도 자
www.inflearn.com
위키
https://en.wikipedia.org/wiki/Sorting_algorithm
Sorting algorithm - Wikipedia
From Wikipedia, the free encyclopedia Algorithm that arranges lists in order Merge sort In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicograph
en.wikipedia.org
| 종료 | 구분 | 시간복잡도 | 공간복잡도 | 안정도 | ||
| 최악 | 평균 | 최선 | ||||
| 선택 정렬 (selection) |
선택 | 비교: $ O\left ( N^{2} \right ) $ 교환: $ O\left ( N \right ) $ |
비교: $ O\left ( N^{2} \right ) $ 교환: $ O\left ( N \right ) $ |
비교: $ O\left ( N^{2} \right ) $ 교환: $ O\left ( N \right ) $ |
예비: $ O\left ( 1 \right ) $ | x |
| 삽입 정렬 (insertion) |
삽입 | 비교/교환: $ O\left ( N^{2} \right ) $ |
비교/교환: $ O\left ( N^{2} \right ) $ |
비교: $ O\left ( N \right ) $ 교환: $ O\left ( 1 \right ) $ |
전체: $ O\left ( N \right ) $ 보조: $ O\left ( 1 \right ) $ |
O |
| 버블 정렬 (bubble) |
교환 | 비교/교환: $ O\left ( N^{2} \right ) $ |
비교/교환: $ O\left ( N^{2} \right ) $ |
비교: $ O\left ( N \right ) $ 교환: $ O\left ( 1 \right ) $ |
보조: $ O\left ( 1 \right ) $ | O |
| 병합 정렬 (merge) |
합병 | $ O\left ( NlogN \right ) $ | $ O\left ( NlogN \right ) $ | $ O\left ( NlogN \right ) $ | $ O\left ( N \right ) $ | O |
| 힙 정렬 (heap) |
선택 | $ O\left ( NlogN \right ) $ | $ O\left ( NlogN \right ) $ | $ O\left ( NlogN \right ) $ | $ O\left ( 1 \right ) $ | x |
| 퀵 정렬 (quick) |
파티셔닝 | $ O\left ( N^{2} \right ) $ | $ O\left ( NlogN \right ) $ | $ O\left ( NlogN \right ) $ | 평균: $ O\left ( logN \right ) $ 최악: $ O\left ( N \right ) $ |
안정판이 존재하지만, x |