PTA_2019春_ツールバーの
3002 ワード
/* */
/* , , , , , ( )*/
/* , , , */
#include
#include
void swap(int *a ,int * b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void bubblesort(int* data, int N) {
int i;
for (int p = N-1; p >= 0; p--) {
int flag = 0;
for (i = 0; i < p; i++) {
if (data[i] > data[i + 1]) {
swap(&data[i], &data[i + 1]);
flag = 1;
}
}
if (flag == 0) break;
}
}
void insertsort(int* data, int N) {
int p,i;
int temp;
for (p = 1; p < N; p++) {
temp = data[p];
for (i = p; i >= 0&&data[i-1]>temp; i--) {
data[i] = data[i - 1];
}
data[i] = temp;
}
}
void shellsort(int* data, int N) {
}
void simpleselectsort(int* data, int N) {
int p, i;
int min;
for (p = 0; p < N-1; p++) {
min = p;
for (i = p + 1; i < N; i++) {
if (data[i] < data[min]) {
min = i;
}
}
swap(&data[p], &data[min]);
}
}
void perdown(int* data, int N, int p) {
int parent, child;
int x;
x = data[p];
for (parent = p; (parent * 2 + 1) < N; parent = child) {
child = parent * 2 + 1;
if ((child != N - 1) && (data[child] < data[child + 1])) {
child++; /*child */
}
if (x >= data[child]) break;
else {
data[parent] = data[child];
}
}
data[parent] = x;
}
void heapsort(int* data, int N) {
int i;
for (i = N / 2 - 1; i >= 0; i--) {
perdown(data, N, i);
}
for (i = N - 1; i > 0; i--) {
swap(&data[0], &data[i]);
perdown(data, i, 0);
}
}
void merge1(int* data, int* tempdata, int L, int R, int rightend) {
int leftend, temp, numelements;
int i;
leftend = R - 1;
temp = L;
while (L <= leftend && R <= rightend) {
if (data[L] < data[R]) {
tempdata[temp++] = data[L++];
}
else tempdata[temp++] = data[R++];
}
while (L <= leftend) {
tempdata[temp++] = data[L++];
}
while (R <= rightend) {
tempdata[temp++] = data[R++];
}
}
void merge_pass(int * data,int * tempdata,int N,int length) {
int i,j;
for ( i = 0; i < N - 2 * length; i += 2 * length) {
merge1(data, tempdata, i, i + length, i + 2 * length - 1);
}
if (i + length < N) {
merge1(data, tempdata, i, i + length, N-1);
}
else {
for (j = i; j < N; j++) {
tempdata[j] = data[j];
}
}
}
void mergesort(int* data, int N) { /* */
int length = 1;
int* tempdata = (int*)malloc(N * sizeof(int));
while (length < N) {
merge_pass(data, tempdata, N, length);
length *= 2;
merge_pass(tempdata, data, N, length);
length *= 2;
}
free(tempdata);
}
int main() {
int N;
scanf("%d", &N);
int* array = (int* )malloc(N * sizeof(int));
for (int i = 0; i < N; i++) {
scanf("%d", &array[i]);
}
//bubblesort(array, N);
//insertsort(array, N);
//simpleselectsort(array, N);
//heapsort(array, N);
mergesort(array, N); /* */
for (int i = 0; i < N; i++) {
printf("%d", array[i]);
if (i != N - 1) {
printf(" ");
}
}
return 0;
}