정렬 - 사고 분석 (2)

간단 한 소개
이 글 은 최근 에 배 운 정렬 알고리즘 을 정리 하여 그 사상 과 차이 점 을 추출 해 냈 다.직접 정렬 삽입, 힐 정렬, 정렬 선택
정렬 직접 삽입 (정렬 삽입)
매번 무질서 구역 의 첫 번 째 기록 을 키워드 에 따라 질서 구역 의 적당 한 위치 에 삽입 하고 질서 구역 의 길 이 를 1 로 추가 합 니 다.

//  a[0..len]      ，0       
void InsertSort(int a[],int len){

    // i             
    for(int i = 1; i < len; i ++){
        //      a[i+1]      
        if( a[i] > a[i+1] ){

            a[0] = a[i+1];
            int j = i+1;
            //   ，  <= >= 
            while(j>0 && a[j]>=a[0]){
                a[j] = a[j-1];
                j --;
            }

            a[j+1] = a[0];
        }
    }
} 

최 악의 경우 시간 복잡 도 O (n)²)
힐 정렬 (셸 정렬)
힐 정렬 은 전체 대기 서열 (R ₁, R ₂, R ₃,... Rn) 을 증 량 d 에 따라 d 자 서열 로 나 누 는 것 이다. 그 중에서 i (1 < = i < = d) 자 서열 은 (Ri, Ri + d, Ri + 2d,... Ri + kd) 이 고 각 자 서열 에 대해 직접 정렬 을 한다. 증 량 d 를 계속 줄 이 고 이 과정 을 반복 한다. d 가 1 로 줄 어 들 때 까지 전체 서열 에 대해 직접 정렬 을 삽입 한다.

// a[1..len]         d       
void ShellInsert(int a[],int len,int d){

    for( int i = 1; i + d <= len; i ++ ){
        if( a[i] > a[i+d] ){
            a[0] = a[i+d];

            int j = i+d;
            //            ★★
            while(j-d>0 && a[j]>=a[0]){
                a[j] = a[j-d];
                j -= d;
            }

            a[j+d] = a[0];
        }
    }
}

void ShellSort(int a[],int len, int b[],int dlen){
    for( int i = 0; i < dlen; i ++ ){
        ShellInsert(a,len,b[i]);        
    }
} 

힐 정렬 의 시간 복잡 도 는 증 량 서열 의 함수 로 아직 정확하게 분석 하기 어렵다.
힐 정렬 은 불안정 정렬 입 니 다.
정렬 선택 (선택 정렬)
정렬 할 시퀀스 에서 최소 또는 최대 요 소 를 선택 하고 정렬 된 끝 에 교환 합 니 다.

//　 a[1..len]       
void SelectionSort(int a[],int len){

    int sel;
    for(int i = 1; i <= len; i ++ ){
        sel = i;
        for( int j = i; j <= len; j ++){
            if( a[sel] > a[j] )//     
                sel = j;
        }

        //     
        if( sel != i ){
            int t = a[sel];
            a[sel] = a[i];
            a[i] = t;
        }
    }
}