IT용어위키



정렬 알고리즘


sort
파일을 구성하는 각 레코드를 특정 키 항목을 기준으로 오름차순/내림차순으로 재배열하는 작업을 말한다

실행 방법에 따른 분류

비교식 정렬(comparative sort)와 분산식 정렬(distribute sort)가 있다.

기억장치에 따른 분류

내부정렬기법

데이터량이 적을 때 주기억장치 내에서 정렬하는 방법
속도는 빠르나 기억장치의 용량을 초과하는 대용량 자료의 정렬이 어려움
  • 삽입 정렬(Insertion Sort)
    • 이미 순서화된 파일에 새로운 레코드를 추가하여 순서에 맞게 배치 (2번째 값부터 시작한다)
    • 시간 복잡도: O(n²)
  • 선택 정렬(Selection Sort)
    • 레코드의 최소값을 찾아 첫번째 위치에 놓고 다음 최소값을 찾아 두번째 위치에 놓는 방법을 반복하여 정렬
    • 시간 복잡도: O(n²)
  • 버블 정렬(Bubble Sort)
    • 인접한 값과 비교하여 정렬하는 방식. 끝에 값부터 정해진다.
    • 시간 복잡도: O(n²)
  • 힙 정렬(Heap Sort)
    • 정렬한 입력 레코드들로 힙을 구성하고 가장 큰 키값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법
    • 시간 복잡도: O(nlog₂n)

외부정렬기법

대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에 테이프나 디스크 내에서 각 서브파일을 합병하는 방법
  • 속도는 느리지만 자료의 대용량 자료를 정렬할 수 있음
  • 진동 병합 정렬(Oscillating Merge Sort)
  • 캐스케이드 병합 정렬(Cascade Merge Sort)
  • 폴리파즈 병합 정렬(Polyphase Merge Sort)
  • 균형 병합 정렬(Balance Merge Sort)

정렬 알고리즘의 선택시 고려사항

  1. 키값들의 분포 상태
  2. 소요공간 및 작업시간
  3. 정렬에 필요한 기억공간의 크기
  4. 데이터의 양
  5. 초기 데이터의 배열상태
  6. 사용 컴퓨터 시스템의 특성

  출처: IT위키(IT위키에서 최신 문서 보기)
  * 본 페이지는 공대위키에서 미러링된 페이지입니다. 일부 오류나 표현의 누락이 있을 수 있습니다. 원본 문서는 공대위키에서 확인하세요!