Sort.java

이곳에서 정렬알고리즘 개요 확인 가능하다.

 

 

필요한 문제만 발췌하면 주요 정렬 알고리즘 요약 부분이다.

그 중에서도 버블정렬 을 사용한다.

ㅇ 버블 정렬 (Bubble Sort)
     - 가장 간단한 정렬 알고리즘
     - 정렬 방법
        . 이웃 요소 간에 대소 비교하고, 필요시 교환을 수행하며,
        . 이 과정을 전체 자료에 걸쳐 반복 수행
        . 비교를 좌(위)에서 우(아래)로 또는 우(아래)에서 좌(위)로도 진행 가능
     - 주요 연산 : 비교(compare), 교환(swap)
     - 계산 효율성 : O(n2)

  ㅇ 교환 정렬 (Exchange Sort) (때론, 버블 정렬과 동의어로 쓰이기도 함)
     - 정렬 방법 : 버블 정렬과 거의 같으나, 
        . 인접 위치의 두 수 간에 비교/교환이 아니라,
        . 두 수의 위치 중 하나를 고정하고 다른 위치를 이동하며 비교/교환을 수행
     - 계산 효율성 : O(n2)

ㅇ 선택 정렬 (Selection Sort)
     - 정렬 방법
        . 가장 큰/가장 작은 자료를 선택하고(찾고),
        . 선두로 옮기는(교환하는) 과정을 반복적으로 수행
     - 주요 연산 : 비교(compare), 교환(swap)
     - 계산 효율성 : O(n2)
     - 키 비교 횟수 : 총 n(n-1)/2회로써, `버블 정렬,교환 정렬`과 같음

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

  ㅇ 힙 정렬 (Heap Sort)
     - 힙 이라는 완전 이진 트리 구조를 통해 정렬하는 방식

  ㅇ 퀵 정렬 (Quick Sort)
     - 가장 빠른 정렬 알고리즘 중의 하나로 널리 사용됨
     - 주요 연산 : 비교(compare), 교환(swap)
     - 계산 효율성 : O(nlogn)

  ㅇ 병합 정렬 (Merging Sort)
     - 자료를 여러 부분 집합으로 분할하고, 각각 정렬한 다음에, 이를 병합하면서 정렬하는 방식
     - 계산 효율성 : O(nlogn)

  ㅇ 기수 정렬 (Radix Sort)
     - 키 값을 여러 부분 집합으로 분배한 후 이를 이용하는 정렬하는 방식