[알고리즘] 정렬 | 정렬의 시간 복잡도 - Python

[알고리즘] 정렬 | [1] 정렬, 선택 정렬 (Selection Sort) - Python

[알고리즘] 정렬 | [1] 정렬, 선택 정렬 (Selection Sort) - Python

[알고리즘] 정렬 | [2] 삽입 정렬 (Insertion Sort) - Python

[알고리즘] 정렬 | [2] 삽입 정렬 (Insertion Sort) - Python

[알고리즘] 정렬 | [3] 퀵 정렬 (Quick Sort) - Python

 

[알고리즘] 정렬 | [3] 퀵 정렬 (Quick Sort) - Python

[알고리즘] 정렬 | [4] 계수 정렬 (Counting Sort) - Python

[알고리즘] 정렬 | [4] 계수 정렬 (Counting Sort) - Python

^ 정렬이 궁금하다면 ^

---

1. 선택 정렬의 시간 복잡도

• 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
• 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.

𝑁 + (𝑁 - 1) + (𝑁 - 2) + ... + 2

• 이는 (𝑁² + 𝑁 - 2) / 2 로 표현할 수 있는데, 빅오 표기법에 따라서 O(N²) 이라고 작성한다.

2. 삽입 정렬의 시간 복잡도

• 삽입 정렬의 시간 복잡도는 O(N²) 이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다
  • 최선의 경우 O(N) 의 시간 복잡도를 가진다
  • 이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 어떻게 될까?
  • 두 번째 원소인 1부터 시작을 한다.
  • 그래서 1이 들어갈 위치를 골라야 하는데, 바로 왼쪽에 있는 원소와 비교할 때 본인이 더 크기 때문에 제자리에 멈춰있을 것이다.
  • 그 다음도 똑같이 계속 진행된다.
  • 그래서 이미 오름차순 정렬이 되어 있는데 또 삽입 정렬을 수행하면, 수행하자마자 멈춘다.
  • 따라서 자신이 어디 자리로 들어갈지 고르는 시간이 상쇄되기 때문에
  • 전체 정렬을 위한 시간 복잡도는 O(N) 이 된다.

3.퀵 정렬의 시간 복잡도

• 퀵 정렬은 평균의 경우 O(NlogN) 의 시간 복잡도를 가진다.
• 하지만 최악의 경우 O(N²) 의 시간 복잡도를 가진다.
  • 분할이 일정하게 되지 않고, 한쪽으로 편향되게 분할이 될 가능성이 있다.
  • 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행하면 어떻게 될까?
  • 첫 번째 원소인 0이 피벗으로 삼아지면, 우선 왼쪽에서부터 큰 데이터를 찾으면 1이다.
  • 이제 오른쪽에서부터 작은 데이터를 찾으면... 없어서 0이 된다.
  • 결과적으로 피벗이 자기 자신의 위치로 다시 변경이 되기 때문에, 분할을 할 때 왼쪽 부분은 없고 오른쪽만 있는 것과 동일해진다.
  • 그래서 오른쪽 부분에 대해서 다시 1을 피벗 값으로 설정해서 퀵 정렬을 수행하게 되고, 매번 분할이 이루어질 때마다 오른쪽 데이터만 남는 형태로 분할이 이루어지기 때문에, 최악의 겨우 분할이 실행되는 횟수가 N과 비례하고, 분할을 하기 위해서 매번 선형 탐색을 써야 하기 때문에 전체 시간 복잡도가 O(N^2)이 되는 것이다.

4. 계수 정렬의 복잡도 분석

• 계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N + K) 이다.
• 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
  • 예를 들어, 데이터가 0과 999,999로 단 2개만 존재하는 경우를 생각해 보자
  • 우리는 총 100만개만큼의 원소가 담길 배열을 만들어야 한다.
  • 이는 데이터의 범위가 너무 커서 계수 정렬을 사용하기 어렵다.
• 계수 정렬은 동일한 값을 가지는 데이터가 여러개 등장할 때 효과적으로 사용할 수 있다.
  • 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적이다.

5. 정렬 알고리즘 비교

• 앞서 다룬 네 가지 정렬 알고리즘을 비교하면 다음과 같다.
• 추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN) 을
  보장하도록 설계되어 있다.

정렬 알고리즘	평균 시간 복잡도	특징
선택 정렬	O(N²)	아이디어가 매우 간단하다.
삽입 정렬	O(N²)	데이터가 거의 정렬되어 있을 때는 가장 빠르다.
퀵 정렬	O(NlogN)	대부분의 경우에 가장 적합하며, 충분히 빠르다.
계수 정렬	O(N + K)	데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르게 동작한다.