정보처리기사/소프트웨어 개발

데이터 입출력 구현 7

RangA 2023. 5. 13. 22:04

정렬(Sort)

01. 정렬의 종규

1) 정렬의 개념

  • 여러 개의 자료를 순서에 따라 나열하는 방법
  • 자료에 속한 키 값에 따라 오름차순과 내림차순으로 정렬
  • 키 값이란 자료의 자신이 될 수도 있고, 레코드의 특정 필드가 될 수도 있음

2) 정렬의 종류

  • 자료의 개수, 자료의 특성에 따라 종류가 나뉨
  • 기수 : 정렬할 자료의 자릿수의 값을 의미
  정렬의 종류     특징  
  선택 정렬     큰(작은) 키 값을 찾아 교환  
  버블 정렬     인접한 키 값을 교환, 이미 정렬되었으면 중단함  
  삽입 정렬     자신의 위치를 찾아서 삽입  
  쉘 정렬     삽입 정렬을 개선한 방법  
  퀵 정렬     자료의 중간 값을 정한 후 정렬  
  힙 정렬     이진 트리 구조를 만들어 정렬  
  이진 병합 정렬     두 개의 키를 한 쌍으로 정한 후 정렬  
  버킷 정렬     기수 값에 따라 분배하여 정렬하는 방식  

3) 정렬의 시간 복잡도

  • 입력되는 자료의 수와 자료의 형태에 따라 연산 횟수는 다를 수 있음
  • 연산 횟수가 적을 때는 최선, 연산 횟수가 가장 많을 때는 최악, 그리고 평균적인 경우로 구분
  정렬의 종류     최상     평균     최악  
  선택 정렬     O(n)     O(n2)     O(n2)  
  버블 정렬     O(n2)     O(n2)     O(n2)  
  삽입 정렬     O(n2)     O(n2)     O(n2)  
  쉘 정렬     O(n)     O(n1.5)     O(n1.5)  
  퀵 정렬     O(nlog2n)     O(nlog2n)     O(n2)  
  힙 정렬     O(nlog2n)     O(nlog2n)     O(nlog2n)  
  이진 병합 정렬     O(nlog2n)     O(nlog2n)     O(nlog2n)  
  버킷 정렬     O(dn)     O(dn)     O(dn)  


02. 선택 정렬(Selection Sort)

1) 선택 정렬의 개념

  • 오름차순으로 정렬했을 때 가장 작은 값을 찾아 선택된 위치 자료와 교환하는 방법
  • 가장 작은 값을 먼저 결정하는 경우, 가장 작은 값이 1번째로 결정되며, 2번째, 3번째 작은 값 순으로 결정됨
  • 가장 큰 값을 먼저 결정하는 경우, 가장 큰 값이 1번째로 결정되며, 2번째, 3번째 큰 값 순으로 결정됨
  • 1번째 자료가 결정되면 1번째를 제외한 2번째 이후의 자료들이 정렬 대상
  • 선택 정렬은 각 Pass 단계에서 여러 번 교체할 수 있고, 한 번만 교체할 수 있음


03. 버블 정렬(Bubble Sort)

1) 버블 정렬의 개념

  • 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하며 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
  • 1번째, 2번째와 비교, 2번째와 3번째와 비교, 3번째와 4번째와 비교하면서 자료를 교환함
  • 오름차순으로 정렬하였을 때 마지막 자료가 먼저 결정됨
  • 마지막 자료가 결정되면 마지막 자료를 제외한 자료들이 정렬 대상


04. 삽입 정렬(Insertion Sort)

1) 삽입 정렬의 개념

  • 첫 번째 자료를 기준으로 두 번째부터 차례로 비교하여 자기 위치를 찾아 삽입하는 정렬 방법
  • 정렬할 자료 일부가 정렬되어 있는 경우에 유리한 방법
  • 임의의 자료가 중간에 삽입되는 경우에는 삽입 위치 이후에 있는 자료들은 한 칸씩 위치 이동함


05. 쉘 정렬(Shell Sort)

1) 쉘 정렬의 개념

  • 삽입 정렬의 단점을 보완하여 확장한 개념으로 간격을 정하고 간격을 점차 줄이면서 삽입 정렬하는 방법
  • 임의의 레코드 키와 매개변수 값만큼 떨어진 곳의 레코드 키를 비교하여 순서화 되어 있지 않으면 서로 교환하는 것을 반복하는 정렬 방식
  • 쉘 정렬은 자료가 많은 경우에 삽입 정렬보다 비교 횟수가 줄어듦
  • 10개의 자료에서 간격이 5라면 1번째 자료와 6번째 자료를 비교하게 됨
  • 자료 수가 n개일 때 가장 이상적인 처음의 간격
    • 간격 = 1.723√n
    • 10개의 자료가 있다면 가장 이상적인 처음의 간격은 1.723√10 = 3.705.. 이므로 3이나 4로 정하면 됨
  • 정렬 대상 자료량이 많을 때 유리한 방식
  • 입력 파일이 부분적으로 정렬되어 있는 경우 유리한 방식


06. 힙 정렬(Heap Sort)

1) 힙 정렬의 개념

  • 임의의 자료에서 최솟값 또는 최댓값을 구할 경우 가장 적합한 정렬 방법
  • 자료를 순서적으로 완전 이진 트리 형태로 만들어 정렬하는 방법
  • 하위 노드 그룹으로부터 상위 노드 그룹으로 점차 확대하는 방법
  • 오름차순 정렬인 경우에 자노드가 부노드보다 크면 자료를 교환함
  • 시작하는 하위 노드 그룹의 결정 공식
    • k : 시작 하위 노드 그룹, n : 전체 자료 수
    • k = n/2


07. 이진 병합 정렬(2-Way Merge Sort)

1) 이진 병합 정렬의 개념

  • 정렬 대상의 자료들을 그룹별로 정렬하여 병합하면서 정렬하는 방법


08. 버킷 정렬(Bucket Sort)

1) 버킷 정렬의 개념

  • 스택(Stack)을 이용하여 정렬하는 방법
  • 레코드의 키 값을 분석하여 같은 값끼리 그 순서에 맞는 버킷에 분해하였다가 버킷의 순서대로 레코드를 꺼내어 정렬


09. 퀵 정렬(Quick Sort)

1) 퀵 정렬의 개념

  • 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방식
  • 레코드의 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽 서브 파일로 분해하여 정렬하는 방식
  • 정렬 방식 중에서는 가장 빠른 방식이며, 프로그램에서 재귀적 함수를 이용하기 때문에 스택을 필요로 함
저작자표시 비영리 변경금지