Sorting Algorithm   정렬 알고리즘

(2018-12-29)

버블 정렬

1. 정렬 알고리즘 (Sorting Algorithm)

  ㅇ 정렬 : 수많은 자료를 특정 목적에 맞게 순서있게 재배열하는 것
     - 레코드들을 키 값의 순서로 재배열하는 것

  ㅇ 정렬 알고리즘 : 정렬을 수행하는 다양한 알고리즘
      - 탐색의 효율성, 실용성, 이론 설명 등을 위해서도 정렬 알고리즘이 필요함
      * 100개 이상의 정렬 알고리즘들이 개발되어 왔음


2. 정렬 알고리즘 분류

  ㅇ 정렬 장소에 따른 분류
     - 내부 정렬 : 정렬 전 모든 데이터가 주기억장치에 올라와있음
     - 외부 정렬 : 대부분 데이터가 외부기억장치에 있고, 필요시 일부분씩 만 주기억장치에 올림
     - 제자리 정렬 : 입력 자료에 할당된 메모리 이외 일정 상수 만큼 작은 추가 메모리 만 필요

  ㅇ 단순성,효율성에 따른 분류
     - 단순하지만 비효율적 : 버블 정렬, 선택 정렬, 삽입 정렬
     - 복잡하지만 효율적   : 퀵 정렬,  정렬, 병합 정렬, 기수 정렬 등
 
  ㅇ 키 비교 방식에 따른 분류
     - 항목 교환하는 방식          : 선택 정렬, 버블 정렬, 퀵 정렬
     - 적절한 위치에 삽입하는 방식 : 삽입 정렬, 셀 정렬
     - 자료를 먼저 분할하고, 병합하면서 정렬하는 방식 : 병합 정렬


3. 주요 정렬 알고리즘

  ㅇ 버블 정렬 (Bubble Sort)
     - 이웃 요소 간에 대소 비교하고 필요시 교환을 수행하며, 전체 자료에 걸쳐 반복 수행
     - 버블 의미 : 매 반복 마다 가장 큰 수가 버블되어 이동됨
     - 주요 연산 : 비교(compare), 교환(swap)
     - 정렬 여부 확인 조건 : 어떤 교환도 하지 않고 훑어지면 자료가 정렬된 상태 임
     - 계산 효율성 : O(n2)

  ㅇ 선택 정렬 (Selection Sort)
     - 가장 큰/가장 작은 자료를 선택하고(찾고) 선두로 옮기는(교환하는) 과정을 반복적으로 수행
     - 계산 효율성 : O(n2)

  ㅇ 삽입 정렬 (Insertion Sort)
     - 선택한 요소를 그보다 더 앞쪽의 알맞은 위치로의 삽입을 반복적으로 수행
     - 특징 : 크기가 작은 정렬 문제에 효율적

  ㅇ  정렬 (Heap Sort)

  ㅇ 퀵 정렬 (Quick Sort)
     - 가장 빠른 정렬 알고리즘 중의 하나로 널리 사용됨
        . 1962년 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 발표
     - 계산 효율성 : O(nlogn)


[정렬 알고리즘] 1. 정렬 알고리즘 2. 선택 정렬 3. 삽입 정렬

 
        최근수정     요약목록     참고문헌