9강 제 5장 정렬알고리즘 1

학습목표 

1. 정렬과 관련된 주요 개념을 이해할 수 있다.

2. 기본적이 정렬 알고리즘 (버블 정렬, 선택 정렬, 삽입 정렬, 셀 정렬)의 개념, 동작, 그리고 특징을 이해할 수 있다.

3. 개선된 성능을 갖는 정렬 알고리즘 (합병 정렬, 퀵정렬, 힙 정렬)의 개념, 동작, 그리고 특징을 이해할 수 있다.

4. 선형 시간의 계수 정렬과 기수 정렬의 개념, 동작 그리고 특징을 이해할 수 있다.

 

주요 용어

#내부정렬 #안정적정렬 #제자리정렬 #비교기반 정렬 #패스 #버블정렬 #선택정렬 #삽입정렬 #셸정렬 #합병정렬 #퀵정렬 #피벗 #힙 #힙정렬 #하한 #계수정렬 #기수정렬

 

 

 

5.1 정렬( sort )의 개념

정렬은 여러 데이터로 구성된 리스트에서 값의 크기 순서에 따라 데이터를 재배치하는 것이다.

정렬을 수행하는 시점에 데이터가 어디에 저장되어 있는지에 따라 내부 정렬과 외부 정렬로 구분할 수 있다.

 

내부정렬 : 모든 데이터를 주기억장치에 저장한 후 정렬하는 방식

외부정렬 : 모든 데이터를 보조기억장치에 저장한 패 일부 데이터씩만 반복적으로 주기억장치로 읽어 들여서 정렬하는 방식

 

내부정렬 알고리즘 종류

비교 기반 알고리즘 : 버블정렬, 선택정렬, 삽입 정렬, 셸정렬 //

향상된성능을 가진 비교기반 알고리즘  (키값의 비교 횟수) : 합병정렬, 퀵정렬, 힙정렬 

 

데이터분포기반 알고리즘 (자료의 이동 횟수(선형시간 복잡도)) : 계수정렬, 기수 정렬

 

안정적 stable 정렬

동일한 값을 갖는 데이터가 여러 개 있을때

정렬전의 상대적인 순서가 정렬 후에도 그대로 유지 되는 정렬방식

 

제자리 in-place 정렬

입력 데이터를 저장하는 공간 이외에 추가적인 저장곤간을 상수 개만 필요로 하는 정렬 방식 

  입력 크기 n이 증가함에도 불구하고 추가적인 저장공간은 증가하지 않음

 

5.2. 버블 (bubble sort)  정렬 

5.2.1. 개념과 원리

 인접한 두 값을 비교하여 왼쪽의 값이 더 큰 경우에는 자리를 바꾸는 과정을 반복해서 정렬하는 방식

 

 

5.2.2 알고리즘

 

BubbleSort( A[], n )

입력 : A [ 0..n-1 ] : 입력 배열

           n : 입력 크기 ( 정렬할 데이터의 개수 )

출력 : A[0..n-1] : 정렬된 배열

{

  for( i = 0; i < n-1; i ++)    // ( n - 1 )번의 패스

     for ( j = 0 ;  j < (n-1) - i; j++ ) // 왼쪽에서 오른쪽으로 진행하는 경우

         if( A[ j ] > A [ J +1 ] ) // 왼쪽값 > 오른 쪽 값이면

             A[ j ]와 A [ j + 1 ] 의 자리 바꿈; // tmp = A[j]; A[j]= A[j+1]; A [ j+1]= tmp;

  return A;

}

 

5.2.3 성능 분석

BubbleSort (A[],n)

{
   for(i=0;i<n-1;i++)
      for(j=0;j<(n-1)-i;j++)
         if(A[j]>A[j+1])
            A[j]와 A[j+1]의 자리바꿈;
   returnA;
}   >>>>>>>>>>>>>>>> 시간 복잡도 O(n^2)

5.2.4 특징

1. 안정적 정렬 알고리즘이다.

2. 제자리 정렬 알고리즘

  입력 배열 A[],입력 크기 n + 추가적인 저장공간은 상수 개 (제어변수 i와 j,데이터 교환을 위한 변수)

3. 개선 여지가 있다.

개선된 알고리즘

BubbleSort (A[],n) 

{ 

   for(i=0;i<n-1;i++)            // ( n - 1 ) 번의 패스

     {

      exchange=false;

      for(j=0;j<(n-1)-i;j++)     // 왼쪽에서 오른 쪽으로 진행하는 경우

           if(A[j]>A[j+1])         // 왼쪽값 > 오른쪽값이면

           {

                A[j]와 A[j+1]의 자리바꿈;

                exchange=true;

            }

      if(exchange==false)break;    // 자리 바꿈이 발생하지 않으면 반복문 종료

     }

returnA;

}

역순으로 정렬된 경우  : O ( n^2 )

제 순서로 정렬된 경우 : O ( n )

 

 

 

5.3 선택 정렬 ( selection sort ) 

 

5.3.1 개념과 원리

주어진 데이터 중에서 가장 작은 값부터 차례대로 '선택' 해서 나열하는 방식

 

5.3.2 알고리즘 

SelectionSort (A[],n) 

입력 : A[ 0..n-1 ] : 입력 배열

        n : 입력 크기

출력 : A [ 0..n-1 ] : 정렬된 배열

{ 

   for( i=0; i<n-1; i++ )

    {     // ( n-1 ) 번 반복

      Min=i;                    //미정렬 부분 A[i..n-1]에서 최솟값 찾기

      for( j= i + 1 ;  j < n; j++)

         if( A[Min] > A[j])

            Min=j;            //미정렬 부분의 첫 번째 원소와 최솟값 교환

       A[i]와 A[Min]의 자리바꿈;

      }

   returnA;

}

5.3.3 성능 분석

SelectionSort ( A[] , n )

{

   for ( i = 0; i < n-1; i++ )

      {

         Min=i;

         for ( j = i + 1; j < n; j++)

            if ( A[Min] > A[j] )

                Min = j ;

          A[ i ]와 A[ Min ]의 자리바꿈;

        }

   returnA;

}     >>>>>>>>>   시간 복잡도  O ( n^2) 

 

 

5.3.4 특징

 

1. 언제나 동일한 시간 복잡도 O(n2)

  최솟값을 찾는 과정이 데이터의 입력 상태에 민감하지 않음

 

2. 제자리 정렬 알고리즘

 

3. 안정적이지 않은 정렬 알고리즘

 

 

5.4. 삽입 ( insertion sort ) 정렬

5.4.1 개념과 원리

  주어진 데이터를 하나씩 뽑은 후 나열된 데이터들이 항상 정렬된 형태를 가지도록 뽑은

데이터를 바른 위치에 '삽입' 해서 나열하는 방식

- 입력 배열을 정렬 부분과 미정렬 부분으로 구분

    -- 미정렬 부분에서 첫 번째 데이터를 뽑은 후, 정렬 부분에서 제자리를 찾아 뽑은 데이터를 삽입

 

 

5.4.2 알고리즘

 

InsertionSort ( A[] , n )

입력 : A[ 0.. n-1 ] : 입력 배열

        n : 입력 크기

출력 : A[ 0.. n-1 ] : 정렬된 배열 

{

   for ( i = 1; i < n; i++ )

      {                           // ( n - 1) 번 반복

          val = A [ i ];        // 미정렬 부분 A [ i..n-1 ]의 첫 번째 원소를 선택

          for ( j = i; j > 0 && A [ j -1 ] > val; j-- ) // 정렬 부분에서 제자리 찾기

               A[ j ] = A[ j - 1 ];     // 정렬 부분의 값 A [ j - 1 ] 이 크면 뒤로 한 칸 이동

          A[j]=val ;             // 제 위치에 선택된 원소를 삽입

       }

   returnA;

}

 

5.4.3 성능 분석

InsertionSort ( A[] , n )

{

   for ( i = 1; i < n; i++ )

      {

         val = A[ i ];

         for( j = i; j > 0 && A[ j - 1] > val; j-- )

           A[ j ] = A [ j - 1 ];

         A[ j ] = val;

      }

   returnA;

}   >>>>>>>>>>> 시간 복잡도  O ( n^2 )

 

 

5.4.4 특징 

- 입력이 거의 정렬된 경우 다른 어떤 정렬 알고리즘보다 빠른 수행 시간 O(n)을 가짐

- 안정적인 정렬 알고리즘

- 제자리 정렬 알고리즘 

- 삽입될 위치를 찾기 위해 한 번에 한 자리씩만 이동  

  -- ( 단점 ) 자료의 이동이 여러 번 발생 

 

 

5.5 셸 ( shell sort ) 정렬

5.5.1 개념과 원리

 

>> 삽입 정렬의 단점 보완

   -- “데이터가 삽입될 위치에서 많이 떨어져 있어도 한 번에 한 자리씩만 이동하므로 제자리를 찾아가는 데 느리다.” 

 

>> 기본 아이디어 

  --  멀리 떨어진 원소를 교환하여 처리 속도 향상 

   

     -- 처음에는 멀리 떨어진 두 원소를 비교하여 필요시 위치를 교환하고 점차 가까운 위치의 원소를

        비교∙교환한뒤, 맨 마지막에는 인접한 원소를 비교∙교환하는 방식 

   

    --  입력 배열을 부분배열로 나누어 삽입 정렬을 수행하는 과정을 부분배열의 크기와 개수를 변화시켜 가면서 반복

 

 

5.5.2 알고리즘 

 

입력 : A [ 0.. n-1 ] : 입력 배열

          n : 입력 크기

 

출력 : A [ 0.. n-1 ] : 정렬된 배열

 

 

// 간격의 크기 D를 지정

// D 만큼 떨어진 원소들에 대해 삽입 정렬 수행 

 

 

 

 

 

 

 

 

 

데이터의 개수를 2로 나누면 8 이 나온다.

주어진 입력 배열을 8개 부분배열로 나눈다.

 

and 인접한 원소간의 거리가 8이 되도로 해라.

 

각각의 부분 정렬에서 삽입정렬 실행

 

 

 

위 결과를 모아서 다시 실행

 

위 결과 수행을 위한 D = 8  을 다시 2로 나눈 값 : 4 

 

4개의 부분배열을 만들고,

간격을 4로 한다. 

 

다시 삽입 정렬 수행 

 

위 결과를 모아서 다시 실행

 

위 결과 수행을 위한 D = 4  을 다시 2로 나눈 값 : 2

 

2 개의 부분배열을 만들고,

간격을 2 로 한다. 

 

다시 삽입 정렬 수행 

 

위 결과를 모아서 다시 실행

 

위 결과 수행을 위한 D = 2  을 다시 2로 나눈 값 : 1

 

이웃한 원소들 끼리 비교 

 

 

5.5.3 성능 분석

최악의 경우 : O (n^2)

최선의 경우 : O( nlogn )

 

5.5.4 특징 

- 간격의 크기 D를 계산하는 방식에 따라 성능이 달라짐

 D = n / (2^i) (n:데이터 개수,i=1,2,3,…)

- 가장 좋은 간격을 찾는 것은 미해결 과제

- 간격의 크기 D의 적용은 역순으로 차례대로 사용 

- 안정적이지 않은 정렬 알고리즘이다.

- 제자리 정렬 알고리즘 

 

 

 

 

2020/04/30 - [방송통신대학/알고리즘] - 8강 제 4장 욕심쟁이 알고리즘

8강 제 4장 욕심쟁이 알고리즘