728x90 CS8 [Algorithm] Quick Sort 특징 Merge 나 Heap Sort 보다 빠름 시간복잡도 O(n log(n)) 최악의 경우가 O(n^2) #include #include using namespace std; void SwapInt(int& a, int& b) { int temp = a; a = b; b = temp; } void QuickSort(vector& arr) { //배열의 크기가 1이면 정렬할게 없으므로 반환 if (arr.size() arr[pivot] && arr[right] < arr[pivot]) {//left 가 pivot보다 크고, right 가 pivot 보다 작으면 Swap SwapInt(arr[left], arr[right]); left++;//Swap 후 각각 좌로 우로 옮겨줌 right--; } } Sw.. 2023. 4. 23. [Data Structure] Vector 와 List의 차이 Vector 연속적인 메모리 공간에 저장 동적임 삽입 삭제가 중간에서 발생할 시 원소를 옮겨줘야함 접근 O(1) 원소 변경시 iterator 변화 선할당이 발생(size와 capacity 값이 다른 이유) 메모리 할당은 미리 하기 때문에 LIST 보다 빠름(push_back은 list 보다 빠름) List Doubly Linked List로 구현 원소 접근이 느림O(n) list 중간에 삽입 삭제하는 것은 vector 보다 빠름 원소가 변경되도 iterator 동일 2023. 4. 10. [Data Structure] List 특징 Linked List로 구현 원소 접근 O(n) 원소가 변견되어도 iterator 동일 주의 아래 코드는 단방향 Linked List로 구현되어 있음 #include #include using namespace std; template class Node{ private: T data; Node*next; public: Node(T _data){ next = NULL; data = _data; } ~Node(){ if(next!=NULL){ delete next; } } T getData(){ return data; } Node*getNext(){ return next; } void setNext(Node*_next){ next = _next; } void setData(T _data){ data .. 2023. 4. 10. [Algorithm] Merge Sort 특징 안정적인 속도 시간복잡도 O(n log(n)) int*mergeSort(int*_arr, int size){ if(size == 1){ return _arr; } int half = size/2; int*halfArr = new int[half]; for(int i=0; i 2023. 4. 10. 이전 1 2 다음