[Java] 정렬 알고리즘(Sorting Algorithm)

정렬 알고리즘이란 원소를 번호순이나 사전순과 같이 일정한 순서로 열거하는 알고리즘을 말한다.

정렬 알고리즘의 종류는 여러가지가 있다.

적합할 알고리즘을 선택할때는 정렬해야하는 데이터의 양, 메모리, 안정성, 시간복잡도 등을 고려해야한다.

 

데이터의 정렬은 추후 데이터 검색과 활용, 정규화등에 유용하게 쓰일 수 있다.

 

그 중 대표적인  알고리즘인 병합정렬, 퀵정렬, 삽입정렬, 힙정렬, 버블정렬, 계수정렬, 기수정렬에 대해 하나씩 정리해보고자 한다.

구분	이름	최선	평균	최악	메모리	안정성	방식
비교 정렬	병합정렬	n log n	n log n	n log n	n	Y	합병
	퀵정렬	n log n	n log n	n^2	log n(average), n(worst)	N	파티셔닝
	삽입정렬	n	n^2	n^2	1	Y	삽입
	힙정렬	n, n log n (모든 키 구분될때)	n log n	n log n	1	N	선택
	버블정렬	n	n^2	n^2	1	Y	교환
비교가 아닌 정렬*	계수정렬	-	n + r	n + r	n + r	Y	-
	기수정렬	-	n * (k / d)	n * (k / d)	n + 2^d	Y	-

* n(항목 수), k(키의 크기), r(정렬될 수의 범위)

 

참고자료

정렬 알고리즘 정리

정렬 알고리즘의 선택과 종류 7가지

Data Structure Visualizations