복단대학 961 - 데이터 구조 - 제4 장 - 정렬 (1) 정렬 의 기본 개념;정렬 삽입, 힐 정렬

961 모든 내용 링크
글 목록

정렬 의 기본 개념

정렬 삽입

정렬 직접 삽입

반 으로 접 고 정렬 삽입

힐 (Shell) 정렬

정렬 의 기본 개념
정렬 은 목록 의 요 소 를 다시 배열 하여 표 의 요 소 를 키워드 에 따라 질서 있 게 하 는 과정 입 니 다.
정렬 알고리즘 은 두 가지 로 나 뉘 는데 안정 적 이 고 불안정 하 며 다음 과 같은 데이터 가 있다 고 가정 합 니 다. 7, 2, 8, 4, 9, 8.이 데이터 에는 8 이 두 개 있 는데, 여 기 는 굵기 로 표시 한다.안정 적 인 정렬 에 있어 정렬 후의 결과 중 두 개의 8 은 위 치 를 바 꾸 지 않 는 다. 즉, 2, 4, 7, 8, 8, 9 이다.그러나 불안정한 정렬 에 대해 정렬 한 후에 두 개의 8 의 순 서 는 '가능 하 다' 는 변화 가 생 겼 다. 예 를 들 어 2, 4, 7, 8, 8, 9 등 이다.
데이터 가 모두 메모리 에 저장 되 었 는 지 여부 에 따라 정렬 을 두 가지 로 나 눌 수 있 습 니 다.

내부 정렬: 내부 정렬 이란 정렬 할 데이터 가 비교적 작 아서 메모리 에 직접 저장 할 수 있다 는 것 을 말한다

외부 정렬: 내부 정렬 에 비해 정렬 할 수량 이 많 습 니 다. 예 를 들 어 몇 개의 G, 심지어 몇 개의 T 는 메모리 에 직접 저장 할 수 없 기 때문에 한 번 에 일부 데 이 터 를 메모리 에 넣 을 수 밖 에 없습니다.이런 정렬 을 외부 정렬 이 라 고 한다.

삽입 정렬
정렬 을 삽입 하 는 기본 사상: 정렬 을 기다 리 는 서열 을 두 부분 으로 나 누고 앞 에는 이미 정렬 이 되 어 있 고 뒤 에는 정렬 이 되 어 있 지 않다.정렬 되 지 않 은 시퀀스 중 하 나 를 선택 하여 정렬 된 시퀀스 에 삽입 합 니 다.정렬 되 지 않 은 모든 시퀀스 가 비어 있 을 때 까지.
직접 삽입 정렬
정렬 을 삽입 하 는 사상 에 따라 직접 정렬 알고리즘 을 쉽게 생각 할 수 있다.
질서 [0,... i]
i + 1 (정렬 대기 요소)
i + 2,..., n (무질서 수열)
정렬 사상 을 직접 삽입 하고 첫 번 째 부분 은 질서 있 는 서열 이 며 두 번 째 부분 은 무질서 한 서열 의 첫 번 째 요소 이 고 세 번 째 부분 은 남 은 무질서 한 수열 이다.알고리즘 (작은 것 부터 큰 것 까지 배열) 은 다음 과 같다.

배열 아래 표 시 된 1 부터 순환 하여 정렬 할 요소 x

를 선택 합 니 다.

x 와 앞의 요 소 를 비교 하고 앞의 요소 보다 작 으 면 두 가지 요 소 를 교환 합 니 다. 그렇지 않 으 면 x 가 생각 하 는 위치 에 도착 했다 는 것 을 설명 합 니 다

x 가 도착 해 야 할 곳 에 도착 할 때 까지 2 과정 을 반복 한다

1 과정 순환 이 끝나 면 정렬 이 끝나 고 이 서열 은 질서 가 있다.

자바 코드 는 다음 과 같 습 니 다:

public static void insertionSort(Comparable[] array) {
     
    if (array == null) return;

    for (int i = 1; i < array.length; i++) {
       //  1    ，                     

        Comparable temp = array[i];
        int j; 
        //          ，       0    ，       temp ，           。
        for (j = i; j > 0 && temp.compareTo(array[j-1]) < 0; j--) {
      
            array[j] = array[j - 1];  //            ，              j-1    ，             。
        }
        array[j] = temp; //   j        ，    
    }
}

복잡 도 분석

시간 복잡 도: 평균 시간 복잡 도와 최 악의 시간 복잡 도 는 O (n2) 이다. 이것 은 할 말 이 없 을 것 이다. 2 층 for 순환 이다.가장 좋 은 시간 복잡 도 는 O (n) 이다. 이것 은 정렬 할 서열 이 질서 에 가 까 울 때 매 라운드 의 비교 에서 앞의 요소 가 자신 보다 작 다 는 것 을 알 게 되 었 기 때문에 다음 라 운 드 를 계속 진행 할 수 있다.최종 적 으로 아주 적은 원소 교환 이 발생 한다.그래서 가장 좋 은 시간 복잡 도 는 O (n)

이다.

공간 복잡 도: O (1)

안정성: 안정 적.매번 비교 할 때 앞의 요소 가 뒤의 요소 보다 클 때 만 교환 이 발생 하고 같 으 면 교환 이 되 지 않 기 때문에 안정 적 이다.그러나 문 제 를 낼 때 는 다 바 뀌 는 것 보다 크 면 불안정 하 게 변 할 수 있다.
적용 성: 이 방식 은 순서 저장 (배열) 과 체인 저장 에 적 용 됩 니 다.무 작위 접근 이 없 기 때문이다.
반절 기 삽입 정렬
직접 삽입 정렬 과 차이 가 많 지 않 습 니 다.직접 정렬 을 삽입 하 는 것 은 비교 하면 서 교환 하 는 것 이 고 반 으로 정렬 을 삽입 하 는 것 은 앞의 질서 있 는 수열 을 반 으로 찾 아 삽입 할 위 치 를 찾 은 다음 에 통일 적 으로 교환 하 는 것 이다.사실 효율 이 떨 어 지 는 것 은 많 지 않다.그러나 반절 삽입 은 체인 메모리 에 적용 되 지 않 는 다.
코드 는 다음 과 같 습 니 다: TODO, 비중 점, 후기 보충
힐 (셸) 정렬
힐 정렬 도 직접 삽입 하 는 특성 (질서 에 가 까 운 서열 시간 복잡 도 O (n) 을 이용 했다.기본 사상 은:

서열 을 여러 그룹 으로 나 눈 다음 에 각 그룹 에 대해 직접 정렬 을 한다.

그 다음 에 그룹의 수량 을 줄 이 는 것 은 각 그룹의 요소 의 개 수 를 늘 린 다음 에 직접 정렬

을 하 는 것 과 같다.

2 를 반복 합 니 다. 한 조 만 남 았 을 때 이 조 는 전체 배열 을 대표 하여 마지막 정렬 을 한 다음 에 정렬 이 완 료 됩 니 다.

힐 의 정렬 이 이해 하기 어 려 운 점 은 바로 이 그룹 이다. 인접 한 요 소 를 한 그룹 으로 나 누 는 것 이 아니다.서로 떨 어 진 고정 거리의 원 소 를 한 조로 나 누 는 것 이다. 예 를 들 어 아래 표 시 된 0, 3, 6, 9... 의 원 소 를 한 조로 나 누고 해당 하 는 1, 4, 7, 11... 을 한 조로 나 누 는 것 이다.이때 거리 d = 3.전문 적 인 말 은 먼저 정렬 할 시 계 를 L [i, i + d, i + 2d,..., i + kd] 의 '특수' 서브 시트 로 나 누 는 것 이다. 즉, 특정한 '증 량' 과 떨 어 진 기록 을 하나의 서브 시트 로 구성 하고 각 서브 시트 에 대해 직접 정렬 을 한다. 전체 표 의 요소 가 '기본 질서' 가 있 을 때 전체 기록 에 대해 직접 정렬 을 한다.
증분 d 에 대해 서 는 매 라운드 마다 체감 해 야 한다.추천 하 는 방식 은 첫 번 째 n/2, 두 번 째 n/2/2 를 취하 고 매번 2 로 나 누 어 0 까지 하 는 것 이다.그러나 문 제 를 낼 때 서로 다른 d 의 체감 방식 을 제시 하여 매 라운드 의 정렬 결 과 를 구 할 수 있다.
예:
9
6
7
4
1
6
2
9
3
제1 라운드
d=4
1
6
2
4
3
6
7
9
9
제1 라운드
d = 4 의 그룹 번호
1 (1)
6 (2)
2 (3)
4 (4)
3 (1)
6 (2)
7 (3)
9 (4)
9 (1)
이차
d=2
1
4
2
6
3
6
7
9
9
이차
d = 2 의 그룹 번호
1(1)
4(2)
2(1)
6(2)
3(1)
6(2)
7(1)
9(2)
9(1)
제3 차
d= 1
1
2
3
4
6
6
7
9
9
이 예 에서 세 바퀴 를 거 쳐 이 서열 을 질서 있 는 서열 로 배열 했다.그 중에서 그룹 번호 의 괄호 중 같은 대표 가 한 그룹 으로 나 뉘 었 다.시험 에서 따로 조별 상황 을 그 릴 필요 가 없다.여 긴 그냥 이해 하기 편 하 게
자바 로 구현, 코드 는 다음 과 같 습 니 다:

public static void shellSort(Comparable[] array) {
     
    if (array == null) return;

    for (int d = array.length / 2; d > 0; d = d / 2) {
      //     d=n/2,   d=n/2/2，    ，  d=0  

        for (int i = d; i < array.length; i++) {
       // i d，          i=1
            Comparable temp = array[i];  //           ，           
            int j;
            for (j = i; j >= d && temp.compareTo(array[j - d]) < 0; j = j - d) {
       //         -kd      ，      
                array[j] = array[j - d];
            }
            array[j] = temp;
        }
    }
}

여기 두 번 째 for 순환 에 주의 하 세 요.힐 정렬 은 여러 그룹 으로 나 뉘 었 지만 실제로 실 행 될 때 첫 번 째 그룹 을 정렬 한 후에 두 번 째 그룹 으로 정렬 하 는 것 이 아니다.1 조 의 첫 번 째 요 소 를 삽입 하여 정렬 한 다음 에 2 조 의 첫 번 째 요 소 를 정렬 한 다음 에 3 조 의 첫 번 째 요 소 를 순서대로 유추 하 는 것 이다.그리고 1 조 의 두 번 째 원소...
복잡 도 분석:

시간 복잡 도: 가장 좋 은 시간 복잡 도 는 O (n) 이 고 평균 복잡 도 는 O (n 1.3) 이 며 최 악의 시간 복잡 도 는 O (n2)

이다.

공간 복잡 도: 공간 복잡 도 O (1)

안정성: 불안정.같은 데이터 두 개가 다른 그룹 으로 나 뉘 면 순서 가 바 뀔 수 있 습 니 다.
적용 성: 순서 저장 에 만 적 용 됩 니 다.무 작위 접근 특성 을 사용 해 야 하기 때문이다.