정렬 알고리즘의 시간 복잡도와 기수 정렬

1. 버블 정렬 (Bubble Sort)

• 사용 방법: 인접한 두 원소를 비교하여 필요 시 교환합니다. 이 과정을 리스트가 정렬될 때까지 반복한다.
• 시간 복잡도: O(n^2)

 

2. 선택 정렬 (Selection Sort)

• 사용 방법: 리스트에서 가장 작은 원소를 찾아 첫 번째 원소와 교환하고, 그 다음 작은 원소를 찾아 두 번째 원소와 교환하는 방식으로 반복한다.
• 시간 복잡도: O(n^2)

 

3. 삽입 정렬 (Insertion Sort)

• 사용 방법: 리스트의 두 번째 원소부터 시작하여, 앞의 원소들과 비교해 적절한 위치에 삽입합니다. 이 과정을 리스트의 끝까지 반복한다.
• 시간 복잡도: O(n^2)

 

4. 합병 정렬 (Merge Sort)

• 사용 방법: 리스트를 반으로 나눈 후 각각을 재귀적으로 정렬하고, 두 정렬된 리스트를 합병한다.
• 시간 복잡도: O(n log n)

 

5. 퀵 정렬 (Quick Sort)

• 사용 방법: 리스트에서 피벗을 선택하고, 피벗보다 작은 원소들과 큰 원소들로 분할한다. 각 부분 리스트를 재귀적으로 정렬한다.
• 시간 복잡도: 평균 O(n log n), 최악 O(n^2)

 

6. 힙 정렬 (Heap Sort)

• 사용 방법: 리스트를 최대 힙으로 만들고, 루트 원소를 제거하여 정렬된 부분에 추가한다. 이 과정을 반복한다.
• 시간 복잡도: O(n log n)

 

7. 기수 정렬 (Radix Sort)

• 사용 방법: 정렬할 리스트의 각 자릿수를 기준으로 정렬한다. 자릿수 별로 정렬을 반복한다.
• 시간 복잡도: O(d(n + k)), 여기서 d는 자릿수의 개수, k는 기수(base)

 

 

 

 

1초의 시간 제한이 있다고 하고 1초에 실행할 수 있는 연산 횟수가 약 1억번이라고 할 때, 

 

데이터의 개수(n)이 2000 이면 시간복잡도가 O(n^2)인 버블정렬, 선택정렬, 삽입정렬을 써도 된다.

 

데이터의 개수(n)이 100,000이면 최대 시간복잡도가 O(nlogn)이 되도록 해야 한다. 힙 정렬, 퀵 정렬, 합병 정렬을 사용할 수 있다.