정보처리기사 정렬과 시간복잡도 정리

삽입 정렬(Insertion Sort)

두번째 값부터 이전 값들과 비교를 시작함

비교하는 값을 Key라고 할 때, 순서를 변경해야 한다면 Key를 변경 할 자리에 삽입하고 그 자리에 있던 값은 뒤로 한 칸 이동 시킴.

예시 "85624"

• key = 5 : 85624 -> 58624
• key = 6 : 58624 -> 56824 
• key = 2 : 56824 -> 25674
• key = 4 : 25684 -> 24568

 

선택 정렬(Selection Sort)

처음 원소 자리부터 순서대로 모든 값들을 검사하여 작은 순서대로 정렬하는 방법

예시 "85624"

• 첫번째 원소 자리 : 85624 -> 25684
• 두번째 원소 자리 : 25684 -> 24685
• 세번째 원소 자리 : 24685 -> 24586
• 네번째 원소 자리 : 24586 -> 24568

 

버블 정렬(Bubble Sort)

서로 인접한 원소를 비교하여 위치를 변경함, 첫번째 부터 마지막-1 번째 원소까지 반복함

예시 "85624"

• 1회 : 85624 : 58624 -> 56824 -> 56284 -> 56248
• 2회 : 56248 : 56248 -> 52648 -> 52468
• 3회 : 52468 : 25468 -> 24568
• 4회 : 24568

 

퀵 정렬(Quick Sort)

레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법

키를 기준으로 작은 값을 왼쪽, 큰 값을 오른쪽 서브 파일로 분해 시키는 방식으로 정렬

• 분할(Divide)와 정복(Conquer)을 통해 자료를 정렬
• 평균 수행 시간 복잡도는 O(nlog2n)이고, 최악의 수행 시간 복잡도는 O(n^2)임

 

힙 정렬(Heap Sort)

완전 이진 트리(Complete Binary Tree)를 이용한 정렬 방식

• 구성된 완전 이진 트리를 Heap Tree로 변환하여 정렬
• 평균과 최악 모두 O(nlog2n)의 시간 복잡도를 가짐

최소 힙 - 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙

최대 힙 - 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

 

2-Way 합병 정렬(Merge Sort)

이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

• 평균과 최악 모두 시간 복잡도는 O(nlog2n)임

 

이분 검색(이진 검색, Binary Search)

Binary Search

전체 파일을 두 개의 서브파일로 분리해 가면선 Key 레코드를 검색하는 방식

• 순서화된 파일만 검색 가능
• 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색
  • key보다 작으면 왼쪽
  • key보다 크면 오른쪽
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로서 탐색 효율이 좋고 탐색 시간이 적게 소요
• 중간 레코드 번호 M = (F + L) / 2 
  • F : 첫 번째 레코드 번호
  • L : 마지막 레코드 번호

 

해싱 함수(Hashing Function)

HashFunction

• 제산법(Division)
  • 레코드 키(K)를 해시표(Hash Table)의 크기보다 큰 수 중에서 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식
  • h(K) = K mod Q
• 제곱법(Mid-Square)
  • 레코드 키 값(K)을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식
• 폴딩법(Folding)
  • 레코드 키 값(K)을 여러 부분으로 나 눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식
• 기수 변환법(Radix)
  • 키 숫자의 진수를 다른 진수로 변 환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 주소 범위에 맞게 조정하는 방법
• 대수적 코딩법(Algebraic Coding)
  • 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나 누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식
• 숫자 분석법(Digit Analysis, 계수 분석법)
  • 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만 큼 택해서 홈 주소로 삼는 방식
• 무작위법(Random)
  • 난수(Random Number)를 발생시 켜 나온 값을 홈 주소로 삼는 방식

출처: https://pupbani.tistory.com/101 [Pupbani's Program Lab:티스토리]