C
2005.08.10 10:10

쉘 정렬 Shell Sort

조회 수 33147 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

+ - Up Down Comment Print Files
?

단축키

Prev이전 문서

Next다음 문서

+ - Up Down Comment Print Files
이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.


■ 쉘 정렬 개념

입력 파일에 있는 레코드들을 여러 개의 서브파일로 다시 구성하고 각 서브파일을 삽입 정렬 방법에 의해 순서적으로 배열하는 과정을 반복한 것
주어진 리스트를 적당한 매개 변수의 값만큼 서로 떨어진 레코드들과 비교하여 교환하는 과정을 매개 변수 값을 바꾸어가며 반복

■ 쉘 정렬 특징

삽입정렬의 개념을 확대하여 일반화한 정렬 방법
알고리즘이 간단하여 프로그램으로 쉽게 구현
수행 능력도 삽입 정렬보다 우수한 것으로 평가
멀리 있는 레코드들끼리 비교 및 교환될 수 있으므로, 어떤 데이타가 제 위치에서 멀리 떨어져 있다면 여러 번의 교환이 발생하는 버블 정렬 방식의 단점을 해결

■ 쉘 정렬 방법

쉘 정렬에서 서브파일을 결정하는 매개 변수의 값 h에 따라 h만큼 떨어져 있는 레코드들은 하나의 서브파일로 구성
입력 파일을 구성하는 레코드들은 h만큼 떨어져 위치한 레코드들과 비교하여 레코드의 키 값에 따라 교환하는 과정을 매개 변수를 감소시켜 1이 될 때까지 반복
매개변수의 값 h를 증분이라고 하며, h는 서브파일의 수와 같음


■ 예를 들어, 증분 h가 4이면 서브파일은,    

X[1], X[5], X[9], …

X[2], X[6], X[10], …

X[3], X[7], X[11], …

X[4], X[8], X[12], …

로 구성되어 부분 정렬이 이루어지며, 증분 h를 감소시켜 새로운 서브파일을 구성하여 정렬시킨다.

증분 h가 1이 될 때까지 위의 과정을 반복 수행하면 최종적으로 정렬된 하나의 전체 파일이 구성



■ n=8일 때, 정렬 간격(매개변수) 4, 2, 1로 입력 레코드 8, 3, 5, 6, 2, 1, 7, 4에 대한 쉘 정렬 과정



▷ 수행 1회 : 매개변수 4

증분=4
8 3 5 6 2 1 7 4

정렬 후
2 1 5 4 8 3 7 6


▷ 수행 2회 : 매개변수 2

증분=2
2 1 5 4 8 3 7 6

정렬 후
2 1 5 3 7 4 8 6



▷ 수행 3회 : 매개변수 1

증분=1
2 1 5 3 7 4 8 6

정렬 후
1 2 3 4 5 6 7 8


■ 쉘 정렬 알고리즘

------------------------------------------------------
void Shellsort(int A[], int N)
{
    int i, j, Increment;
    int Tmp;
    for(Increment=N/2; Increment>0; Increment/=2)
        for(i=Increment; i<N; i++)
        {
            Tmp=A[i];
            for(j=i; j>=Increment; j-=Increment)
                if(Tmp < A[j-Increment])
                    A[j]=A[j-Increment];
                else
                    break;
                A[j]=Tmp;
        }
}
------------------------------------------------------



■ 성능



▷ 발생하는 비교 횟수는 정렬 간격(매개변수의 값)이 수행속도 좌우
▷ 매개 변수는 근사적으로 소수이어야 한다고 알려져 있으며,
     이러한 경우의 알고리즘 수행시간은 O(N(logN)2)

▷ Shell(N/2) 최악의 경우 O(N2)
▷ Hibberd 간격 1, 3, 7, 15, ..., (2k-1) 최악의 경우 O(N3/2)

▷ Sedgewick 간격 9·4i-9·2i+1 또는 4i-3*2i+1
      { 1, 5, 9, 19, 41, 109, ... } worst O(N4/3), average O(N7/6)

▷ 쉘 정렬을 구현할 때에는 정렬간격을 배열에 저장하여 사용함
▷ 인접요소의 교환방법 개선책임, 최악 N2, 실제로 N1.5,  N1.3
▷ 쉘 정렬은 퀵 정렬 다음으로 수행속도가 빠르고 안정적

Dreamy의 코드 스크랩

내가 모으고 내가 보는

List of Articles
번호 분류 제목 날짜 조회 수 추천 수
431 Pi 아두이노 레오나르도 보드 기본 사용법 2016.11.22 11531 0
430 Pi 아두이노 데이터 저장하기(Arduino EEPROM 사용하기) 2019.12.24 17493 0
429 Pi 아두이노 Arduino String Class 2017.07.16 10174 0
428 Pi 아두이노 (Arduino)로 서보모터 (SG90) 제어 2017.07.11 10839 0
427 Pi 아두이노 (Arduino) 소개 및 유형별 종류, 제품별 특징 2016.11.15 6920 0
426 Android 실시간으로 폰의 pcap 보기 2016.01.05 7171 0
425 Pi 시프트 레지스터 사용방법 (Shift Register, 74HC595, 74HC165) 2016.11.21 31403 0
424 MFC 시작프로그램 레지스트리에 등록/해제 함수 2006.04.14 45687 0
423 일반 시스템 환경변수 세팅 2011.02.08 28276 0
422 MFC 시스템 출력 리디렉션 - 도스 커맨드 결과 받아오기 file 2007.08.14 52867 0
421 개념 스트리밍 개요 Streaming overview 2012.11.26 13871 0
» C 쉘 정렬 Shell Sort file 2005.08.10 33147 0
419 일반 소스코드 게시판입니다. 2005.07.29 45767 0
418 C 선택정렬 Selection Sort file 2005.08.10 34149 0
417 LINUX 서버간 폴더 또는 파일을 이동 하는 scp 명령어 2012.06.27 26023 0
목록
Board Pagination ‹ Prev 1 2 3 4 5 6 7 8 9 10 ... 34 Next ›
/ 34

나눔글꼴 설치 안내


이 PC에는 나눔글꼴이 설치되어 있지 않습니다.

이 사이트를 나눔글꼴로 보기 위해서는
나눔글꼴을 설치해야 합니다.

설치 취소

Designed by sketchbooks.co.kr / sketchbook5 board skin

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5