BLOG. 2won0

Binary Search 를 구현해 보겠다. 먼저 Binary Search란  위의 그림처럼 배열의 중간값을 기준으로 찾고자 하는 값이 중간값보다 크면 기준의 오른쪽 배열을 선택, 찾고자 하는 값이 중간값보다 작으면 기준의 왼쪽 배열을  선택해가며 원하는 숫자를 찾아내는 방법이다.  Binary Search에 대한 포스팅은 1. 사이즈가 10,000인 배열을 생성하고 배열에 겹치지 않는 랜덤한 숫자를 저장한 뒤 파일에 저장한다. 2. Binary Search를 Iterative한 방식으로 구현해 본다. 3. Binary Search를 Recursive한 방식으로 구현해 본 뒤 Iterative한 방식과 비교해 본다. 총 3개의 글로 나누어 포스팅 해 보겠다.  먼저 중복이 없이 오름차순으로 정렬된 100..

Insertion Sorting에 이어 이번에는 Selection Sorting의 시간을 측정해 보았다.   이번에도 마찬가지로 1,000,000개의 랜덤한 숫자를 생성한 뒤 Selection Sorting을 이용하여 정렬하고 시간을 측정해 보았다. 측정된 시간은 1772.119초, 약 29분 53초가 소요되었다. 역시 정렬되기 전 숫자들은 before.txt 파일에, 정렬된 후의 숫자들은 after.txt에 저장하고 제대로 정렬이 되었는지 또한 확인해 보았다.      제대로 정렬된 모습을 볼 수 있었다.  같은 1,000,000개의 숫자를 정렬 할 때 Insertion Sorting과 비교해 본다면 정렬해야 할 숫자의 양이 많아질 때는  Selection Sorting이 비교적 느린 속도를 보여주었다..

삽입정렬, (Insertion Sorting)을 이용하여 1,000,000개의 랜덤한 숫자를 생성한 뒤 Insertion Sorting을 통해 정렬한뒤 시간을 측정해 보았다.또한 정렬되기 전 랜덤하게 생성된 숫자들을 before.txt 라는 파일에 저장하고,정렬이 완료된 숫자는 after.txt라는 파일에 저장하여 두 파일을 비교 해 보았다.   Sorting을 진행한 총 시간은 1059.978 sec 즉, 17분 6663초 정도가 소요 되었다.    before.txt파일과 after.txt 파일을 비교해 보면 정렬 또한 제대로 된 것을 확인 할 수 있다.    데이터의 양에 따른 Sorting 시간을 측정해 보았는데   일정 양을 넘어가면 Sorting 시간이 기하급수적으로 증가하는 모습을 볼 수 있..

Array를 정적할당할때와 동적할당으로 할 때 최대한 만들 수 있는 사이즈는 얼마나 될 까? 실험을 해 보았다. 그전에 먼저 정적할당이란 #define arrSize 200000int arr[arrSize];와 같이 직접 코드 작성시에 메모리 사이즈를 할당해 주는 것이고, 이는 메모리의 STACK 영역에 compile time시 메모리가 할당된다. 동적할당이란int* arr = (int*)malloc(sizeof(int)*arrSize); if(arr==NULL){ printf("메모리할당실패\n"); exit(1);}​와 같이 흔히들 malloc, calloc으로 알고 있는 방법으로 메모리 사이즈를 할당해 주는 것으로 메모리의 HEAP 영역에 올라가며running time에 메모리를 할당할 수 있다. ..

보통의 Swap 함수를 구현한다고 하면 두개의 변수를 포인터로 받아와 함수 내에서 temp 변수를 사용하는게 일반적이다. void swap(int *pa, int *pb) { int temp; temp = *pa; *pa = *pb; *pb = temp; } 하지만 temp변수를 사용하지 않고 Swap 함수를 구현할 수도 있다. void swap(int *pa, int *pb) {// without temp *pa = *pa + *pb; // a의 값에 b를 더한다. *pb = *pa - *pb; // b에는 a에서 b를 뺀 값을 저장한다. (즉, 처음 a의 값이 된다.) *pa = *pa - *pb; // a에는 처음 a와 b가 더해진 값에서 b를 뺀다 (b는 바뀐 a값이 저장되어 있다.) // 결국 ..