정렬

정렬 알고리즘은 데이터의 순서를 재배치하여 정렬된 순서로 데이터를 나열하는 알고리즘입니다.

 

데이터를 효율적으로 정렬하기 위해 사용되며, 다양한 종류의 정렬 알고리즘이 존재합니다. 문제의 크기, 데이터의 특성, 정렬의 안정성(stability), 메모리 사용량 등을 고려하여 적절한 정렬 알고리즘을 선택하는 것이 중요합니다.

 

• 버블 정렬 (Bubble Sort): 인접한 두 개의 요소를 비교, 시간 복잡도는 최악, 평균, 최선 모두 **O(n^2)**입니다.

버블 정렬

 

• 선택 정렬 (Selection Sort): 최솟값을 찾아 앞으로, 시간 복잡도는 최악, 평균, 최선 모두 **O(n^2)**입니다.

선택 정렬

 

• 삽입 정렬 (Insertion Sort): 정렬되지 않은 요소를 적절한 위치에 삽입, 시간 복잡도는 최악, 평균의 경우 O(n^2)이지만, 최선의 경우에는 O(n)입니다.

삽입 정렬

 

• 퀵 정렬 (Quick Sort): 리스트에서 하나의 요소를 **피벗(pivot)**으로 선택하고, 피벗보다 작은 요소는 피벗의 왼쪽으로, 큰 요소는 피벗의 오른쪽으로 분할하여 정렬합니다. 분할된 부분 리스트에 대해 재귀적으로 동일한 과정을 반복하며, 전체 리스트가 정렬되는 결과를 얻습니다. 평균적으로 빠른 속도를 가지며, **평균적으로 O(n log n)이며, 최악의 경우에는 O(n^2)**입니다. 최악의 경우는 피벗이 제일 처음이나 끝이거나 제일 작거나 크거나. 불안정 정렬(값이 같은 경우 순서 보장 안될수도)

퀵 정렬

 

• 병합 정렬 (Merge Sort): 리스트를 반으로 분할하고, 분할된 각 부분 리스트를 재귀적으로 정렬한 후 병합하여 정렬된 리스트를 생성합니다. 분할과 병합 과정을 반복하여 전체 리스트가 정렬되는 결과를 얻습니다. 시간 복잡도는 최악, 평균, 최선 모두 **O(nlogn)**입니다.