[Certi 세미나] 알고리즘 기초 - 자료 정렬

• 삽입 정렬 (Insert Sort)
  1. 앞쪽의 원소들은 이미 정렬되었다고 가정
  2. 정렬할 원소부터 차례로 삽입될 위치를 찾아 삽입한다.

💡 핵심 아이디어 : 원소를 알맞은 위치에 삽입하자.

 

• 퀵 정렬 (Quick Sort)
  1. 임의의 Pivot(보통 제일 앞 또는 뒤의 요소)을 선정하고, Pivot을 기준으로 작고, 큰 묶음으로 나눈다.
  2. 나눠진 좌우 묶음에 대해 더 이상 쪼개지지 않을 때까지 반복한다.
  ※ 데이터가 정렬된 경우 O(N2)까지 성능이 저하된다.

💡 핵심 아이디어: Pivot을 중심으로 나눈다. (Pivot은 보통 맨앞 or 맨뒤로 잡는다.)

 

• 합병 정렬 (Merge Sort)
  1. 분할 : 배열의 크기가 1이 아니라면, n/2로 쪼갠다.
  2. 정복 : 각 부분 배열을 정렬한다.
  3. 통합 : 부분 배열을 합병하여 하나의 배열로 만든다.

💡 핵심 아이디어: 분할해서 정렬한다.

 

• 힙 정렬 (Heap Sort)

: 완전 이진 트리의 일종으로 레벨 간 정렬만 유지되는 느슨한 정렬 상태 반정렬을 유지한다.

 

[Heap의 종류]

• Min Heap : 부모 노드가 자식 노드보다 작거나 같은 Heap
• Max Heap : 부모 노드가 자식 노드보다 크거나 같은 Heap

💡 핵심 아이디어 : Max Heap을 만들어, 정렬한다.

 

• 계수 정렬 (Counting Sort)
  1. 최대 값이 K일 때, K+1크기의 배열을 만들고 0으로 초기화 한다.
  2. 모든 요소 A[i]에 대해 해당 빈도를 array[a[i]]에 저장한다.

💡 핵심 아이디어 : 요소의 빈도를 요소 값의 위치에 저장하는 카운팅 배열을 이용한다.

 

• 이진 탐색 (Binary Search)

💡 핵심 아이디어 : 중간 위치의 값과 크기 비교를 탐색 성공할 때까지 반복한다.

 

* 정렬 함수 쓰는 법 익혀두기