삽입 정렬 구현하기

삽입 정렬을 구현해 보았다.

전체 코드

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include "vld.h"

#define MAX_VALUE 30

void insertion_sort(int arr[], int size);
void swap(int* a, int* b);
int* generate_random_arr(int size);
void print_arr(int arr[], int size);

int main(void)
{
	srand((unsigned)time(NULL));
	const int SIZE = 10;
	int* arr = generate_random_arr(SIZE);
	print_arr(arr, SIZE);

	insertion_sort(arr, SIZE);
	print_arr(arr, SIZE);

	free(arr);
}

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void insertion_sort(int arr[], int size)
{
	for (int i = 1; i < size; i++) {
		int j = i - 1;
		int tmp = arr[i];
		while (arr[j] > tmp && j >= 0) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = tmp;
		
	}
}

int* generate_random_arr(int size)
{
	int* arr = (int*)malloc(sizeof(int) * size);
	if (arr == NULL) return NULL;

	for (int i = 0; i < size; i++)
		arr[i] = rand() % MAX_VALUE + 1;
	return arr;
}

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

설명

void insertion_sort(int arr[], int size)

void insertion_sort(int arr[], int size)
{
	for (int i = 1; i < size; i++) {
		int j = i - 1;
		int tmp = arr[i];
		while (arr[j] > tmp && j >= 0) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = tmp;
		
	}
}

주어진 요소마다의 위치를 찾아서 삽입한다.

삽입될 때엔 공간을 마련하기 위해 한 칸씩 뒤로 밀려난다.

실행 결과