CHAPTER 6. 정렬

CHAPTER 6. 정렬

데이터를 특정한 기준에 따라 순서대로 나열하는 것

일반적으로 문제 상황에 따라서 적절한 알고리즘이 공식처럼 사용된다.

ex) 데이터의 개수가 적을 때, 데이터 개수가 많더라도 데이터 범위가 한정적일 때, 이미 정렬되어 있는 경우 등...

사람은 직관적으로 데이터를 파악하고 계산할 수 있지만 컴퓨터는 정렬을 어떻게 수행할지 알고리즘을 구체적으로 명시해야한다.

1. 선택정렬
2. 삽입정렬
3. 합병정렬
4. 퀵정렬
5. 계수정렬

 

	Best	Avg	Worst	Stable	In-Place
삽입 정렬(Insertion Sort)	N	N²	N²	O	O
거품 정렬(Bubble Sort)	N²	N²	N²	O	O
선택 정렬(Selection Sort)	N²	N²	N²	X	O
퀵 정렬(Quick Sort)	NlogN	NlogN	N²	X	O
합병 정렬(Merge Sort)	NlogN	NlogN	NlogN	O	X
힙 정렬(Heap Sort)	NlogN	NlogN	NlogN	X	O
계수정렬(Counting Sort)	N	N	N	O	X
기수 정렬 (Radix Sort)	N	N	N	O	X

 

 

---