[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;
}