[알고리즘] 우선순위 큐(2) - 예제

[문제1] n개의 양의 정수를 입력받아, 제자리 선택정렬을 하는 프로그램

-배열의 뒷 부분을 정렬 상태로 유지

입력예시                     출력예시

8 2 5 6 8 1 7 3 4

1 2 3 4 5 6 7 8

#include<stdio.h> #include<stdlib.h> void main(){ int *arr; int arrNumber, max, temp; scanf("%d", &arrNumber); arr = (int*)malloc(sizeof(int)*arrNumber); for (int i = 0; i < arrNumber; i++){ scanf("%d", &arr[i]); } for (int i = arrNumber - 1; i >= 0; i--){ max = 0; for (int j = 1; j <= i; j++){ if (arr[j] > arr[max]){ max = j; } } for (int j = 0; j <= i; j++){ if (max == j){ temp = arr[i]; arr[i] = arr[max]; arr[max] = temp; break; } } } for (int i = 0; i < arrNumber; i++) { printf(" %d", arr[i]); } printf("\n"); free(arr); }

[문제2] n개의 양의 정수를 입력받아, 제자리 삽입정렬을 하는 프로그램

- 배열의 앞 부분을 정렬 상태로 유지

입력예시                      출력예시

8 2 5 6 8 1 7 3 4

1 2 3 4 5 6 7 8

#include<stdio.h> #include<stdlib.h> void main(){ int *arr; int arrNumber, temp, j; scanf("%d", &arrNumber); arr = (int*)malloc(sizeof(int)*arrNumber); for (int i = 0; i < arrNumber; i++){ scanf("%d", &arr[i]); } for (int i = 1; i < arrNumber; i++){ temp = arr[i]; j = i-1; while ((j >= 0) && (arr[j] > temp)) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = temp; } for (int i = 0; i < arrNumber; i++) { printf(" %d", arr[i]); } printf("\n"); free(arr); }