728x90 Sketch (Programming Language)/C & C++4 Quick sort Quick sort algorithm 퀵정렬은 pivot을 설정하고 설정한 pivot을 기준으로 작은 요소들은 모두 pivot의 왼쪽으로 옮겨지고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하고 분할된 부분 리스트에 대하여 recursion을 이용하여 정렬을 반복한다. 이때 quick sort는 unstable sorting process이다. 나누어진 리스트에서도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다. 이때도 merge sort와 같이 divide and conquer 과정을 통해 진행이 됨을 알 수 있다. 추가적으로 pivot을 설정하는 다양한 방법이 있는데 pivot.. 2022. 12. 23. Merge sort Merge sort Divide and Conquer식 설계전략을 이용하고 추가적으로 통합하는 Combine과정을 거쳐셔 Merge sort를 진행한다. 이러한 방식을 하향식(top-down) 접근법이라고 한다. Source code 전체 code를 보기전에 psuedo code를 살펴보면 mergesort는 merge함수를 이용하였음을 알 수 있다. 전체 코드 mergesort.cpp #include "ArrayVector.h" #include #include #include #include //난수생성을 위한 library #include //string으로 형변환을 위한 library #include //실행시간 측정을 위한 library using namespace std; //divide and.. 2022. 12. 22. C++ 난수 생성 rand함수 #include #include #include int main() { srand(time(NULL)); for (int i = 0; i < 5; i++) { printf("Random Num : %d \n", rand() % 100); } return 0; } rand함수를 이용한 위 코드를 보면 srand, time, rand와 같은 함수들을 볼 수 있다. 우선 위의 코드는 실제 난수를 생성하는 코드가 아니라 난수처럼 보이도록 하는 의사 난수(pseudo random number)를 생성하는 코드이다. srand 함수로 무작위로 정해지는 첫 숫자인 seed를 설정할 수 있다. 위 코드의 경우 time(NULL)을 통해 프로그램을 실행했던 시간 초를 시드값으로 지정햇다. 그리고 rand().. 2022. 11. 17. Bubble sort, Insertion sort, Selection sort Bubble Sorting Algorithm 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 알고리즘의 흐름을 보면 이중 반복문을 통해 안쪽 반복문을 이용하여 0번 인덱스와 1번 인덱스를 비교하고 1번 인덱스와 2번 인덱스를 비교하는 방식으로 i번째 인덱스와 i+1번째 인덱스를 비교한다. 다음으로 바깥 반복문을 수행하려고 보면 마지막 인덱스에는 가장 큰 자료가 도달해있다. 그러면 마지막 인덱스를 제외하고 n-1번째까지 반복문을 진행하면 n-1번째 인덱스에 두번째로 큰 자료가 도착을한다. 따라서 바깥반복문은 j data[j+1]) { temp = data[j+1]; data[j+1] = data[j]; data[j] = temp; } } } } Time complexity Tn = (n-1)+(n-.. 2022. 11. 8. 이전 1 다음 728x90
