쉽게 짠 구조체 Insertion Sort

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

#define MAX_TABLE 10
#define MAX_GROUP 5
#define MAX_TOP 3

struct GRADE
{
	int group;
	int id;
	int score;
} grade[MAX_TABLE];

GRADE top[MAX_GROUP][MAX_TOP]; // MAX_GROUP개 그룹이 있고, 각각의 그룹의 score가 가장 큰 수가 저장됨(MAX_TOP개)

void insertionSort(GRADE dst[], GRADE src)
{
	int i = 0;
	while (i < MAX_TOP && dst[i].id != -1)
	{
		//if (dst[i].score > src.score) // 오름차순(초기화를 MAX로 해주어야함)
		if (dst[i].score < src.score) // 내림차순
		{
			for (int j = MAX_TOP - 1; j > i; j--)
			{
				dst[j] = dst[j - 1];
			}
			break;
		}
		i++;
	}
	if (i < MAX_TOP)
	{
		dst[i] = src;
	}
}

int main(void)
{
	srand(time(NULL));

	for (int i = 0; i < MAX_TABLE; i++)
	{
		grade[i].group = grade[i].id = grade[i].score = -1;
	}

	for (int i = 0; i < MAX_TABLE; i++)
	{
		grade[i].group = rand() % 5; // group은 0~4만 생성 가능
		grade[i].id = rand() % 10 + 1; // id는 1~10.
		grade[i].score = (rand() % 11) * 10; // score는 0~100 중 10의 단위

		insertionSort(top[grade[i].group], grade[i]);
	}

	printf("Insertion Sorting 전 \n");
	
	for (int i = 0; i < MAX_TABLE; i++)
	{
		printf("Group : %2d , ID : %2d , SCORE : %4d\n", grade[i].group, grade[i].id, grade[i].score);
	}

	printf("\nInsertion Sorting 후 \n");

	for (int i = 0; i < MAX_GROUP; i++)
	{
		for (int j = 0; j < MAX_TOP; j++)
		{
			printf("Group : %2d , ID : %2d , SCORE : %4d\n", top[i][j].group, top[i][j].id, top[i][j].score);
		}
		printf("\n");
	}

	return 0;
}

 

예제이다.

 

insertionSort 부분만 보자면

void insertionSort(GRADE dst[], GRADE src)
{
	int i = 0;
	while (i < MAX_TOP && dst[i].id != -1)
	{
		//if (dst[i].score > src.score) // 오름차순(초기화를 MAX로 해주어야함)
		if (dst[i].score < src.score) // 내림차순
		{
			for (int j = MAX_TOP - 1; j > i; j--)
			{
				dst[j] = dst[j - 1];
			}
			break;
		}
		i++;
	}
	if (i < MAX_TOP)
	{
		dst[i] = src;
	}
}

이와같다.

 

1. i를 증가시키면서, src가 들어가야할 위치를 찾는다.

2. MAX - 1 부터 위치를 찾은 곳 까지 한 칸씩 뒤로 미룬다.

3. 위치에다가 src를 넣는다.

 

이 코드는 top3개 혹은 top5개를 찾을 때 매우 유용한 소스코드이다.

시험보기전에 필수적으로 외우고 들어가야한다.

 

이 코드를 이용해서 푼 예제 : SNS

https://github.com/JirongKim/Certificate/blob/master/SNS/SNS/user3.cpp