정보처리기사 실기 알고리즘 정리 03

01 Aug 2018

Reading time ~6 minutes

정보처리기사 실기 알고리즘 정리 03

10개의 수치 자료를 입력 받아 배열에 저장한 후 저장된 자료를 오름차순으로 정렬하는 순서도를 작성하시오.
(선택 정렬)

알고리즘의 이해

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행.
- 이 설명은 오름차순에 대한 설명, 내림차순이라면 1회전에 가장 큰 값을 찾아 첫 번째 위치에 놓음.
- 회전 : 첫 번째 자료의 위치를 결정하기 위해 첫 번째 자료를 다른 모든 자료와 비교하는 과정.
  - 선택정렬에선 마지막 자료가 자기 자신과 비교하는 것을 생략하므로 자료가 10건이라면 9회전을 수행.
변수
- data[10] : 정렬할 숫자가 저장될 배열
- input_index : 입력 받는 숫자의 개수가 저장될 변수
- i : 정렬 회전 수, 비교 기준 값이 있는 위치를 지정해 주는 변수, 즉 i는 1에서 9까지 차례로 변경됨.
- j : 비교 대상이 있는 위치를 지정해 주는 변수, 즉 j는 i+1에서 10까지 차례로 변경됨.
- tmp : 자료를 교환할 때 사용하는 임시 변수
- x : 정렬된 숫자의 출력 시 배열의 위치를 지정해 주는 변수

main() {
  int input_index, i, j, tmp, x;
  int data[10];
  input_index = -1;

  do {
    input_index++;
    scanf("%d", &data[input_index]);
  } while (input_index < 9);

  i = -1;
  do {
    i++;                          // 비교할 기준 배열요소
    j = i;                       
    do {
      j++;                        // i옆부터 반복해서 비교
      if (data[i] > data[j]) {    // 기준 데이터가 비교 데이터보다 크면 교환. 반복
        tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
      }
    } while(j < 9);
  } while(i < 8);

  for (x = 0; x <= 9; x++)
    printf("%d", data[x]);
}

반복문을 이용한 선택 정렬

main() {
  int m, i, j, temp, x;
  int data[10];

  for (m = 0; m <=9; m++)
    scanf("%d", &data[m]);

  for (i = 0; i <= 8; i++) {
    for (j = i+1; j <= 9; j++) {
      if (data[i] > data[j]) {          // 부등호를 바꿔 올림, 내림차순 변경 가능
        temp = data[i];
        data[i] = data[j];
        data[j] = temp;
      }
    }
  }

  for (x = 0; x <= 9; x++)
    printf("%d ", data[x]);
}

배열의 기억된 10건의 자료를 오름차순으로 정렬하는 순서도를 작성하시오. (버블정렬)

알고리즘의 이해

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를… 이런식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외된다.
2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다.
이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 늘어난다.
- 선택 정렬과 버블 정렬의 차이점
  - 선택정렬은 앞에서부터 정렬됨
  - 버블 정렬은 뒤에서부터 정렬됨
버블정렬의 회전 수
- 처음에 모든 자료들과 비교하는 과정이 1회전, 자료의 개수가 10건이면 10개의 자료를 모두 다른 자료들과 비교하므로 10회전을 수행해야 하지만 마지막 회전에는 비교의 기준과 대상이 모두 자기 자신이므로 의미가 없음.
- 그러므로 자료가 10건이면 9회전만 수행.
변수
- data[10] : 정렬한 숫자가 저장될 배열
- n : 입력 받은 숫자의 개수가 저장될 변수
- i : 정렬 회전 수를 지정할 변수
- j : 각 회전에서의 비교 횟수 및 배열의 위치를 지정할 변수
- tmp : 두 값을 교환할 때 사용할 임시 변수

main() {
  int n, i, j, tmp;          // i는 회전수, j는 각 회전마다 비교할 배열 인덱스
  int data[10];
  n = -1;

  do {
    n++;
    scanf("%d", &data[n]);
  } while(n < 9);

  i = -1;
  do {
    i++;

    j = -1;
    do {
      j++;

      if (data[j] > data[j + 1]) {
        tmp = data[j];
        data[j] = data[j + 1];
        data[j + 1] = tmp;
      }

    } while(j < 8 - i);      // 뒤에서부터 비교를 안하므로, 회전수에 따라 줄여나감.

  } while (i < 8);

  for (int x = 0; x <= 9; x++)
    printf("%d", data[x]);
}

반복문을 이용한 버블 정렬

main() {
  int n, i, j, tmp;
  int data[10];

  n = -1;
  do {
    n++;
    scanf("%d", &data[n]);
  } while (n < 9);

  for (i = 1; i <= 9; i++) {
    for (j = 0; j <= 9 - i; j++) {
      if (data[j] > data[j + 1]) {
        tmp = data[j];
        data[j] = data[j + 1];
        data[j + 1] = tmp;
      }
    }
  }

  for (int x = 0; x < 10; x++)
    printf("%d", data[x]);
}

배열에 기억된 10건의 자료를 오름차순으로 정렬하는 순서도를 작성하시오. 단, 정렬 수행 중 특정 회전에서 정렬을 위한 교환이 한 번도 이루어지지 않으면 정렬이 완료된 것이므로 그 때까지의 교환 횟수와 정렬된 자료를 출력하고 끝낸다.
(버블 정렬2 - 중간 종료)

알고리즘의 이해

버블정렬 수행 중 특정 회전에서의 자료 교환 여부를 검사하려면 특정 회전을 시작하기 전에 플래그 변수(flag)를 초기화 시킨 후 자료가 교환될 떄마다 플래그 변수의 값을 지정해야 함.
그리고 특정 회전을 마친 후 플래그 값을 검사하여 플래그 값이 회전을 시작하기 전의 값과 같다면 자료의 교환이 한 번도 이루어지지 않은 것을 판단하면 됨.
- 프로그램은 자료의 정렬이 끝났는지 알 수 없음. 다음 회전을 수행해 봐야만 자료 교환이 없다는 걸 보고 정렬이 완료되었음을 알 수 있음.
자료의 교환 횟수를 세려면 자료 교환이 일어날 때마다 교환 횟수(cnt)를 1씩 증가시킴.
변수
- data[10] : 정렬한 숫자가 저장될 배열
- n : 입력 받은 숫자의 개수가 저장될 배열
- i : 정렬 회전 수를 지정할 변수
- j : 각 회전에서의 비교 횟수 및 배열의 위치를 지정할 변수
- flag : 자료의 교환 여부를 검사하기 위한 플래그 변수로, flag가 1이면 교환이 발생한 것, 0이면 교환이 발생하지 않은 것
- cnt : 자료의 교환 횟수가 저장될 변수
- tmp : 두 값을 교환하기 위해 값이 임시로 저장될 변수

main() {
  int n, i, j, flag, cnt, tmp;

  int data[10];
  n = -1;

  do {
    n++;
    scanf("%d", &data[n]);
  } while(n < 9);

  cnt = 0;
  
  for (i = 1; i <= 9; i++) {
    flag = 0;
    for (j = 0; j <= (9 - i); j++) {
      
      if (data[j] > data[j + 1]) {
        tmp = data[j];
        data[j] = data[j + 1];
        data[j + 1]  = tmp;
        cnt++;
        flag = 1;    
      }
    }

    if (flag == 0)
      break;
  }

  printf("%d ", cnt);
  
  for (int x = 0; x <= 9; x++)
    printf("%d", data[x]);
}

버블 정렬 기법을 응용하여 한 번은 왼쪽에서 오른쪽으로 진행하면서 최대값을 우측으로 보내고, 한 번은 오른쪽에서 왼쪽으로 진행하면서 최소값을 좌측으로 보내는 방법을 반복하면서 정렬하는 순서도를 작성하시오.
(버블정렬3 - 좌우로 번갈아 가면서 정렬)

알고리즘의 이해

좌우로 번갈아 가면서 버블 정렬을 수행하려면 정렬할 데이터의 시작을 나타내는 위치와 끝을 나타내는 위치를 기억할 변수가 하나씩 있어야 함.
버블 정렬의 특성상 오름차순 정렬인 경우 왼쪽에서 오른쪽으로 1회전의 정렬을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외됨.
2회전에서는 맨 오른쪽 끝의 자료를 제외한 오른쪽 자료에서 왼쪽 방향으로 정렬을 수행하는데, 정렬을 수행하고 나면 가장 작은 자료가 맨 앞으로 이동하므로 다음 회전에서는 맨 앞에 있는 자료가 정렬에서 제외됨.
이렇게 정렬할 데이터의 시작 위치와 끝 위치가 변경되므로 시작과 끝을 기억할 변수가 각각 하나씩 필요할 것.
변수
- d[10] : 정렬할 자료가 저장된 배열, 10개의 숫자가 입력되어 있다고 가정
- n : 입력 받은 숫자의 개수가 저장될 변수
- i : 정렬 회전 수를 지정할 변수
- shift : 왼쪽 또는 오른쪽의 시작 위치를 지정할 변수
- left : 왼쪽 위치가 기억될 변수
- right : 오른쪽 위치가 기억될 변수
- tmp : 두 값을 교환하기 위해 값이 임시로 저장될 변수

main() {

  int n, i, shift, left, right, tmp;
  int d[10] = {8,5,6,2,4,1,3,7,9,10};

  n = 9;
  left = 0;     // 왼쪽 위치가 기억될 변수
  right = n;    // 오른쪽 위치가 기억될 변수

  while (left < right) {                     // 위치를 가리키는게 동일해지면 정렬 끝
    for (i = left; i <= right - 1; i++) {    // 좌->우로 정렬
      if (d[i] > d[i + 1]) {
        tmp = d[i];
        d[i] = d[i+1];
        d[i+1] = tmp;
        shift = i;                          // 마지막으로 교환된 위치를 저장
      }
    }
    right = shift;                          // 그 오른쪽 위치부터 시작하도록 right에 저장
    for (i = right; i >=left + 1; i--) {    // 우->좌로 정렬
      if (d[i-1] > d[i]) {
        tmp = d[i-1];
        d[i-1] = d[i];
        d[i] = tmp;
        shift = i;                         // 마지막으로 교환될 위치를 저장
      }
    }
    left = shift;                          // 그 왼쪽 위치부터 시작하도록 left에 저장
  }

  for (int x = 0; x < 10; x++)
    printf("%d ", d[x]);
}

정보처리기사실기