[알고리즘] 정렬

정렬

 1.내부 정렬

    정렬한  자료를 주기억장치에 저장한 상태에서 저장

     1.1. 정렬 방식

        1)교환방식: 버블정렬, 퀵정렬

        2)삽입방식: 삽입정렬, 셀정렬

        3)병합방식: 2-way병합, n-way병합

        4)분배방식: 기수정렬 (키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식)

        5)선택방식:선택정렬,힙정렬

 

 2.외부 정렬

    외부 기억장치(하드 디스크)에 대부분의 데이터가 있고, 그 중 일부만 주기억 장치에 저장된 상태에서 정렬 

 

 

3. 정렬 알고리즘 

     정렬 알고리즘은 배열의 원소를 원한느 순으로 배치하는 알고리즘을 의미한다. 입력 인자로 정렬할 자료들이 있는 배열의 시작주소, 원소개수, 비교 알고리즘이 필요하며 수행 후에는 배열 내의 자료들이 원하는 순서로 배치된 상태여야 한다. 

    모든 경우에 대해서 최적인 정렬 알고리즘은 없으며, 상황에 따라 프로그래머가 적절히 이용해야한다. 

 

    단순하지만 비효율적인 정렬: 삽입정렬, 선택정렬, 버블정렬 등 (시간 복잡도가 높다)

    복잡하지만 효율적인 정렬 : 퀵, 힙, 합병, 기수정렬

 

   

   3.1 순차 정렬 

       반복적인 방법으로 해결하는 알고리즘으로, 맨 앞에서부터 제일 작은 원소를 배치해 만들어나가는 알고리즘이다.  배치할 자리에 있는 원소를 뒤쪽에 있는 원소들과 비교하면서 작은 것을 발견하면 배치할 위치의 원소와 교환한다.

       

       반복(i=0~n) , 반복(j =i+1~n), 조건(arr[i], arr[j] > 0), 교환(arr[i],arr[j])로 시간 복잡도는 최선/최악 모두 O(n^2)이다. 

      

 3.2 버블 정렬 

        마찬가지로 반복적인 방법인 알고리즘으로, 앞에서부터 이웃힌 원소끼리의 값을 비교하여 위치를 교환하는 것을 반복한다. 수행 시 제일 큰 값이 맨 뒤에 위치한다. 정렬할 개수가 반복할 때마다 줄어들고, 1이 되면 작업을 완료한다.

     

        반복(i=n, i>1, i--), 반복(j=1,j<i,j++), 조건(arr[j-1],arr[j]>0), 교환(arr[j-1],arr[j])로 시간복잡도는 최선/최악 모두 O(n^2)이다.