TWpower Reading time ~1 minute

쉘 스크립트에서 sudo 패스워드를 전달 받거나 스크립트에서 사용해보자


환경

  • Linux 기반 시스템
  • Bash shell(/bin/bash)


방법

  • -S 옵션과 |를 이용
echo "PASSWORD" | sudo -S apt-get update
  • 파일을 이용하는 경우
cat << EOF > password.txt
> PASSWORD
> EOF

cat password.txt | sudo -S apt-get update


  • --stdin 옵션과 |를 이용
echo "PASSWORD" | sudo --stdin apt-get update
  • 파일을 이용하는 경우
cat << EOF > password.txt
> PASSWORD
> EOF

cat password.txt | sudo --stdin apt-get update


참고자료

TWpower Reading time ~1 minute

Process file or result of command in while loop line by line in shell script.


Environment and Prerequisite

  • Linux base system
  • Bash shell(/bin/bash)


Solution

  • Use -S option and |
echo "PASSWORD" | sudo -S apt-get update
  • Usage with file
cat << EOF > password.txt
> PASSWORD
> EOF

cat password.txt | sudo -S apt-get update


  • Use --stdin option and |
echo "PASSWORD" | sudo --stdin apt-get update
  • Usage with file
cat << EOF > password.txt
> PASSWORD
> EOF

cat password.txt | sudo --stdin apt-get update

Reference

TWpower Reading time ~5 minutes

Implement basic form of singly linked list


Environment and Prerequisite

  • C++


What is Singly Linked List?

Concept

  • It is a data structure which have datas in one node and point to other node sequentially.
  • It is an advantage compared with array in insertion and deletion. However accessing takes O(n).
  • It is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.



Implementation

Common

  • list is a head of list
  • You can modify insertion, deletion and finding codes if you want.
#include <stdio.h>
#include <stdlib.h>

// Node
struct Node {
	int data;
	Node * next;
};

// Global list
Node * list;


Insertion/Delettion Common

  • It is easy to implement if we consider the head(or first element) of list
  • It is helpful if there are cur pointer which points current node and prev pointer which points previous node of current node. They are helpful in insertion and deletion.
  • In deletion, if there is a node that we want to delete, then it returns true. If not, then return false.


Insertion

  • Like below picture, find the position of new node. Then, point new node’s next to next node and previous node’s next to new node.
  • There are 3 types of functions.
  • add: add just new node
  • ascending_order_add: add node in middle(by ascending order)
  • add_unique: add only unique node



// Add - one by one
void add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	// Check first element
	if (list == NULL) {
		list = new_node;
	}
	else {
		// Add new node to head
		new_node->next = list;
		list = new_node;
	}
}

// Add - add ascending order
void ascending_order_add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {

		Node * cur = list;
		Node * prev = NULL;

		// If first element is larger than key
		if (cur->data > new_node->data) {
			new_node->next = cur;
			list = new_node;
		}
		// Other cases
		else {
			while (cur != NULL && cur->data < new_node->data) {
				prev = cur;
				cur = cur->next;
			}
			// Add in middle
			if (cur != NULL) {
				new_node->next = cur;
				prev->next = new_node;
			}
			// Add to end
			else {
				prev->next = new_node;
			}
		}
	}
}

// Add - add only unique value
void add_unique(int key) {
	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {
		Node * cur = list;

		// Duplication check
		while (cur != NULL) {
			if (cur->data == key) {
				return;
			}
			cur = cur->next;
		}

		new_node->next = list;
		list = new_node;
	}
}


Deletion

  • Like below picture, find the position of node which will be deleted. Then, points previous node’s next to current node’s(which will be deleted) next.
  • Use curand prev pointers.



// Remove
bool remove(int key) {

	if (list == NULL) {
		return false;
	}

	if (list->data == key) {
		Node * cur = list;
		list = list->next;
		free(cur);
		return true;
	}
	else {
		Node * cur = list->next;
		Node * prev = list;
		while (cur != NULL && cur->data != key) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}


Code

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

// Node
struct Node {
	int data;
	Node * next;
};

// Global list
Node * list;

// Init
void init() {

	if (list == NULL) {
		return;
	}
	else {
		Node * cur;
		cur = list;

		while (cur != NULL) {
			list = cur->next;
			free(cur);
			cur = list;
		}
	}
}

// Add - one by one
void add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	// Check first element
	if (list == NULL) {
		list = new_node;
	}
	else {
		// Add new node to head
		new_node->next = list;
		list = new_node;
	}
}

// Add - add ascending order
void ascending_order_add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {

		Node * cur = list;
		Node * prev = NULL;

		// If first element is larger than key
		if (cur->data > new_node->data) {
			new_node->next = cur;
			list = new_node;
		}
		// Other cases
		else {
			while (cur != NULL && cur->data < new_node->data) {
				prev = cur;
				cur = cur->next;
			}
			// Add in middle
			if (cur != NULL) {
				new_node->next = cur;
				prev->next = new_node;
			}
			// Add to end
			else {
				prev->next = new_node;
			}
		}
	}
}

// Add - add only unique value
void add_unique(int key) {
	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {
		Node * cur = list;

		// Duplication check
		while (cur != NULL) {
			if (cur->data == key) {
				return;
			}
			cur = cur->next;
		}

		new_node->next = list;
		list = new_node;
	}
}

// Remove
bool remove(int key) {

	if (list == NULL) {
		return false;
	}

	if (list->data == key) {
		Node * cur = list;
		list = list->next;
		free(cur);
		return true;
	}
	else {
		Node * cur = list->next;
		Node * prev = list;
		while (cur != NULL && cur->data != key) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}

// Traverse
void traverse() {

	Node * cur = list;
	while (cur != NULL) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");

}

int main() {

	int arr[9] = { 2, 4, 6, 8, 1, 3, 5, 7, 9 };
	int arr_duplicated[18] = { 8, 1, 3, 2, 4, 6, 8, 1, 3, 5, 7, 9, 2, 4, 6, 5, 7, 9 };
	int arr_rmv[4] = { 2, 9, 8, 100 };


	// Add to list 1
	init();
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
		add(arr[i]);
	}
	printf("After add(normal): ");
	traverse();


	// Add to list 2
	init();
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
		ascending_order_add(arr[i]);
	}
	printf("After add(ascending): ");
	traverse();


	// Add to list 3
	init();
	for (int i = 0; i < sizeof(arr_duplicated) / sizeof(arr_duplicated[0]); ++i) {
		add_unique(arr_duplicated[i]);
	}
	printf("After add(unique): ");
	traverse();


	// Remove specific values in list
	for (int i = 0; i < sizeof(arr_rmv) / sizeof(arr_rmv[0]); ++i) {
		remove(arr_rmv[i]);
	}
	printf("After remove: ");
	traverse();

	return 0;

}

Result

After add(normal): 9 7 5 3 1 8 6 4 2
After add(ascending): 1 2 3 4 5 6 7 8 9
After add(unique): 9 7 5 6 4 2 3 1 8
After remove: 7 5 6 4 3 1


Reference

TWpower Reading time ~7 minutes

업데이트(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;
}


참고자료

TWpower Reading time ~8 minutes

Update(2019.07.25): Add insertions codes

Use insertion sort to find top n elements in array.


Environment and Prerequisite

  • C++


Insertion Sort?

Concept

  • Insertion Sort: Traverse all elements from front to end and insert each element to front sorted array part. As you can see below picture, consider the front array value is sorted. Then traverse all rest elements and insert each element to front sorted array part.
  • Time Complexity: O(n^2), Space Complexity: O(1)(doesn’t need extra spaces)
  • Below GIF shows insertion sort.


Find top N elements in datas.

Solution

  • There are many solutions.
  • We can use heap, selection after quick sorting… etc there many solutions. However when it is a case that select top n elements after all processings are done it doesn’t need to sort all elements. We only need top n elements so insertion sort could the best solution.
  • If it is not a case that all processings are done, heap could be the solution. That is why we call heap as priority queue.


Implmentation Goal

  • We will find top n elements in nodes which have string key and integer value.
  • Sorting rule will be 1. Integer value 2. Lexicographical order(if integer value are same)


Implementation

Common

  • Node is a datas that need to be sorted. Node have string key and integer value.
  • nodes: array with Node data type.
  • ranks: array which has top n elements of nodes.
#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;
};

// data
Node nodes[MAX_NUM_OF_DATA];

// array for saving top NUM_OF_RANKS of nodes index
int ranks[NUM_OF_RANKS];


String Comparison

  • Common string compare and copy function.
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;
}


Compare Function

  • i and j each represents index of nodes array.
  • Compare rule: 1. Integer value 2. Lexicographical order(if integer value are same)
  • if i is bigger than j then it returns 1, it they are same then returns 0 if not then return -1
// compare nodes[i] and nodes[j] value ans 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;
	}
}


Init

  • Init nodes array and ranks array values.
void init() {

	// ranks array init
	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		ranks[i] = -1;
	}

	// for random value
	srand(time(NULL));

	// init integer values
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		nodes[i].value = rand() % MAX_VALUE_SIZE + 1;
	}

	// init string key values
	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';
	}
}


Insert node data to ranks array

  • Basically codes are base on insertion sort.
  • There are insertion sort 1 and insertion sort 2. First one is find place from back to front and second one is find place from front to back. First one is a bit simple.
  • Doing insertion sort in ranks array when node_id in nodes array passes to function.
  • Return if node_id of node is smaller than last element of ranks array.
  • In first case, if it is included in top N elements then find place from back by comparing.
  • In second case, if it is included in top N elements then find place from front by comparing and move rest elements in turn.
void find_ranks(int node_id) {

	// return if nodes[node_id]'s value is smaller than last element of ranks array
	if (my_compare(ranks[NUM_OF_RANKS - 1], node_id) > 0) {
		return;
	}

    // insertion sort 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;
	}
    /*
	// insertion sort 2
	// traverse ranks array
	for (int rank_index = 0; rank_index < NUM_OF_RANKS; ++rank_index) {

		// if nodes value of index node_id is bigger than current ranks[rank_index]
		if (my_compare(ranks[rank_index], node_id) < 0) {
			// move each values from that point
			for (int j = NUM_OF_RANKS - 1; j > rank_index; --j) {
				ranks[j] = ranks[j - 1];
			}
			// insert node_id to ranks array
			ranks[rank_index] = node_id;
			break;
		}
	}*/
}


Main Function

  • First, sort NUM_OF_RANKS elements. At first, there are trash values in ranks array so it needs to be sorted NUM_OF_RANKS elements.
  • Call find_ranks(node_id) function and print results.
int main() {

	init();

	// Initial array is blank
	// Add NUM_OF_RANKS's amount elements.

	// Add NUM_OF_RANKS elements.
	for (int node_id = 0; node_id < NUM_OF_RANKS; ++node_id) {
		ranks[node_id] = node_id;
	}

	// insertion sort 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;
	}
	/*
	// insertion sort 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) {

			// if nodes value of index node_id is bigger than current ranks[rank_index]
			if (my_compare(ranks[rank_index], node_id) < 0) {
				// move each values from that point
				for (int k = NUM_OF_RANKS - 1; k > rank_index; --k) {
					ranks[k] = ranks[k - 1];
				}
				// insert node_id to ranks array
				ranks[rank_index] = node_id;
				break;
			}
		}
	}
	*/
	// Find top NUM_OF_RANKS elements in nodes
	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;
}


Code

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

// data
Node nodes[MAX_NUM_OF_DATA];

// array for saving top NUM_OF_RANKS of nodes index
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;
}

// compare nodes[i] and nodes[j] value ans 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() {

	// ranks array init
	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		ranks[i] = -1;
	}

	// for random value
	srand(time(NULL));

	// init integer values
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		nodes[i].value = rand() % MAX_VALUE_SIZE + 1;
	}

	// init string key values
	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) {

	// return if nodes[node_id]'s value is smaller than last element of ranks array
	if (my_compare(ranks[NUM_OF_RANKS - 1], node_id) > 0) {
		return;
	}

    // insertion sort 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;
	}
	/*
	// insertion sort 2
	// traverse ranks array
	for (int rank_index = 0; rank_index < NUM_OF_RANKS; ++rank_index) {

		// if nodes value of index node_id is bigger than current ranks[rank_index]
		if (my_compare(ranks[rank_index], node_id) < 0) {
			// move each values from that point
			for (int j = NUM_OF_RANKS - 1; j > rank_index; --j) {
				ranks[j] = ranks[j - 1];
			}
			// insert node_id to ranks array
			ranks[rank_index] = node_id;
			break;
		}
	}*/
}

int main() {

	init();

	// Initial array is blank
	// Add NUM_OF_RANKS's amount elements.

	// Add NUM_OF_RANKS elements.
	for (int node_id = 0; node_id < NUM_OF_RANKS; ++node_id) {
		ranks[node_id] = node_id;
	}

	// insertion sort 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;
	}
	/*
	// insertion sort 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) {

			// if nodes value of index node_id is bigger than current ranks[rank_index]
			if (my_compare(ranks[rank_index], node_id) < 0) {
				// move each values from that point
				for (int k = NUM_OF_RANKS - 1; k > rank_index; --k) {
					ranks[k] = ranks[k - 1];
				}
				// insert node_id to ranks array
				ranks[rank_index] = node_id;
				break;
			}
		}
	}
	*/
	// Find top NUM_OF_RANKS elements in nodes
	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;
}


Reference