이것이 취업을 위한 코딩 테스트다 2021 - 정렬 알고리즘

#4 정렬 알고리즘

https://youtu.be/KGyK-pNvWos?si=91JdaPGhICvfiJb5 

■ 정렬?

- 데이터를 특정한 기준에 따라 순서대로 나열

- 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용

• 데이터의 개수가 적을 때
• 데이터가 많지만 특정 범위로 한정되어 있을 때
• 이미 데이터가 정렬되어 있는 경우
• ...

---

■ 선택 정렬

- 동작 원리 및 설명

• 미처리 데이터 중 가장 작은 데이터를 선택, 맨 앞에 있는 데이터와 바꾸는 것을 반복
• 미처리 데이터가 하나 남을 경우 처리하지 않아도 됨
  
  • # 처리해도 자기 자신의 위치와 같기 때문

- 동작 과정

• 1) 탐색 범위는 반복 시 줄어듦
• 2) 매번 가장 작은 데이터를 찾기 위해 탐색 범위만큼 데이터를 확인
• 3) 매번 선형 탐색을 수행하는 것과 같음
• ※ 즉, 이중 반복문을 통해 구현 가능

- '선택 정렬'의 시간복잡도: O(N^2)

• N번만큼 가장 작은 수를 찾아서 맨 앞으로 보냄
• 구현 방식에 따라서 오차는 있을 수 있지만, 전체 연산 횟수는 아래와 같음
  
  • # N+(N-1)+(N-2)+... + 2
  • # (N^2 + N - 2)/2로 표현 (등차수열 공식)
• > 빅오 표기법에 따라서 O(N^2)으로 작성

---

■ 삽입 정렬

- 동작 원리 및 설명

• 미처리 데이터를 하나씩 골라 적절한 위치에 삽입
  
  • #  어느 위치에 들어갈지 매번 계산
• 선택 정렬에 비해 구현 난이도가 높은 편이지만 더 효율적으로 동작
• 즉, 매번 왼쪽의 원소와 비교하여 자기가 작다면 위치를 바꿈

- 동작 과정

• 1) 첫 번째 데이터는 그 자체로 정렬이 되어 있다고 판단
• 2) 두 번째 데이터가 앞선 데이터(왼쪽)의 어떤 위치로 들어갈지 판단
• 3) 앞 데이터의 왼쪽이나 오른쪽으로 가는 두 경우가 존재
• 4) (반복)

- '삽입 정렬'의 시간복잡도: O(N^2)

• 선택 정렬과 마찬가지로 반복문이 두 번 중첩
• 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작
  
  • # 최선의 경우 O(N)

---

■ 퀵 정렬

-  동작 원리 및 설명

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
  
  • # C, JAVA, Python, ... 등이 채택
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정

- 동작 과정

• 1) 첫 번째 원소를 기준(Pivot)으로 설정
• 2) 왼쪽에서부터 Pivot보다 큰 값을 고르고, 오른쪽에서는 Pivot보다 작은 값을 고름
• 3) 두 값(데이터)의 위치를 서로 바꿈
• 4) (반복)
• 5) 단, 위치가 엇갈리는 경우 Pivot과 작은 데이터의 위치를 서로 변경
• 6) Pivot값이 중간으로 들어가고 데이터가 왼쪽, 오른쪽으로 분할 (Divide/Partition)
  
  • # 왼쪽은 Pivot보다 작고 오른쪽은 Pivot보다 큼
• 7) 왼쪽, 오른쪽 데이터 각각의 묶음을 하나의 배열로 보고 다시 한번 각각 퀵 정렬 수행 
  
  • # 재귀적 수행, 정렬 범위가 점점 줄어듦

- 퀵 정렬이 빠른 이유: 직관적인 이해

• 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수 O(NlogN)
• 데이터의 범위가 절반씩 줄어든다? (= 밑이 2인 logN으로 표현)
• 데이터의 개수 N * 연산 횟수 logN = NlogN

- 퀵 정렬의 시간 복잡도: O(NlogN)

• 평균 O(NlogN)의 시간 복잡도
• 최악의 경우 O(N^2)의 시간 복잡도
  
  • # 한쪽 방향으로 편향된 분할이 발생할 가능성 (자기 자신의 위치만 그대로 바뀜)
    
    • @ 오른쪽 데이터만 남는 형태
  • #  분할을 하기 위해 매 반복마다 선형 탐색 가능성
  • # 첫 번째 원소를 피벗으로 삼을 때 
• 실제 다양한 프로그래밍 언어에서 표준 라이브러리 제공 시 
  
  • # 퀵 정렬 기반은 최악의 경우에도 O(NlogN)이 보장되도록 함
   

알고리즘을 배우기 시작한 이래로 O(NlogN)을 오랫동안 이해하지 못했었다.

하지만 이번에 드디어 알게 됐다. 여기에 나오는 로그는 log_2였다는 사실...!

보편적으로 2배씩 줄어드는 과정을 logN이라고 할 수 있겠다.

---

■ 계수 정렬 (Counting Sort)

- 동작 원리

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작
  
  • # 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
• 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 
  
  • # 최악의 경우에도 수행 시간 O(N+K)를 보장

- 동작 과정

• 1) 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 담길 수 있도록 리스트 생성
• 2) 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터 1씩 증가
• 3) 최종리스트에는 각 데이터가 몇 번씩 등장했는지 그 횟수가 기록
• 4) 결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력
• ※ 즉, 각각의 데이터가 몇 번씩 등장했는지 세는 방식으로 정렬

- 계수 정렬의 시간 복잡도 및 공간복잡도: 모두 O(N+K)

• 타 정렬에 비해 상대적으로 공간 복잡도 큼
  
  • # 가장 작은 데이터부터 가장 큰 데이터까지의 모든 범위를 포함하는 배열을 만들기 때문
• 때에 따라서 심각한 비효율성을 초래할 수 있음
  
  • # 데이터가 0과 999,999로 단 2개만 존재할 때
• 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적
  
  • # 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효율적