제5장 정렬 알고리즘

1. 제5장 정렬 알고리즘
   1. 5.5. 쉘 정렬(Shell Sort)
   2. 문서에 대하여

5.5. 쉘 정렬(Shell Sort)

• 정의 : 인접한 요소만을 교환하는 삽입 정렬의 단점을 극복하기 위해서 h만큼의 간격으로 떨어진 요소들을 교환한다.
  고무를 잡아당기는 듯한 점진적인 형태를 보인다.

• 단점: 안정성(stability)이 없다.

5.5.1. 쉘 정렬의 전략

• 1. h의 초기값을 구한다.
• 2. h가 1보다 작으면 끝낸다.
• 3. i =0
• 4. i가 h보다 크거나 같으면 7로 간다.
• 5. (h간격 +i) 요소들에 대해서 삽입정렬을 한다.
• 6. i를 하나 증가시키고 4로 간다.
• 7. h의 다음 값을 구하고 2로 간다.

5.5.2. 쉘 정렬 자바로 구현

 public class ShellSort {
	
  public static void shellSort(char[] arrAlphabet, int arrLength){
     int i,j,k;
     int iLength;
     char temp;

     for(iLength=arrLength/2;iLength>0;iLength=iLength/2){

       for(i=0;i<iLength;i++)
       {	

          for(j=i+iLength;j<arrLength;j+=iLength){

             temp = arrAlphabet[j];
             k=j;

            while(k>iLength-1&&arrAlphabet[k-iLength]>temp){

                  arrAlphabet[k]=arrAlphabet[k-iLength];
                  k -=iLength;
            }
           arrAlphabet[k] = temp;	
        }
      }
    }
  }
	
  public static void initData(char[] arrAlphabet, int arrLength){

      System.out.println("/===========================/");
      
      for(int i=0;i<arrAlphabet.length;i++){
           System.out.println("char[" + i + "]:"+arrAlphabet[i]);
      }
  }

  public static void main(String[] args) {

      char[] alphabet = new char[]{'T','O','L','E','A','R','N','S','O','R','T','A','L','G','O','R','I','T','H','M'};

      initData(alphabet, alphabet.length);

      shellSort(alphabet, alphabet.length);

      initData(alphabet, alphabet.length);

   }

}

결과:


/==초기값=========================/
char[0]:T
char[1]:O
char[2]:L
char[3]:E
char[4]:A
char[5]:R
char[6]:N
char[7]:S
char[8]:O
char[9]:R
char[10]:T
char[11]:A
char[12]:L
char[13]:G
char[14]:O
char[15]:R
char[16]:I
char[17]:T
char[18]:H
char[19]:M
/==정렬된 값=========================/
char[0]:A
char[1]:A
char[2]:E
char[3]:G
char[4]:H
char[5]:I
char[6]:L
char[7]:L
char[8]:M
char[9]:N
char[10]:O
char[11]:O
char[12]:O
char[13]:R
char[14]:R
char[15]:R
char[16]:S
char[17]:T
char[18]:T
char[19]:T

문서에 대하여

• 이 문서의 내용은 C로 배우는 알고리즘 (1) 교재를 스터디 하면서 정리한 내용 입니다.
• 최초작성자 : 임영미
• 최초작성일 : 2009년 4월 02일
• 이 문서는 오라클클럽 자바 웹개발자 스터디 모임에서 작성하였습니다.
• 이 문서를 다른 블로그나 홈페이지에 퍼가실 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^\^