삽입 정렬(揷入整列)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다. 

각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다. 그러므로 다음과 같은 결과가 된다. 

배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.

선택 정렬이나 거품 정렬과 같은 같은 O(n2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

31 25 12 22 11 의 원소들이 있을 때 삽입정렬을 하면,


31 [25] 12 22 11    두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<25> 31 [12] 22 11    세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<12> 25 31 [22] 11    네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
12 <22> 25 31 [11]    마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<11> 12 22 25 31    종료.

소스)

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  for ( i = 1; i < n; i++ )
  {
    remember = data[(j=i)];
    while ( --j >= 0 && remember < data[j] ) data[j+1] = data[j];
    data[j+1] = remember;
  }
}

 

아래는 정렬되는 자료가 단순 데이터일 경우에 memcpy()를 이용하여 자료를 밀어내는 예제이다. memcpy()는 자료를 당겨야하므로 비교를 역순으로 수행한다. 위의 코드보다 25~30% 가량 빠르게 처리된다.

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  i = n-1;
  while ( i-- > 0 )  
  {
    remember = data[(j=i)];
    while ( ++j < n && remember > data[j] );
 
    if ( --j == i ) continue;
    memcpy ( data+i, data+i+1, sizeof(*data) * (j-i) );
    data[j] = remember;
  }
}

출처 : 위키백과

Posted by 파이군
,

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다.
시간 복합도가 O(n2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.
- 출처 : 위키백과

수열 "10 9 4 8 5 1 7" 을 버블 정렬을 이용하여 오름차순으로 정렬하는 방법은 다음과 같다.
결과)



소스)
#define SWAP(x, y) {int t=x; x=y; y=t;}

int main()
{
    int a[7]={10, 9, 4, 8, 5, 1, 7};
    int i, j;

    for (i=1; i<7; i++){
        for (j=0; j<7-i; j++){
            if (a[j] > a[j+1])SWAP(a[j], a[j+1]);
        }
    }

    for (i=0; i<7; i++){
        printf ("%d ", a[i]);
    }

    return 0;
}
다음 수열 "10 9 4 5 6 7 8" 은 두번만에 정렬이 끝나게 된다. 이런경우 나머지 5번의 작업은 의미가 없다.
정렬작업 중 정렬이 다 되었으면 작업을 마치는 방법은 다음과 같다.
결과) 


 소스)

#define SWAP(x, y) {int t=x; x=y; y=t;}

int main()
{
    int a[7]={10, 9, 4, 5, 6, 7, 8};
    int i, j, flag;

    for (i=1; i<7; i++){
        flag=0;
        for (j=0; j<7-i; j++){
            if (a[j] > a[j+1]){
                SWAP(a[j], a[j+1]);
                flag=1;
            }
        }
        if (flag==0) break;
    }

    for (i=0; i<7; i++){
        printf ("%d ", a[i]);
    }

    return 0;
}


Posted by 파이군
,

선택 정렬(選擇整列, selection sort)은 내부정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1.주어진 리스트 중에 최소값을 찾는다.
2.그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3.맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.
-출처 : 위키백과

5개의 정수 95, 75, 85, 100, 50 을 오름차순으로 정렬한다.
결과)



소스)

int main()
{
	int a[5] = {95, 75, 85, 100, 50};
	int i, j, tmp;

	// 정렬
	for (i = 0; i < 4; i++){
		for (j = i + 1; j < 5; j++){
			if (a[i] > a[j]){
				tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}
	}

	//출력
	for (i = 0; i < 5; i++){
		printf("%d ", a[i]);
	}

	return 0;
}
* #define 사용해서 배열의 값을 바꿀수도 있다.

소스)
#define SWAP(a, b) { int t = a; a = b; b = t; } 

int main()
{
    int a[5] = {95, 75, 85, 100, 50};
    int i, j, tmp;

    // 정렬
    for (i = 0; i < 4; i++){
        for (j = i + 1; j < 5; j++){
            if (a[i] > a[j]) SWAP(a[i], a[j]);
       }
   }

    //출력
    for (i = 0; i < 5; i++){
        printf("%d ", a[i]); 
    }

    return 0;
}
내림차순을 할때는 if()의 조건만 반대로 해주면된다. 오름차순으로 정렬된것을 거꾸로 출력하는 방법도 있다.
Posted by 파이군
,