insertion sort - c

삽입정렬을 c로 구현해봤다. 이진탐색을 구현하면서 포인터에 익숙해진터라 좀 더 수월하게 작업했다.

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <time.h>

int* scaffolding(int);

void print_array(int *, int);

void insertionsort(int *, int);

int main() {

int *x, n, i;

printf("배열 크기 : ");

scanf("%d", &n);

x = scaffolding(n);

printf("입력 : ");

print_array(x, n);

insertionsort(x, n);

printf("결과 : ");

print_array(x, n);

return 0;

}

void insertionsort(int *x, int n) {

int i, j;

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

for(j = i; j > 0 && x[j-1] > x[j]; --j){

int temp = x[j-1];

x[j-1] = x[j];

x[j] = temp;

}

}

}

void print_array(int *x, int n) {

int i;

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

printf("%d ", x[i]);

printf("\n");

}

int* scaffolding(int n) {

srand((unsigned) time(NULL));

int *x, i;

x = (int *)malloc(n * sizeof(int));

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

x[i] = rand() % n;

return x;

}

위의 삽입정렬에서 배열의 값을 swap 해주는 부분만 알고리즘을 바꿔봤다.
메모리에 쓰는 작업을 덜하기 때문에 좀 더 효율적이다.

void insertionsort(int *x, int n) {

int i, j, temp;

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

temp = x[i];

for(j = i; j > 0 && x[j-1] > temp; --j)

x[j] = x[j-1];

x[j] = temp;

}

}