업데이트(2018.04.19) : C++ 정렬 코드 추가

Merge Sort를 구현해보자


환경

  • Python
  • C++


Merge Sort란?

원리

  • 현재 주어진 값들을 반으로 나누고 각각 나누어진 부분을 또 계속 나눈 후에 합치면서 정렬을 진행한다. 대표적인 분할정복의 예제

특징

  • Divide and Conquer이라는 분할정복 방법으로 정렬을 진행하며 자세한 부분은 다음을 참고하시면 좋습니다.
  • stable sort : 정렬 할 원소들이 튜플이나 레코드처럼 다른 원소들을 포함하고 있을 때 정렬 후에도 그 순서가 유지되는 정렬입니다.


복잡도

  • 시간복잡도 : O(nlogn)
  • 공간복잡도 : 이 코드에서는 O(n)이며 분할정복을 병렬로 진행하면 O(nlogn)


구현 코드(Python)


def merge_sort(A):
	if len(A) <= 1:
		return A

	# 분할 정복
	mid = int(len(A)/2)
	left_side = merge_sort(A[:mid])
	right_side = merge_sort(A[mid:])

	# left,right 각각을 위한 인덱스 l,r
	# 왼쪽과 오른쪽에서의 합병된 값을 저장할 A의 인덱스 k

	l = 0
	r = 0
	k = 0

	# 이제 왼쪽과 오른쪽을 비교하면서 merge
	while l < len(left_side) and r < len(right_side):
		if left_side[l] < right_side[r]:
			A[k] = left_side[l]
			k += 1
			l += 1
		else:
			A[k] = right_side[r]
			k += 1
			r += 1

	# 이제 남아 있는 경우만 더 확인

	# 오른쪽이 남아있다면
	while r < len(right_side):
		A[k] = right_side[r]
		r += 1
		k += 1

	# 왼쪽이 남아있다면
	while l < len(left_side):
		A[k] = left_side[l]
		l += 1
		k += 1

	return A


import random
A = [random.randint(0,100) for _ in range(0,10)]
print(A)
merge_sort(A)
print(A)


구현 코드(C++)

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

using namespace std;


void merge_sort(vector<int> &a, int left, int right) {

	if (left < right) {

		// 분할 정복
		int mid = left + (right - left) / 2;
		merge_sort(a, left, mid);
		merge_sort(a, mid + 1, right);

		//merge(a, left, mid, right);
		// i는 왼쪽, j는 오른쪽, k는 a를 채울 index
		int i, j, k;

		int left_side_size = mid - left + 1; // left ~ mid
		int right_side_size = right - mid; // mid+1 ~ right

		// 왼쪽과 오른쪽을 저장할 배열 1개씩 생성
		int * left_side = (int*)malloc(left_side_size * sizeof(int));
		int * right_side = (int*)malloc(right_side_size * sizeof(int));

		// 배열 채우고
		for (int l = 0; l < left_side_size; l++) {
			left_side[l] = a[left + l];
		}
		for (int r = 0; r < right_side_size; r++) {
			right_side[r] = a[mid + 1 + r];
		}

		// Merge
		// 이제 양 옆에서 하나씩 비교하면서 a에 추가
		i = j = 0;
		k = left;
		while (i < left_side_size && j < right_side_size) {

			if (left_side[i] <= right_side[j]) {
				a[k] = left_side[i];
				i++;
			}
			else {
				a[k] = right_side[j];
				j++;
			}
			k++;
		}

		// 오른쪽이 남아있다면
		while (j < right_side_size) {
			a[k] = right_side[j];
			j++;
			k++;
		}

		// 왼쪽이 남아있다면
		while (i < left_side_size) {
			a[k] = left_side[i];
			i++;
			k++;
		}
		free(left_side); free(right_side);
	}
}

int main() {

	vector<int> a(5);
	int len = a.size(); // 벡터길이

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

	// 벡터 초기화
	for (int i = 0; i < len; i++) {
		// 1 ~ 50까지의 난수 생성
		a[i] = rand() % 50 + 1;
	}

	// 정렬 전 출력
	for (int i = 0; i < len; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	// 합병정렬
	merge_sort(a, 0, len - 1);

	// 정렬 후 출력
	for (int i = 0; i < len; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	return 0;
}


참고자료

업데이트(2018.04.19) : C++ 정렬 코드 추가

Quick Sort를 구현해보자


환경

  • Python
  • C++


Quick Sort란?

원리

  • pivot을 정하고 pivot보다 작은 값들을 pivot의 왼쪽 pivot보다 큰 값들은 pivot의 오른쪽으로 위치시키고 pivot의 왼쪽 값들과 오른쪽 값들을 각각 따로 또 재귀를 통해 분할정복한다.

특징

  • O(nlogn)의 성능을 보이는 정렬 알고리즘중에 하나로 최악에는 O(n^2)의 성능을 보이지만 일반적으로 빠른 성능을 나타내기에 보편적으로 많이 쓰는 알고리즘 입니다.
  • Divide and Conquer이라는 분할정복 방법으로 정렬을 진행하며 자세한 부분은 다음을 참고하시면 좋습니다.
  • in-place sorting : 정렬 할 원소들을 위한 추가적인 메모리를 사용하지 않고 현재 메모리에서 정렬을 진행


복잡도

  • 시간복잡도 : 평균 O(nlogn), 최악 O(n^2)
  • 공간복잡도 : O(logn)(in-place sorting의 경우!)


구현 코드(Python)

in-place sort

  • 메모리를 아낄 수 있다.
  • 하지만 코드가 조금 더 복잡하다.

def swap(A, i, j):
	tmp = A[i]
	A[i] = A[j]
	A[j] = tmp


def quick_sort(A, left, right):
	if left < right:
		p = partition(A, left, right)

		# p 기준으로 왼쪽 값들은 p보다 작고 오른쪽 값들은 p보다 큼
		quick_sort(A,left, p-1)
		quick_sort(A,p+1,right)



def partition(A, left, right):

	import random
	# 랜덤하게 pivot 생성
	pivot_index = random.randint(left, right)
	pivot_value = A[pivot_index]


	# 피벗값과 right의 값을 swap
	swap(A, pivot_index, right)

    # store_index를 기준으로
    # 왼쪽에 pivot_value보다 작은 값들 위치시킴
	store_index = left
	for i in range(left, right):
		if A[i] < pivot_value:
			swap(A, i, store_index)
			store_index += 1
	swap(A, right, store_index)
	return store_index


# 테스트 코드
import random

A = [random.randint(0,100) for _ in range(0,10)]
print(A)
quick_sort(A, 0, len(A)-1)
print(A)


not-in-place sort

  • 코드가 간결하다.
  • 하지만 추가적인 메모리를 사용한다.

def quick_sort(A):
	if(len(A)>1):
		import random
		pivot = A[random.randint(0, len(A)-1)]
		greater = [i for i in A if i > pivot]
		smaller = [i for i in A if i < pivot]
		middle = [i for i in A if i == pivot]
		return quick_sort(smaller) + middle + quick_sort(greater)
	else:
		return A

# 테스트 코드
import random

A = [random.randint(0,100) for _ in range(0,10)]
print(A)
A=quick_sort(A)
print(A)


구현 코드(C++)

in-place sort

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

using namespace std;

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

int partition(int a[], int left, int right) {

	srand(time(NULL));
	// left ~ right 사이의 값을 랜덤으로 생성
	int pivot_index = rand() % (right + 1 - left) + left;
	int pivot_value = a[pivot_index];

	swap(&a[pivot_index], &a[right]);

	// store_index를 기준으로
	// 왼쪽에 pivot_value보다 작은 값들 위치시킴
	int store_index = left;
	for (int i = left; i < right; i++) {
		if (a[i] < pivot_value) {
			swap(&a[i], &a[store_index]);
			store_index += 1;
		}
	}

	swap(&a[store_index], &a[right]);

	return store_index;

}

void quick_sort(int a[], int left, int right) {

	if (left < right) {
		int p = partition(a, left, right);

		quick_sort(a, left, p - 1);
		quick_sort(a, p + 1, right);
	}
}

int main() {

	int a[5];
	int len = sizeof(a) / sizeof(int); // 배열길이

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

	// 배열 초기화
	for (int i = 0; i < len; i++) {
		// 1 ~ 50까지의 난수 생성
		a[i] = rand() % 50 + 1;
	}

	// 정렬 전 출력
	for (int i = 0; i < len; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	// 퀵정렬
	quick_sort(a, 0, len - 1);

	// 정렬 후 출력
	for (int i = 0; i < len; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	return 0;
}


참고자료

Travis CI에서 Python과 Node.js 환경을 설정해서 Appium을 통해 테스트 및 빌드를 진행해보자.


환경 및 선수조건

  • Travis CI
  • Appium(Server+python-client)+Android의 테스트 경험(링크)


과정

Travis CI에서 Android 환경은 기본적으로 설정이 되어있기 때문에 설정되어 있는 환경을 이용하고 Appium(Node.js and Python)yml을 통해서 환경을 직접 설정 해줄 예정입니다.


  1. 안드로이드 환경 설정
    • 언어 및 기본 설정
    • SDK 및 Android 관련 설정
  2. Python 환경 설정
    • pyenv와 virtualenv 설치
    • 가상환경 설정 및 패키지 설치(pytest, Appium-Python-Client etc…)
  3. Node.js 환경 설정
    • node.js 설치
    • appium 설치
  4. Appium 실행
  5. 에뮬레이터 실행
  6. 빌드 및 테스트


1. 안드로이드 환경 설정

사용하는 Travis CI에서는 이미 안드로이드를 빌드 할 수 있는 환경을 모두 제공해줍니다. SDKbuild-tools와 기타 부가적인 부분들만 명시해주면 됩니다.

언어 및 기본 설정

.travis.yml

language: android # 언어는 android로 java가 아닙니다.
sudo: required # sudo의 경우 나중에 필요하기 때문에 required로 명시함
jdk: oraclejdk8 # 필요에 따라서 변경


SDK 및 Android 관련 설정

.travis.yml

language: android # 언어는 android로 java가 아닙니다.
sudo: required # sudo의 경우 나중에 필요하기 때문에 required로 명시함
jdk: oraclejdk8 # 필요에 따라서 변경

android:
    components:
        # 아래를 명시하면 가장 최신 Android SDK Tools를 사용
        - tools
        - platform-tools

        # 버전에 맞는 build-tools
        - build-tools-26.0.2

        # The SDK version used to compile your project
        - android-26
        - android-22
        - android-24

        # Additional components
        - extra-google-google_play_services
        - extra-google-m2repository
        - extra-android-m2repository
        - addon-google_apis-google-26

        # 사용할 시스템 이미지로 에뮬레이터를 사용하려면 적어도 하나는 꼭 명시해줘야 합니다.
        - sys-img-armeabi-v7a-android-22
        - sys-img-armeabi-v7a-android-24


2. Python 환경 설정

나중에 Appium에서 Client(테스트를 실행할 주체)를 Appium-Python-Client를 이용할거기 때문에 pyenvvirtualenv를 이용해 환경을 만들고 패키지들을 설치합니다.

pyenv와 virtualenv 설치

.travis.yml


... # 위에 안드로이드 설정하던거에 이어서

# 사용자 마음이지만 저는 before_install에 환경을 설정했습니다.
before_install:
    - sudo apt-get update

    # pyenv와 virtualenv 그리고 나중에 node.js를 위해 필요한 Ubuntu 패키지를 미리 설치
    - sudo apt-get install -y make build-essential libssl-dev zlib1g-dev libbz2-dev libreadline-dev
      libsqlite3-dev wget curl llvm libncurses5-dev libncursesw5-dev xz-utils tk-dev

    # pyenv 환경 설정
    - git clone https://github.com/pyenv/pyenv.git ~/.pyenv
    - echo 'export PYENV_ROOT="$HOME/.pyenv"' >> ~/.bash_profile
    - echo 'export PATH="$PYENV_ROOT/bin:$PATH"' >> ~/.bash_profile
    - echo 'eval "$(pyenv init -)"' >> ~/.bash_profile

    # virtualenv 환경 설정
    - git clone https://github.com/yyuu/pyenv-virtualenv.git ~/.pyenv/plugins/pyenv-virtualenv
    - echo 'eval "$(pyenv virtualenv-init -)"' >> ~/.bash_profile
    - source ~/.bash_profile
    - pyenv versions


가상환경 설정 및 패키지 설치

아래에 있는 requirements.txt는 패키지들의 목록으로 따로 필요하신것들만 직접 설치하셔도 됩니다.

.travis.yml


... # 위에 이어서 설정하던거에 이어서

    # 파이썬 3.6.1 설치
    - pyenv install 3.6.1

    # 가상환경 생성(가상환경 이름은 undang)
    - pyenv virtualenv 3.6.1 undang
    - pyenv activate undang
    - python -V

    # 패키지 설치
    # 필수 패키지 : Appium-Python-Client, pytest
    - pip install -r requirements.txt


3. Node.js 환경 설정

node.js 설치

설치 방법은 “[Ubuntu] Ubuntu에 PPA를 통해 최신 npm 및 node.js 설치하기“를 참고하세요.

.travis.yml


... # 위에 이어서 설정하던거에 이어서

    # node.js 및 npm 설치
    - curl -sL https://deb.nodesource.com/setup_9.x | sudo -E bash -
    - sudo apt-get install nodejs
    - sudo apt-get install build-essential


appium 설치

.travis.yml


... # 위에 이어서 설정하던거에 이어서

    # PATH에 $JAVA_HOME/bin 추가(Appium 실행할 때 필요)
    - PATH=$PATH:$JAVA_HOME/bin

    # appium 및 appium-doctor 설치
    - npm install appium
    - npm install appium-doctor


4. Appium 실행

.travis.yml


... # 위에 이어서 설정하던거에 이어서

    # -g로 설치하지 않아서 아래처럼 직접 들어가서 appium-doctor 실행
    - "./node_modules/.bin/appium-doctor"

    # appium을 background로 실행하고 log를 appium_log.txt로 로깅
    - "./node_modules/.bin/appium --log-level info > appium_log.txt &"


5. 에뮬레이터 실행

.travis.yml


... # 위에 이어서 설정하던거에 이어서


before_script:

    # 1에서 명시한 시스템이미지로 에뮬레이터 생성
    - echo no | android create avd --force -n test -t android-22 --abi armeabi-v7a

    # 에뮬레이터 실행
    - emulator -avd test -no-skin -no-window &
    - android-wait-for-emulator
    - adb shell input keyevent 82 &


6. 빌드 및 테스트

.travis.yml


script:
    - "./gradlew assemble" # 빌드
    - pytest # 테스트

after_script:
    - cat ./appium_log.txt # appium 로그 확인


최종 .travis.yml

.travis.yml

language: android
sudo: required
jdk: oraclejdk8
android:
    components:
        - tools
        - platform-tools
        - build-tools-26.0.2
        - android-26
        - android-22
        - android-24
        - extra-google-google_play_services
        - extra-google-m2repository
        - extra-android-m2repository
        - addon-google_apis-google-26
        - sys-img-armeabi-v7a-android-22
        - sys-img-armeabi-v7a-android-24
before_install:
    - sudo apt-get update
    - sudo apt-get install -y make build-essential libssl-dev zlib1g-dev libbz2-dev libreadline-dev
      libsqlite3-dev wget curl llvm libncurses5-dev libncursesw5-dev xz-utils tk-dev
    - git clone https://github.com/pyenv/pyenv.git ~/.pyenv
    - echo 'export PYENV_ROOT="$HOME/.pyenv"' >> ~/.bash_profile
    - echo 'export PATH="$PYENV_ROOT/bin:$PATH"' >> ~/.bash_profile
    - echo 'eval "$(pyenv init -)"' >> ~/.bash_profile
    - git clone https://github.com/yyuu/pyenv-virtualenv.git ~/.pyenv/plugins/pyenv-virtualenv
    - echo 'eval "$(pyenv virtualenv-init -)"' >> ~/.bash_profile
    - source ~/.bash_profile
    - pyenv install 3.6.1
    - pyenv virtualenv 3.6.1 undang
    - pyenv activate undang
    - pip install -r requirements.txt
    - curl -sL https://deb.nodesource.com/setup_9.x | sudo -E bash -
    - sudo apt-get install nodejs
    - sudo apt-get install build-essential
    - PATH=$PATH:$JAVA_HOME/bin
    - npm install appium
    - npm install appium-doctor
    - "./node_modules/.bin/appium-doctor"
    - "./node_modules/.bin/appium --log-level info > appium_log.txt &"
before_script:
    - echo no | android create avd --force -n test -t android-22 --abi armeabi-v7a
    - emulator -avd test -no-skin -no-window &
    - android-wait-for-emulator
    - adb shell input keyevent 82 &
script:
    - "./gradlew assemble"
    - pytest
after_script:
    - cat ./appium_log.txt


참고자료

Brief explanation about difference between CNAME and A record


Prior Knowledge

  • DNS(Domain Name Server)
  • Domain, IP Address
  • Let’s assume there is domain which name is test.me


CNAME

CNAME = Acronym of Canonical Name. It gives another name to specific domain name. You can easily think that it is another name of domain name

Example

 blog.test.me -> test.me // Another domain name of test.me
 www.test.me -> test.me  // Another domain name of test.me


A record

A record means domain name has One IP Address. Specific domain(include sub or root) has its own ip address. Like below sub domain can have different ip address.

Example

dev.test.me -> 123.456.789.123 // dev.test.me ip address
test.me -> 987.654.321.123     // test.me ip address


Wiki Example

Below are examples from Wikipedia. Each has different value depends on TYPE


NAME TYPE VALUE
bar.example.com CNAME foo.example.com
foo.example.com A 192.0.2.23

Set ppa and install latest npm and nodejs on Linux(Ubuntu)


Environment and Prerequisite

  • Linux(Ubuntu 16.04 or 14.04)


What is PPA?

PPA

PPA is acronym of Personal Package Archive. It is a third party software package repository. There are many packages which are not included in Ubuntu official apt-get.

ppa-homepage


Install npm and nodejs using PPA

Set PPA

First, we need to specify repository(PPA repository). Now 9.x is the latest version of nodejs so I set to 9.x. You can check latest version on https://github.com/nodejs/Release#release-schedule

$ curl -sL https://deb.nodesource.com/setup_9.x | sudo -E bash -


Install nodejs

Install nodejs

$ sudo apt-get install nodejs


Install build-essential

Above nodejs include npm but we need to install build-essential for using better npm.

$ sudo apt-get install build-essential


Reference