버블 정렬, 선택 정렬, 삽입 정렬 비교

정렬 알고리즘의 Big O

알고리즘	시간 복잡도 (Best)	시간 복잡도 (Average)	시간 복잡도 (Worst)	공간 복잡도
버블 정렬	O(n)	O(n^2)	O(n^2)	O(1)
삽입 정렬	O(n)	O(n^2)	O(n^2)	O(1)
선택 정렬	O(n^2)	O(n^2)	O(n^2)	O(1)

 

보통 이 세 가지 정렬 알고리즘은 2차 정렬 알고리즘이라고 불립니다. 이는 시간 복잡도가 O(n^2) 이기 때문입니다.

 

버블 정렬, 삽입 정렬의 경우 정렬이 거의 다 되어있으면 시간 복잡도가 O(N) 입니다. (Best)
하지만 선택 정렬의 경우 최솟값을 찾기위해 끝까지 다 보기 때문에 모든 경우에서 O(n^2) 입니다. (Best)

 

요약

• 정렬은 기본입니다.
• 버블 정렬, 선택 정렬, 삽입 정렬은 모두 대략 비슷합니다.
• 모두 평균 시간 복잡도가 이차적입니다.
• 우리는 더 나은 방법을 찾을 수 있지만, 더 복잡한 알고리즘이 필요합니다.
• 데이터 셋이 매우 작을 때 효과적입니다.

 

결론

버블 정렬, 선택 정렬, 삽입 정렬은 모두 시간 복잡도가 O(n^2)인 기본적인 정렬 알고리즘입니다. 작은 데이터 셋에서는 효과적이지만, 큰 데이터 셋에서는 비효율적일 수 있습니다. 따라서 더 나은 성능을 위해서는 퀵 정렬, 병합 정렬 등의 복잡한 알고리즘을 고려해야 합니다. 이 글에서는 세 가지 기본 정렬 알고리즘의 작동 방식과 시간 복잡도를 비교하여 정리했습니다.