정렬(Sort)의 개념과 기법 - 정보올림피아드 문제풀이

데이터 정렬(Sort)과 탐색(Search)은 컴퓨터 시스템의 가장 기본적인 기능으로 데이터베이스, 웹 검색, 단순 입력창에 이르기까지 다양한 영역에서 사용하는 것이므로 꼭 알아두어야 할 개념입니다. 퍼스널 컴퓨터가 등장하기 이전 부터 데이터 정렬은 여러 형태로 발전되어 왔는데 예전에는 메모리가 크지 않은 환경이었으므로 이런 제약적인 환경에서도 활용할 수 있는 알고리즘부터 최대한 검색 시간을 줄이기 위하여 검색을 감안하여 정렬된 데이터로 보관하는 기법까지 다양한 알고리즘이 존재합니다. 이런 알고리즘의 복잡도는 O(빅오 Big-Oh)로 표시합니다.

■ 버블 정렬(Bubble sort)

한쪽 방향으로 이동하면서 인접한 두원소를 비교하여 그 방향 맨 끝에 가장 큰수 또는 가장 작은수를 배치하고 다음번에는 동일 방향과 방식으로 직전에 가장 크거나 작은수 이전까지 배치 하는 방식을 반복하는 정렬 방법입니다. 데이터가 정렬되는 과정이 거품이 표면으로 몰리는 것과 같은 모습이라 해서 버블 소트라 합니다. 시간 복잡도는 로 정렬 알고리즘 중에 느린 편에 속합니다. 공간 복잡도는 0으로 정렬에 필요한 별도의 공간은 필요없고, 같은 값인 경우 원래 순서를 유지합니다(안정성)

void print_data(int dat[], int size)
{
  int i;
  
  printf("\n");
  for (i = 0; i < size; i++) {
    printf("%3d", dat[i]);
  }
}

main()
{
  int loop, i, tmp;
  int data[] = { 10, 3, 34, 5, 26, 4, 1, 6, 9, 19 };
  int datasize = sizeof(data) / sizeof(int);
  
  for (loop = datasize-1; loop>0; loop--) {
    print_data(data, datasize);
    for (i = 0; i < loop; i++) {
      if (data[i] > data[i+1]) {
        tmp = data[i];
        data[i] = data[i+1];
        data[i+1] = tmp;
      }
    }
  }
}

위의 코드를 보면 바깥 루프는 비교의 종착점을 관리하여 정렬이 완성된 원소에 대해서는 더이상 비교하지 않도록 합니다. 내부의 for 루프는 인접한 두원소를 비교하여 앞 쪽 원소 값이 크면 뒤로 보낼 수 있도록 자리 바꿈(swap)을 반복합니다. 위의 코드를 실행 시킨 결과는 아래와 같습니다.

위의 결과를 보면 일곱번째 부터는 자리 바꿈이 일어나지 않고 있으므로 이런 상황을 감안하여 플래그를 두어 불필요한 비교 과정을 생략하면 좀더 효과적인 로직이 될 수 있습니다.

■ 선택 정렬(Selection sort)

데이터를 한쪽 방향으로 검색하면서 검색 시작 위치에 가장 큰 값 또는 가장 작은 값을 찾아 배치시키고 다음 스텝에서는 시작 위치를 다음으로 옮겨 같은 방식으로 가장 큰/작은 값을 선택하여 정렬하는 방식입니다. 버블 소트처럼 의 시간 복잡도를 가지지만 데이터 자리바꿈(swap)을 최소화해서 속도는 버블소트 보다 상당히 빠릅니다. 공간 복잡도는 0으로 정렬에 필요한 별도의 공간은 필요없습니다, 같은 값인 경우 원래 순서를 유지 못할 가능성이 있습니다.(불안정성)

main()
{
  int loop, i, tmp, min;
  int data[] = { 10, 3, 34, 5, 26, 4, 1, 6, 9, 19 };
  int datasize = sizeof(data) / sizeof(int);
  
  for (loop = 0; loop < datasize - 1; loop++) {
    print_data(data, datasize);
    min = loop;
    for (i = loop + 1; i < datasize; i++) {
      if (data[i] < data[min]) {
          min = i;
      }
    }
    if (min != loop) {
      tmp = data[min];
      data[min] = data[loop];
      data[loop] = tmp;
    }
  }
  print_data(data, datasize);
}

코드를 보면 최소값을 찾는 로직이 주이고 데이터 교환은 시작 위치보다 작은 값을 찾은 경우에만 발생하므로 최소의 데이터 이동으로 정렬할 수 있습니다. 아래의 그림은 선택 정렬을 수행한 결과입니다.

■ 삽입 정렬(Insertion sort)

새로 추가되는 자료가 위치할 곳을 찾아 삽입하고 나머지 자료는 뒤로 미는 방식으로 정렬합니다. 기존 배열을 정렬할 경우에는 두번째 자료부터 차례로 새로 추가될 데이터로 간주하고 그 앞쪽의 자료들은 정렬되어 있는 자료로 간주할 수 있습니다. 버블소트, 선택소트 처럼 의 시간 복잡도를 가지지만 속도는 가장 빠른 편입니다. 공간 복잡도는 0으로 정렬에 필요한 별도의 공간은 필요없고, 같은 값인 경우 원래 순서를 유지합니다. 단, 삽입 위치 이후를 뒤로 미는 작업 때문에 각 원소의 크기나 배열 상태에서 따라 편차가 큽니다.

main()
{
  int loop, i, tmp;
  int data[] = { 10, 3, 34, 5, 26, 4, 1, 6, 9, 19 };
  int datasize = sizeof(data) / sizeof(int);
  
  for (loop = 1; loop < datasize; loop++) {
    print_data(data, datasize);
    for (i = 0; i < loop; i++) {
      if (data[i] > data[loop]) break;
    }
    if (i < loop) { //found
      tmp = data[loop];
      memmove(&data[i+1], &data[i], sizeof(int) * (loop - i));
      data[i] = tmp;
    }
  }
  print_data(data, datasize);
}

위의 코드를 보면 data[loop]를 새로 추가되는 데이터로 간주하여 삽입 위치를 찾고 memmove 함수를 통해서 뒤로 미는 작업을 확인할 수 있습니다. 아래는 프로그램을 실행한 결과로 바깥 루프가 반복되면서 부분 정렬 그룹이 커지는 것을 확인할 수 있습니다.

■ 쉘 정렬(Shell sort)

쉘 정렬은 1959년 Donald shell에 의해서 처음 만들어졌다고 해서 붙여진 이름이며 데이터를 그룹으로 나누어 그룹내에서 삽입 정렬하고 다음 스텝에서는 그룹의 크기를 줄여 정렬하고 최종적으로는 전체를 삽입 정렬하는 방식으로 수행합니다. 데이터가 일정 순서로 배열되어 있는 경우 효율성이 매우 높은 삽입 정렬의 장점을 활용한 것으로 창안자 Shell의 경우 그룹의 크기를 N/2, N/4.....1의 방식으로 적용했으나 많은 연구자들이 이 값을 다르게 적용해서 효율을 좀더 높이고자 했습니다. 가장 최근 연구에서는 Ciura가 실험적 방식으로 701, 301, 132, 57, 23, 10, 4, 1의 값을 제안 했습니다. Ciura 방식의 쉘정렬 코드 예제와 실행 결과입니다.

void shell_sort_pass(int data[], int datasize, int grpval) {
  int i, j, insert, blk, tmp;

  blk = (datasize / grpval) * grpval;
  for (i=0; i < datasize; i++) {
    insert = data[i];
 
    for (j = i - grpval; j >= 0; j -= grpval) {
      if (data[j] <= insert) break;
        data[j + grpval] = data[j];
    }
    if (i != (j+grpval)) data[j + grpval] = insert;
  }
}

main() 
{
  int grpsize[] = {701, 301, 132, 57, 23, 10, 4, 1};
  double ciura_parameter = 2.3;
  int data[] = { 10, 3, 34, 5, 26, 4, 1, 6, 9, 19 };
  int datasize = sizeof(data) / sizeof(int);
  int grpidx = 0;
  int grpval = grpsize[0];
  
  //check first group size
  if (datasize > grpval) {
    while(datasize > grpval) {
      grpidx--;
      grpval = (int)(grpval * ciura_parameter);
    }
  } else {
    while(datasize < grpval) {
      grpidx++;
      grpval = grpsize[grpidx];
    }
  }

  print_data(data, datasize);
  while (grpval > 1) {
    grpidx++;
	if (grpidx >= 0) {
	  grpval = grpsize[grpidx];
	} else {
	  grpval = (int)(grpval/ciura_parameter);
	}

    shell_sort_pass(data, datasize, grpval);
    print_data(data, datasize);
  }
}

코드와 결과를 보면서 설명드리면 입력 데이터의 크기가 10이므로 예제에서는 그룹크기 4와 1로 정렬을 수행합니다. 그룹을 나누는 값 4를 간격으로 (10, 26, 9), (3, 4, 19), (34, 1), (5, 6)를 그룹으로 해서 삽입 정렬을 수행하고 최종적으로는 삽입 정렬과 동일한 방식이 적용됩니다. 주목할 점은 최종 단계에 들어서기 전에 데이터가 상당부분 정렬되어 있다는 점이고 정렬 대상이 클수록 효율성의 차이를 보일 것입니다. main 함수를 보면 본격적인 정렬에 들어가기 앞서 최초 그룹의 크기를 정하는 작업을 수행하는데 701보다 큰 값의 경우에는 2.3이라는 파라미터를 곱해서 그룹 크기를 정하고 있음을 확인할 수 있습니다.

시간 복잡도는부터 까지 그룹을 나누는 값에 따라 다양하지만 공간 복잡도는 0으로 추가 메모리가 필요 없으면서도 빠른 속도를 가지고 있어 임베디드 시스템등에서 사용하는 편입니다. 같은 값인 경우 원래 순서를 유지하지 못하는 특성이 있습니다.(불안정성) 

■ 퀵 정렬(Quick sort)

대표적인 정렬 알고리즘으로 임의의 한 값을(피벗, pivot) 기준으로 한 쪽은 기준보다 작은것, 한 쪽은 기준보다 큰 것으로 좌우를 나누고(분할, partition) 양쪽을 같은 방식으로 재귀적으로 호출하는 것을 반복함으로 정렬합니다. 기준값(피벗)의 위치는 공정되어 양쪽의 데이터가 1일때 까지 반복하는데 효율을 높이기 위해서 좌우 그룹이 일정 개수 이하인 경우에는 삽입 정렬로 재귀 호출을 대신하기도 합니다. 또한 어떤 값을 기준(피벗)으로 선택하는가에 따라 효율이 달라지기 때문에 난수를 통해서 선택하기도 하고 좌우끝이나 중간등 일정한 위치로 피벗을 정하기도 합니다. 복잡도는 시간 복잡도외에 의 추가 메모리가 있어야 하고 평균적으로는 의 복잡도를 보이고 최악은 의 복잡도를 갖습니다. 같은 값인 경우 원래 순서를 유지하지 못하는 특성이 있습니다.

void print_data(int dat[], int sta, int end)
{
  int i;
  
  printf("\n%d~%d : ", sta, end);
  for (i = 0; i < sta; i++) printf("   "); 
  for (i = sta; i <= end; i++) printf("%3d", dat[i]); 
}

void swap(int data[], int idx1, int idx2)
{
  int tmp;
  
  tmp = data[idx1]; 
  data[idx1] = data[idx2]; 
  data[idx2] = tmp;
}

int partition( int data[], int sta, int end) 
{
  int pivot, i, j, tmp;
   
  pivot = data[sta];
  i = sta; 
  j = end + 1;
		
  while (1) {
    do ++i; while ( data[i] <= pivot && i <= end );
    do --j; while ( data[j] > pivot );
    if( i >= j ) break;
    swap(data, i, j);
  }
  swap(data, sta, j);
  return j;
}

void quicksort( int data[], int sta, int end)
{
   int pivot;

   if( sta >= end ) return; 
   pivot = partition( data, sta, end);
   print_data(data, sta, end);
   quicksort( data, sta, pivot - 1);
   quicksort( data, pivot + 1, end);
}

main()
{
  int data[] = { 10, 3, 34, 5, 26, 4, 1, 6, 9, 19 };
  int datasize = sizeof(data) / sizeof(int);
  
  print_data(data, 0, datasize - 1);
  quicksort(data, 0, datasize - 1);
  print_data(data, 0, datasize - 1);
}

위의 예제 코드는 피벗으로 정렬 대상의 맨 좌측을 선택하는 방식입니다. 실행 결과를 보면 10, 1, 3, 9, 4, 5, 26를 피벗으로 사용했습니다. 

■ 힙 정렬(Heap sort)

힙(Heap)은 최대값 또는 최소값을 빠르게 찾기 위해 만들어진 트리구조로 부모 노드가 자식 노드 보다 항상 큰 값을 가지는 힘을 최대힙, 부모 노드가 자식 노드 보다 항상 작은 값을 가지는 힙을 최소힙이라 합니다. 많은 경우 차수가 2인 이진 힙을 사용하며 이진 힙을 사용하는 정렬 기법을 힙 정렬이라고 합니다. 선택 정렬의 개선된 형태로도 볼 수 있는 것이 최대값 또는 최소값을 힙구조를 통해서 찾아서 정렬된 영역으로 옮기고 비정렬 영역에서 최대/최소값을 찾아 정렬된 영역으로 옮기는 작업을 반복하는 방식으로 정렬합니다. 부가적인 공간이 필요 없으며 시간 복잡도는  를 보이고 같은 값인 경우 원래 순서를 유지하지 못할 수 있습니다. 이진 힙을 데이터 배열에 저장했을때 루트는 0이고 노드 N의 좌측 자식 노드는 2N+1, 우측 자식 노드는 2N+2, 부모 노드는 (N-1)/2를 활용합니다.

#define LEFT(N)   (2*(N) + 1)
#define RIGHT(N)  (2*(N) + 2)
#define PARENT(N) ((N-1) / 2)
#define SWAP(i, j) tmp = data[i]; data[i] = data[j]; data[j] = tmp

main()
{
  int node, i, tmp;
  int data[] = { 10, 3, 34, 5, 26, 4, 1, 6, 9, 19 };
  int datasize = sizeof(data) / sizeof(int), sortsize;
  
  print_data(data, datasize);
  //make max heap
  for (i = 0; i < datasize; i++) {
    node = i;
    while (data[PARENT(node)] < data[node]) {
      SWAP(PARENT(node), node);
      node = PARENT(node);
    }
  }
  print_data(data, datasize);
  
  sortsize = datasize;
  while (sortsize > 0) {
    SWAP(0, sortsize - 1);
    sortsize --;
 
    node = 0;     // 0 = new entry, keep max heap
    while (1) {
 	    if (LEFT(node)  < sortsize && data[node] < data[LEFT(node)] &&
 	        (RIGHT(node) >= sortsize || data[LEFT(node)] >= data[RIGHT(node)])) {
 	      SWAP(node, LEFT(node));
 	      node = LEFT(node);
 	    } else if (RIGHT(node) < sortsize && data[node] < data[RIGHT(node)]) {
 	      SWAP(node, RIGHT(node));
 	      node = RIGHT(node);
 	    } else {
 	      break;
 	    }
 	  }
 	  print_data(data, datasize);
  }
  print_data(data, datasize);
}

코드를 보면 우선 MAC HEAP을 제작합니다. 그리고 루트에 올라온 최대값을 정렬된 영역으로 옮기면서 새로운 값을 루트에 두고 새로운 값이 MAX HEAP에 맞도록 위치를 찾아가도록 하면 다시 MAX HEAP이 유지되어 루트에 있는 최대값을 옮기고 새로운 값에 대하여 위치를 찾아가는 작업을 반복하여 데이터를 정렬합니다.

■ 병합 정렬(Merge sort)

가장 오래된 정렬 알고리즘의 하나로 메모리의 크기 보다 상당히 큰 파일을 N개로 나누어 정렬하는 외부 병합 정렬은 메모리 허용 공간으로는 퀵소트와 같은 빠른 알고리즘을 사용하여 정렬하고 정렬된 블럭을 병합 정렬을 통해서 정렬합니다. 병합 정렬은 데이터를 원소가 1개이하의 그룹일때 까지 나누고 각 그룹을 재귀적으로 합치면서 정렬합니다. 

void mergesort(int data[], int datasize, int temp[]) {
  int i, j, t;
  
  if (datasize <= 1) return;
  mergesort(data, datasize/2, temp);
  mergesort(data + datasize/2, datasize - datasize/2, temp);
  
  i = 0;
  j = datasize/2;
  t = 0;
  while (i < datasize/2 && j < datasize) {
      if (data[i] <= data[j])
          temp[t++] = data[i++];
      else
          temp[t++] = data[j++];
  }
  //remainder
  while (i < datasize/2) temp[t++] = data[i++];
  while (j < datasize) temp[t++] = data[j++];
  memcpy(data, temp, datasize * sizeof(int));
}

블럭을 2개가 아니라 N개로 나누어 병합하기도 하고 블럭을 1개 이하가 아니라 일정 수 이하인 경우에는 삽입 소트등으로 정렬하기도 합니다.  의 시간 복잡도를 보이고  의 추가 공간을 필요로 합니다. 같은 값인 경우 원래 순서를 유지하는 안정성이 있습니다.

■ 기수 정렬(Radix sort)

데이터 항목간 비교가 아니라 N진법의 각 자리수를 기준으로 정렬하는 방식으로 10진수라면 1의 자리, 10의 자리, 100의 자리 수으로 정렬합니다.

void radixsort(int data[], int datasize) {
	int i, max = data[0], exp = 1, base = 10;
	int tmp[datasize], bucket[base];
 
	for (i = 1; i < datasize; i++) {
		if (data[i] > max) max = data[i];
	}
 
	while (max / exp > 0) {
		memset(bucket, 0, base * sizeof(int));
 
		for (i = 0; i < datasize; i++) {
			bucket[(data[i] / exp) % base]++;
		}
 
		for (i = 1; i < base; i++) {
			bucket[i] += bucket[i - 1]; 
		}
 
		for (i = datasize - 1; i >= 0; i--) {
			tmp[--bucket[(data[i] / exp) % base]] = data[i];
		}
		memcpy(data, tmp, datasize * sizeof(int));
		exp *= base;
		print_data(data, datasize);
	}
}

main()
{
  int data[] = { 10, 3, 34, 5, 26, 4, 1, 6, 9, 19 };
  int datasize = sizeof(data) / sizeof(int);
  
  
  print_data(data, datasize);
  radixsort(data, datasize);
}

위의 코드를 보면 exp는 1, 10, 100등으로 변하면서 각 자리수를 지칭하고 각 자리수별로 동일한 값을 버킷으로 관리하여 간편한 방법으로 데이터를 정렬합니다. 정수값에만 사용할 수 있는 한계가 있지만 간단하고 빠른 성능을 보입니다. 의 추가 공간을 필요로 하고 의 시간 복잡도를 가집니다. 같은 값인 경우 원래 순서를 유지하는 안정성이 있습니다.

■ 연관 문제 풀이

1. 다음의 정렬 방법 중 최악의 경우(worst case) 가장 빠른 속도를 갖는 것은?

(1) 선택 정렬(selection sort)

(2) 삽입 정렬(insertion sort)

(3) 쉘 정렬(shell sort)

(4) 퀵 정렬(quick sort)

(5) 힙 정렬(heap sort)

※쉘 정렬과 퀵 정렬의 경우에도 최악의 경우에는 시간 복잡도가 선택, 삽입 정렬과 같다는 점에 주의합니다.

2. 다음은 삽입정렬(insert sort)하는 프로그램의 일부이다. 빈 칸에 알맞은 것은?

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

  j = i; temp = a[i];

  while(j > 0 && a[j-1] > temp) {

    ____________________________   

  }

  a[j] = temp;

}

(1) a[j] = a[j+1]; j++; (2) a[j] = a[j+1]; j--; (3) a[j+1] = a[j]; j--; (4) a[j] = a[j-1]; j++; (5) a[j] = a[j-1]; j--; 

※두번째 항목부터 새로 추가될 항목으로 간주하여 해당 값 보다 큰 값을 뒤로 밀고 비교하는 작업을 동시에 수행하는 알고리즘입니다. 루프가 0보다 클동안 반복하는 것을 보면 오른쪽부터 거꾸로 내려옴을 확인할 수 있습니다.

3. 다음은 주어진 수를 오름차순으로 정렬하는 프로그램의 일부이다. 빈 칸에 알맞은 것은? 

for ( i = 0; i < 10; i++ )

{

  tmp = a[i];

  for ( j = i - 1; j >= 0; j-- )

    if ( a[j] > tmp ) ________________;

    else break;

  a[j + 1] = tmp;

}

① a[j] = a[j + 1]  ② a[j + 1] = a[j]  ③ a[j] = a[i] ④ a[j + 1] = a[i]  ⑤ a[i + 1] = a[j]

※삽입위치를 찾아 그 뒤에 있는 항목들은 뒤로 미는 삽입정렬입니다.

4. a 배열에는 10이하인 자연수가 10개 담겨 있다. b 배열에 결과 값이 담긴다고 할 때, 다음 함수는 무엇을 하는 함수인가?

void f ()
{
  int i;
  
  for ( i = 1; i <= 10; i++) c[i] = 0;
  for ( i = 1; i <= 10; i++) c[a[i]]++;
  for ( i = 2; i <= 10; i++) c[i] += c[i-1];
  for ( i = 1; i <= 10; i++) {
    b[c[a[i]]] = a[i];
    c[a[i]]--;
  }
}

① 각 숫자의 빈도수를 구하는 프로그램 ② 오름차순으로 정렬하는 프로그램 ③ 내림차순으로 정렬하는 프로그램  ④ 작은 순으로 등수를 구하는 프로그램 ⑤ 큰 순으로 등수를 구하는 프로그램

※기수 정렬을 참조해 보시면 c 배열은 버킷을 만드는 과정임을 확인할 수 있습니다. 값을 끄집어 내는 과정을 1->10 방향으로 수행했으므로 오름차순 정렬입니다. 

5. 배열 A(또는 a)에는 N개의 자연수가, 배열 B(또는 b)에는 M개의 자연수가 오름차순으로 정렬되어 들어있다. 이 둘을 합쳐 오름차순으로 정렬된 결과를 배열 C(또는 c)에 담는 프로그램을 작성하려 한다. 다음 빈 칸에 알맞은 것은? 

 pa = pb = pc = 0; 

 while ( pa < N && pb < M ) 

 {

   if ( a[pa] < b[pb] ) {

     c[pc] = a[pa]; 

     pc++; pa++;

   }  else  {

     c[pc] = b[pb];

     pc++; pb++;

   }

 }

 if (________)

  for ( i = pa; i < N; i++ ) [pc++] = a[i]; 

 else 

  for ( i = pb; i < M; i++ ) [pc++] = b[i]; 

① pa < N  ② pa <= N ③ pa == N  ④ pa >= N  ⑤ pa > N  

※병합 정렬 알고리즘이고 괄호 부분은 나머지를 처리하는 부분입니다. true 영역이 pa를 참조하고 있음을 주의해야 합니다.

2006

6. 다음과 같이 정렬되어 있는 배열에서 이진 탐색(binary search)으로 10의 위치를 찾고자 한다. 10을 찾기까지 찾은 10을 포함해서 몇 개의 수를 10과 비교하는가?

1, 3, 4, 7, 10, 12, 14, 17, 23, 31, 37, 42, 45, 57, 63

① 3개   ② 4개   ③ 5개   ④ 6개   ⑤ 7개

※오름차순으로 정렬되어 있는 배열의 중간 위치 값과 비교하여 작으면 우측 크면 좌측을 동일한 방식으로 중간값과 비교해서 찾아가는 방식이 이진 탐색 입니다. 총 개수가 15이므로 중간 위치 7의 값 17, 같은 방식으로 7, 12, 10을 차례로 비교합니다.

7. 다음은 오름차순으로 정렬되어 있는 두 배열 a와 b를 합쳐 오름차순으로 정렬된 하나의 배열 c를 만드는 프로그램의 일부이다. 배열 a에는 M개의 수가 a[1]부터 a[M]까지, 배열 b에는 N개의 수가 b[1]부터 b[N]까지 들어 있고, MAX는 이 모든 수보다 더 큰 수라고 할 때 빈 칸에 들어갈 내용으로 가장 알맞은 것은?

p = q = 1; r = 0;

a[M + 1] = b[N + 1] = MAX;

while (______ ) {

  r++;

  if ( a[p] < b[q] ) {

    c[r] = a[p]; p++;

  } else {

    c[r] = b[q]; q++;

  }

}

① p < M || q < N   ② p < M && q < N   ③ p <= M && q <= N

④ p <= M || q <= N   ⑤ p + q <= M + N

※약간 다른 방식으로 구현한 병합 정렬입니다. 앞서 소개된 병합정렬은 나머지 처리 부분이 있는데 병합 대상 끝에 MAX 값을 두어서 별도의 나머지 처리 로직을 제거한 알고리즘입니다.

 

8. 다음 프로그램은 둘 다 a와 b의 값을 서로 바꾸어 주는 swap 함수를 구현한 것이다. 빈 칸에는 보기 중 하나의 문장이 들어간다고 할 때 다음 보기 중 어느 곳에도 들어가는 내용이 아닌 것은? 

void swap( int &a, int &b )

{

  a = a + b;

  ________;

  ________;

}

void swap( int &a, int &b )

{

  a = a - b;

  ________;

  ________;

}

① a = a - b  ② a = b - a  ③ b = a + b  ④ b = a - b  ⑤ b = b - a

※정렬에서 많이 사용하는 SWAP을 임시 변수를 사용하는 방식이 아닌 정수 연산으로 구현한 것으로 첫번째는 b=a-b; 앞선 연산을 감안하면 b=a+b-b; 이므로 결과적으로 b=a;의 효과를 냅니다. a=b;의 효과는 내려면 a=a-b입니다. 두번째 문장을 감안하면 a=a+b-a이므로 a=b가 됩니다. 두번째는 b=a+b; a=b-a입니다.

9. 30, 15, 10, 25, 5, 20을 인접한 두 수들만 교환하여 5, 10, 15, 20, 25, 30과 같이 크기 순서대로 정렬하고자 한다. 최소 교환 횟수는 얼마인가?

① 8 ② 10 ③ 11 ④ 12 ⑤ 13

※버블소트의 알고리즘을 확인하세요. 첫 스텝에서 30이 맨 우측으로 가면서 5회의 교환이 발생하고, 다음 스텝에서는 (15,10)과 (25, 5), (25,20) 교환이 발생하면 25가 정렬됩니다. 10, 15, 5, 20가 미정렬 상태에서 다음 스템에서는 (15, 5) 교환이 이루어 지고 최종 교환은 (10,5)입니다. 총 10회입니다.

10. 배열 a에 a[1]부터 a[9]까지 임의의 9개의 정수가 들어가 있을 때, 그 중간값을 구하여 출력하는 프로그램을 아래와 같이 작성하였다. 단, 중간값은 배열 a의 원소들을 크기 순서대로 정렬하였을 때 a[5]에 저장되는 값을 의미한다.

for (i = 1 ; i <= 9 ; i++) {

    c1 = 0; c2 = 0;

    for (j = 1 ; j <= 9 ; j++) {

        if (a[j] ㉠ a[i]) c1++;

        if (a[j] ㉡ a[i]) c2++;

    }

    if (c1 >= ㉢ && c2 >= ㉣) {

        mid = a[i];

        break;

    }

}

printf("%d\n", mid);

 다음의 보기에서 ㉠~㉣에 들어갈 수 있는 내용이 알맞게 짝지어진 것을 모두 고르면?

가. ㉠ < ㉡ > ㉢ 4 ㉣ 4  나. ㉠ < ㉡ >= ㉢ 4 ㉣ 5  다. ㉠ <= ㉡ > ㉢ 5 ㉣ 4  라. ㉠ <= ㉡ >= ㉢ 5 ㉣ 5

① 가   ② 라   ③ 나, 다  ④ 나, 다, 라  ⑤ 가, 나, 다, 라

※정렬 알고리즘과 비슷한데 각 위치에 값을 대입해서 확인하셔야 합니다. i로 루프를 돌리면서 a[i]를 검사 후보로 해당 값보다 작거나 큰 값이 균형을 이루도록 해야 하므로 문제는 기준값과 동일한 값의 처리가 문제이므로 가, 나, 다, 라 모두 답이 됩니다.