정렬 알고리즘

정렬이란?

데이터를 기준에 맞춰 나열하는 것

정렬의 종류

버블 정렬
인접한 두 요소를 비교하여 필요하면 위치를 바꾸는 방식
큰 요소를 점차 끝으로 보내며 정렬한다.

시간 복잡도는 O(N^2)로, 효율성이 낮아 소규모 데이터 정렬에 적합하다.

선택정렬(selection sort)

전체 배열에서 가장 작은 값을 찾아 맨 앞의 요소와 교환하는 방식

시간 복잡도는 O(n^2)로, 데이터가 많을수록 비효율적이다.

삽입 정렬(Insertion sort)
배열의 첫 번째 요소를 기준으로 다음 요소를 적절한 위치에 삽입해가며 정렬하는 방식
시간 복잡도는 O(n^2)이지만, 거의 정렬된 데이터에서는 빠르게 동작하여 효율적이다.

퀵 정렬(Quick Sort)
피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 재귀적으로 정렬하는 방식
평균 시간 복잡도는 O(nlogn)이며, 속도가 빨라 큰 데이터를 다룰 때 유용하다.

병합 정렬(Merge Sort)
배열을 반으로 나누어 각각을 정렬한 후 다시 합병하는 방식
시간 복잡도는 항상 O(nlogn)으로 안정적이고 데이터 크기에 상관없이 일정한 성능을 보장한다.

힙 정렬(Heap Sort)
최대 힙이나 최소 힙을 이용해 정렬하는 방식으로 힙을 이용해 최댓값(또는 최솟값)을 선택적으로 정렬한다.
시간 복잡도는 O(nlogn)으로 메모리 효율성이 높아 큰 데이터에서 안정적이다