기본 개념

  • 한 개를 꺼내어 이미 정렬되어 있는 배열 사이에 순서가 맞도록 끼워 넣는 방식이다

  • 삽입 정렬의 i번째 단계가 시작될 때에 배열의 맨 처음 i-1개의 키인 A[0:i-2]는 이미 정렬되어 있다

  • 여기에 A[i-1]를 삽입하여 A[0:i-1]이 정렬되도록 하는 것이 i번째 단계의 목표이다

  • A[i-1]자리에 있던 키가 제자리를 찾을 때까지 A[i-1]보다 큰 값을 갖는 A[i-2], A[i-3], ... 등을 오른쪽으로 한 자리씩 이동시키고 원래 A[i-1]에 있던 키를 이때 생긴 빈 자리에 넣는다

  • 이러한 과정을 n-1회 실행하면 배열이 정렬된다

시간복잡도 O(n^2) 
공간복잡도 O(n)

 

삽입 정렬 예제

 

알고리즘

void InsertionSort(int A[], int n){
/* 입력 : A[0:n] - 정렬할 원소가 있는 배열, n - 정렬할 원소의 개수.
          A[0]는 A[1:n]의 어느 값보다도 더 작은 더미 키이다.
   출력 : A[0:n] - A[0]은 더미 키이고, A[1:n]은 정렬된 배열임. */
   int i, j, Value;
   for (i=2; i<=n ; i++){
  	 Value = A[i];
     j=i;
   	 while(A[j-1] > Value) {
   	    A[j] = A[j-1];
         j--;
  	 }
     A[j]=Value;
   }
}

 

  • 삽입 정렬에서는 키간의 비교 횟수가 키들의 원래 순서에 민감하게 반응한다

  • 키가 내림차순으로 이미 정렬되어 있는 경우 가장 많은 비교를 하게 된다

  • 삽입 정렬의 최악의 경우에 2+3+...+n = n(n+1)/2 -1 번의 비교를 필요로 한다

  • 사용하는 메모리 공간은 배열의 첨자에 쓰이는 변수와 삽일할 키의 값을 잠시 기억하는데 사용하는 변수뿐이므로 제자리 정렬이다

  • 두 개의 동일한 값을 가지는 키의 상대적 위치가 정렬 후에도 변하지 않으므로 안정적인 정렬이다.

 

 

 

참고 : 알고리즘 - 이한출판사

'알고리즘스터디' 카테고리의 다른 글

[알고리즘] 힙 정렬 (Heap Sort)  (0) 2020.08.19
[알고리즘] 쉘 정렬 (Shell Sort)  (0) 2020.08.10
[알고리즘] 퀵 정렬 (Quick Sort)  (0) 2020.08.10
[알고리즘] 버블정렬 (Bubble Sort)  (0) 2020.08.03
[알고리즘] 선택정렬 (Selection Sort)  (0) 2020.08.03

기본 개념

 

  • 버블 정렬 알고리즘은 여러 단계로 나누어진다.

  • 첫째 단계에서 n 개의 키가 왼쪽으로부터 오른쪽으로 검색되면서 모든 인접한 두 개의 키가 서로 비교된다.

  • 인접합 두 개의 키 중에서 왼쪽의 키가 더 크면 오른쪽의 키와 자리를 바꾼다.

  • 첫째 단계가 완료되었을 때 n개의 키중에서 가장 큰 키가 오른쪽 끝으로 옮겨져 A[n-1] 에 있게 된다.

  • 두 번째 단계에서는 A[0:n-2] 가 왼쪽으로부터 오른쪽 방향으로 가면서 차례로 검색된다

  • 역시 모든 인접한 두개의 키가 서로 비교되고 왼쪽의 키가 큰 경우에 오른쪽 키와 자리바꿈 한다

  • 두 번째 단계가 끝나면 두 번째로 큰 키가 A[n-2]에 자리하게 된다.

  • 최악의 경우 이러한 단계를 n-1회를 거치면 배열 전체가 오름차순으로 정렬된다.

  • 실행 시간 단축을 위해 한 단게를 시작하기 전에 바로 전의 단계에서 키의 자리바꿈이 일어났는지 검사하여 자리바꿈이 전혀 일어나지 않은 경우에는 배열이 이미 정렬된 것이므로 다음 단계를 생략한다.

시간복잡도 O(n^2) 
공간복잡도 O(n)

 

버블 정렬 예제

 

알고리즘

void BubbleSort(int A[], int n)
/*입력 : A[0:n-1] - 정렬한 원소가 있는 배열, n - 정렬할 원소의 개수.
  출력 : A[0:n-1] : 정렬된 배열. */
  int i, Sorted;
  Sorted = false;
  while(!Sorted){
  		Sorted=True;
        for(i=1;i<n;i++)
        	if(A[i-1] > A[i]){
            	Swap(&A[i-1], &A[i]);
                Sorted=false;
            }
  	}
}

 

  • 주어진 키가 모두 내림차순으로 이미 정렬되어 있는 경우 최악의 실행시간을 보인다

  • 모든 경우의 단계를 거쳐야만 정렬이 완료되므로 n(n-1)/2회의 비교를 하게 된다

  • 이 때 비교를 할 때마다 n(n-1)/2 회의 자리바꿈이 발생한다

  • 키 사이의 자리바꿈이 발생하지 않고 상수 개의 변수만이 여분으로 필요하므로 안정적인 제자리 정렬이다

 

 

 

 

참고 : 알고리즘 - 이한출판사

 

'알고리즘스터디' 카테고리의 다른 글

[알고리즘] 힙 정렬 (Heap Sort)  (0) 2020.08.19
[알고리즘] 쉘 정렬 (Shell Sort)  (0) 2020.08.10
[알고리즘] 퀵 정렬 (Quick Sort)  (0) 2020.08.10
[알고리즘] 삽입정렬 (Insertion Sort)  (0) 2020.08.03
[알고리즘] 선택정렬 (Selection Sort)  (0) 2020.08.03

기본개념

  • 정렬할 키가 배열 A[0:n-1] 에 저장되어 있다고 가정할 때
  •  가장 작은 키, 둘째로 작은 키, 셋째로 작은 키 등을 순서대로 선택하여 배열의 원소를 재배치시키면서 배열을 정리한다.
  •  n개의 키 중에서 가장 작은 것을 찾아 그 키와 첫째 키인 A[0] 와 자리바꿈 한다.
  •  다음에는 남아 있는 키들 중에서 가장 작은 키를 찾아 그 원소와 A[1] 의 자리를 바꾼다.
  •  i번째 단계에 이르면 A[0:i-2] 에는 가장 작은 i-1 개의 키가 이미 순서대로 정렬되어 있다.
  •  i번째 단게에서는 남아 있는 n-i+1개의 키 중에서 가장 작은 것을 찾아 A[i-1]와 바리를 바꾼다.
  • 이러한 단계를 n-1회 거쳐 배열 전체를 정리한다. 
시간복잡도 O(n^2) 
공간복잡도 O(n)

 

선택 정렬 예제

 

알고리즘

 

void SelectionSort (int A[ ], int n) {
/* 입력 : A[0:n-1] - 정렬할 원소가 있는 배열, n - 정렬할 원소의 개수.
   출력 : A[0:n-1] - 정렬된 배열. */
   int i, j, MinIndex;
   for (i=0; i<n-1;i++) {
   		MinIndex = i;
        for(j = MinIndex+1; j < n; j++)
           if(A[MinIndex] > A[j])
           	 MinIndex = j;
        if(MinIndex != i)
           swap(&A[i], &A[MinIndex]);
   }
}

 

  • 선택 정렬은 간단하며 레코드 수가 작은 경우에 효율적, 정렬 과정에서 모든 키는 자신의 자리를 찾은 후에는 자리 이동을 하지 않는다.
  • 키의 비교 횟수를 살펴보면, 가장 작은 키를 고르는 데 n-1 , 두 번째로 작은 키를 고르는데  n-2회의 비교를, 일반적으로 i번째 작은 키를 고르는 데 n-i 회의 비교를 하게 되므로
  • (n-1) + (n-2) + ... +1=n(n-1)/2 회의 키 비교를 하게 된다.
  • i번째 단계에서는 항상 n-i 회의 비교를 하므로 알고리즘의 실행 시간은 입력 자료의 순서에 민갑하지 않다.
  • 3~4개의 변수 외에는 별도의 메모리 공간을 차지하지 않는 제자리 정렬 이다.

 

 

 

 

 

 

참고 : 알고리즘 - 이한출판사

 

'알고리즘스터디' 카테고리의 다른 글

[알고리즘] 힙 정렬 (Heap Sort)  (0) 2020.08.19
[알고리즘] 쉘 정렬 (Shell Sort)  (0) 2020.08.10
[알고리즘] 퀵 정렬 (Quick Sort)  (0) 2020.08.10
[알고리즘] 삽입정렬 (Insertion Sort)  (0) 2020.08.03
[알고리즘] 버블정렬 (Bubble Sort)  (0) 2020.08.03

+ Recent posts

티스토리툴바