[Algorithm] C/C++에서 삽입정렬을 이용해 상위 n개 구하기

업데이트(2019.07.25): 삽입정렬 코드 추가

C++에서 삽입정렬을 이용해 상위 n개를 구하는 코드를 작성해보자


환경

  • C++


삽입정렬이란?

개념

  • 삽입정렬: 앞에서부터 모든 원소를 탐색하면서 정렬된 앞 부분에 위치를 찾아서 추가하는 방법으로 진행하는 정렬을 의미합니다. 아래 사진을 보시면 시작할 때 제일 앞에 원소는 정렬되어있다고 가정하고 뒤에 원소를 하나하나 탐색하면서 앞의 정렬된 부분에 추가하고 그 뒤에 부분은 밀어주는 방식입니다.
  • 시간복잡도: O(n^2), 공간복잡도: O(1)(추가적인 공간 필요X)
  • 아래 GIF는 해당 내용을 이미지로 빠르게 표현한 사진입니다.


전체 자료에서 상위 N개 구하기

방법

  • 여러가지 방법이 있을 수 있습니다.
  • 힙을 사용, 퀵소트를 통해 정렬하고 앞에서 N개를 선택…과 같은 여러 방법이 있지만 모든 작업을 마치고 주어진 자료에서 상위 N개를 선택할 때의 상황에서는 전체가 정렬될 필요가 없고 상위 N개만 필요하기 때문에 삽입정렬이 유리합니다.
  • 만약 모든 작업을 마친게 아니고 매 작업마다 현재 상황에서 가장 우선 순위가 높은 자료를 가져오는 경우라면 힙을 사용하는게 유리합니다.(실제로 우선 순위 큐의 목적)


구현 목표

  • 문자열과 정수값을 가지고 있는 무작위의 노드들에서 정수값이 가장 크고 정수값이 같을 때 문자열이 사전순인 노드 상위 N개를 선택하려한다.


구현

공통

  • Node는 정렬할 자료의 대상이며 각 Node는 문자열 key와 정수 value를 가지고 있습니다.
  • nodes: Node들을 가지고 있는 배열입니다.
  • ranks: nodes에 서 상위 N개의 인덱스를 차례로 저장할 배열입니다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_KEY_LEN 13
#define MIN_KEY_LEN 5
#define MAX_NUM_OF_DATA 5000
#define MAX_VALUE_SIZE 5000
#define NUM_OF_RANKS 5

using namespace std;

struct Node {
	char key[MAX_KEY_LEN];
	int value;
};

// 데이터
Node nodes[MAX_NUM_OF_DATA];

// 상위 NUM_OF_RANKS개에 해당하는 nodes의 인덱스를 저장할 배열
int ranks[NUM_OF_RANKS];


문자열 비교

  • 비교함수와 복사함수입니다.
  • 일반적으로 사용하는 문자열 함수와 같습니다.
void my_str_cpy(char * dest, const char * src) {
	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';
}

int my_str_cmp(const char * str1, const char * str2) {
	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++; str2++;
	}
	return *str1 - *str2;
}


비교함수

  • i와 j는 각각 nodes 배열에 있는 인덱스를 의미합니다.
  • 비교는 1. 정수값이 클수록 2. 정수값이 같다면 문자열은 사전순으로에 따라서 비교합니다.
  • i가 j보다 크다면 양수를 둘이 같다면 0을 그게 아니라면 음수를 반환합니다.
// nodes[i]와 nodes[j]의 value와 key를 비교합니다.
// nodes[i] > nodes[j] => return 1;
// nodes[i] == nodes[k] => return 0;
// nodes[i] < nodes[j] => return -1;
int my_compare(int i, int j) {
	if (nodes[i].value > nodes[j].value ||
		(nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) < 0)) {
		return 1;
	}
	else if (nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) == 0) {
		return 0;
	}
	else {
		return -1;
	}
}


초기화

  • Node의 값들과 ranks 배열의 값들을 초기화합니다.
void init() {

	// 순위 배열 초기화
	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		ranks[i] = -1;
	}

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// 정수값들 초기화
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		nodes[i].value = rand() % MAX_VALUE_SIZE + 1;
	}

	// 문자열 key들 초기화
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		for (int j = 0; j < MAX_KEY_LEN - 1; ++j) {
			nodes[i].key[j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		nodes[i].key[rand() % MIN_KEY_LEN + MIN_KEY_LEN] = '\0';
	}
}


상위 N개를 찾는 배열에 데이터 삽입

  • 기본적으로 삽입정렬에 기반한 코드를 작성하였습니다.
  • 삽입정렬1과 삽입정렬2가 있으며 1번은 뒤에서부터 비교하면서 위치를 찾는 코드이며 2번은 앞에서부터 비교하면서 위치를 찾는 코드입니다. 1번을 이용해 비교적 코드가 더 간결해질 수 있습니다.
  • nodes 배열에 있는 node_id를 함수에 전달하면 ranks안에서 삽입정렬을 시행합니다.
  • 이 때 상위 N개 중에서 가장 마지막 값보다 값이 작으면 삽입을 진행하지 않습니다.
  • 1번의 경우, 만약 상위 N개 안에 포함된다면 뒤에서부터 비교해가면서 위치를 찾아갑니다.
  • 2번의 경우, 만약 상위 N개 안에 포함된다면 앞에서부터 값을 찾고 뒤에 값들은 하나씩 자리를 이동시킨 다음에 삽입합니다.
void find_ranks(int node_id) {

	// nodes[node_id]가 제일 뒤에 값보다 작으면 비교하지 않는다.
	if (my_compare(ranks[NUM_OF_RANKS - 1], node_id) > 0) {
		return;
	}

	// 삽입정렬1
	ranks[NUM_OF_RANKS - 1] = node_id;
	for (int rank_index = 1; rank_index < NUM_OF_RANKS; ++rank_index) {
		int tmp = ranks[rank_index];
		int j = rank_index - 1;

		while(j >= 0 && my_compare(ranks[j], tmp) < 0){
			ranks[j+1] = ranks[j];
			j--;
		}
		ranks[j+1] = tmp;
	}
	/*
	// 삽입정렬2
	// ranks 배열을 탐색하면서
	for (int rank_index = 0; rank_index < NUM_OF_RANKS; ++rank_index) {

		// node_id에 해당하는 노드가 ranks[rank_index]에 해당하는 노드보다 크다면
		if (my_compare(ranks[rank_index], node_id) < 0) {
			// 해당 위치부터 뒤에 있는 값들을 ranks에서 한칸씩 밀고
			for (int j = NUM_OF_RANKS - 1; j > rank_index; --j) {
				ranks[j] = ranks[j - 1];
			}
			// ranks에 현재 node_id를 추가합니다.
			ranks[rank_index] = node_id;
			break;
		}
	}*/
}


메인함수

  • 처음에 NUM_OF_RANKS의 수만큼 우선 정렬을 해줍니다. 처음에는 아무값도 없기때문에 미리 NUM_OF_RANKS만큼 정렬을 해줍니다.
  • 나머지 자료들에 대해서 find_ranks() 함수를 호출하고 결과를 출력합니다.
int main() {

	init();

	// 초기 배열은 비어있는 상태로
	// NUM_OF_RANKS의 수만큼은 직접 대입해준다.

	// NUM_OF_RANKS만큼 먼저 대입
	for (int node_id = 0; node_id < NUM_OF_RANKS; ++node_id) {
		ranks[node_id] = node_id;
	}

	// 삽입정렬1
	for (int rank_index = 1; rank_index < NUM_OF_RANKS; ++rank_index) {
		int j = rank_index - 1;
		int tmp = ranks[rank_index];

		while(j >= 0 && my_compare(ranks[j], tmp) < 0){
			ranks[j+1] = ranks[j];
			j--;
		}
		ranks[j+1] = tmp;
	}
	/*
	// 삽입정렬2
	for (int node_id = 1; node_id < NUM_OF_RANKS; ++node_id) {
		for (int rank_index = node_id; rank_index < NUM_OF_RANKS; ++rank_index) {

			// node_id에 해당하는 노드가 ranks[rank_index]에 해당하는 노드보다 크다면
			if (my_compare(ranks[rank_index], node_id) < 0) {
				// 해당 위치부터 뒤에 있는 값들을 ranks에서 한칸씩 밀고
				for (int k = NUM_OF_RANKS - 1; k > rank_index; --k) {
					ranks[k] = ranks[k - 1];
				}
				// ranks에 현재 node_id를 추가합니다.
				ranks[rank_index] = node_id;
				break;
			}
		}
	}
	*/
	// 전체 자료들에 대해 상위 NUM_OF_RANKS개 구하기
	for (int node_id = NUM_OF_RANKS; node_id < MAX_NUM_OF_DATA; ++node_id) {
		find_ranks(node_id);
	}

	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		printf("%d: \n", i + 1);
		printf("ID: %d\n", ranks[i]);
		printf("Value: %d\n", nodes[ranks[i]].value);
		printf("Key: %s\n", nodes[ranks[i]].key);
	}
	return 0;
}


전체 코드

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

#define MAX_KEY_LEN 13
#define MIN_KEY_LEN 5
#define MAX_NUM_OF_DATA 5000
#define MAX_VALUE_SIZE 5000
#define NUM_OF_RANKS 5

using namespace std;

struct Node {
	char key[MAX_KEY_LEN];
	int value;
};

// 데이터
Node nodes[MAX_NUM_OF_DATA];

// 상위 NUM_OF_RANKS개에 해당하는 nodes의 인덱스를 저장할 배열
int ranks[NUM_OF_RANKS];

void my_str_cpy(char * dest, const char * src) {
	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';
}

int my_str_cmp(const char * str1, const char * str2) {
	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++; str2++;
	}
	return *str1 - *str2;
}

// nodes[i]와 nodes[j]의 value와 key를 비교합니다.
// nodes[i] > nodes[j] => return 1;
// nodes[i] == nodes[k] => return 0;
// nodes[i] < nodes[j] => return -1;
int my_compare(int i, int j) {
	if (nodes[i].value > nodes[j].value ||
		(nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) < 0)) {
		return 1;
	}
	else if (nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) == 0) {
		return 0;
	}
	else {
		return -1;
	}
}

void init() {

	// 순위 배열 초기화
	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		ranks[i] = -1;
	}

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// 정수값들 초기화
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		nodes[i].value = rand() % MAX_VALUE_SIZE + 1;
	}

	// 문자열 key들 초기화
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		for (int j = 0; j < MAX_KEY_LEN - 1; ++j) {
			nodes[i].key[j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		nodes[i].key[rand() % MIN_KEY_LEN + MIN_KEY_LEN] = '\0';
	}
}

void find_ranks(int node_id) {

	// nodes[node_id]가 제일 뒤에 값보다 작으면 비교하지 않는다.
	if (my_compare(ranks[NUM_OF_RANKS - 1], node_id) > 0) {
		return;
	}

	// 삽입정렬1
	ranks[NUM_OF_RANKS - 1] = node_id;
	for (int rank_index = 1; rank_index < NUM_OF_RANKS; ++rank_index) {
		int tmp = ranks[rank_index];
		int j = rank_index - 1;

		while(j >= 0 && my_compare(ranks[j], tmp) < 0){
			ranks[j+1] = ranks[j];
			j--;
		}
		ranks[j+1] = tmp;
	}
	/*
	// 삽입정렬2
	// ranks 배열을 탐색하면서
	for (int rank_index = 0; rank_index < NUM_OF_RANKS; ++rank_index) {

		// node_id에 해당하는 노드가 ranks[rank_index]에 해당하는 노드보다 크다면
		if (my_compare(ranks[rank_index], node_id) < 0) {
			// 해당 위치부터 뒤에 있는 값들을 ranks에서 한칸씩 밀고
			for (int j = NUM_OF_RANKS - 1; j > rank_index; --j) {
				ranks[j] = ranks[j - 1];
			}
			// ranks에 현재 node_id를 추가합니다.
			ranks[rank_index] = node_id;
			break;
		}
	}*/
}

int main() {

	init();

	// 초기 배열은 비어있는 상태로
	// NUM_OF_RANKS의 수만큼은 직접 대입해준다.

	// NUM_OF_RANKS만큼 먼저 대입
	for (int node_id = 0; node_id < NUM_OF_RANKS; ++node_id) {
		ranks[node_id] = node_id;
	}

	// 삽입정렬1
	for (int rank_index = 1; rank_index < NUM_OF_RANKS; ++rank_index) {
		int j = rank_index - 1;
		int tmp = ranks[rank_index];

		while(j >= 0 && my_compare(ranks[j], tmp) < 0){
			ranks[j+1] = ranks[j];
			j--;
		}
		ranks[j+1] = tmp;
	}
	/*
	// 삽입정렬2
	for (int node_id = 1; node_id < NUM_OF_RANKS; ++node_id) {
		for (int rank_index = node_id; rank_index < NUM_OF_RANKS; ++rank_index) {

			// node_id에 해당하는 노드가 ranks[rank_index]에 해당하는 노드보다 크다면
			if (my_compare(ranks[rank_index], node_id) < 0) {
				// 해당 위치부터 뒤에 있는 값들을 ranks에서 한칸씩 밀고
				for (int k = NUM_OF_RANKS - 1; k > rank_index; --k) {
					ranks[k] = ranks[k - 1];
				}
				// ranks에 현재 node_id를 추가합니다.
				ranks[rank_index] = node_id;
				break;
			}
		}
	}
	*/
	// 전체 자료들에 대해 상위 NUM_OF_RANKS개 구하기
	for (int node_id = NUM_OF_RANKS; node_id < MAX_NUM_OF_DATA; ++node_id) {
		find_ranks(node_id);
	}

	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		printf("%d: \n", i + 1);
		printf("ID: %d\n", ranks[i]);
		printf("Value: %d\n", nodes[ranks[i]].value);
		printf("Key: %s\n", nodes[ranks[i]].key);
	}
	return 0;
}


참고자료

Read More

[Java] API 테스트를 위한 Rest Assured 준비와 예제

Published on January 28, 2024

[Java](EN) Rest Assured Setting and Example for API Test

Published on January 28, 2024

[AWS] Policy에서 AWS IAM ARN이 고유 식별자(Unique Identifier)로 바뀌는 이유와 해결 방법

Published on January 01, 2024