수정렬하기9 [백준 2750번][C++] 수 정렬하기 - 9. 카운팅 정렬 #include #include #include #include #include #include #include #include #include #include #include using namespace std; void PositiveCountingSort(vector& v, int maxVal) { vector count(maxVal + 1); // 각 데이터 별 개수를 저장할 벡터 for (int i = 0; i < v.size(); i++) { count[v[i]]++; // 각 데이터 별로 갯수를 셈 } // 0부터 오름차순으로 정렬할 것이므로 0번은 구했던 값 그대로이기 때문에 1부터 시작 for (int j = 1; j < count.size(); j++) { // 자신의 값에 이전의 원소.. 2023. 7. 23. [백준 2750번][C++] 수 정렬하기 - 8. 기수 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void RadixSort(vector& v, int maxRadix, int firstIndex) { // maxRadix는 [최대 자릿수 + 1] 이므로 그 이전까지만 반복을 진행 for (int i = 1; i 104, 103은 1번, 555는 5번, 777은 7번 // 0번 인덱스는 해당 자릿수의 값이 없는 경우 // ex) 100의 자릿수 검사 -> 1,.. 2023. 7. 21. [백준 2705번][C++] 수 정렬하기 - 7. 쉘 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void SkipInsertionSort(vector& v, int start, int skipNum) { // 숫자를 건너뛰는 삽입정렬 for (int i = start + skipNum; i = 0; j -= skipNum) { if (v[j] > originNum) { // 앞의 숫자가 더 큰 경우 v[j + skipNum] =.. 2023. 7. 20. [백준 2705번][C++] 수 정렬하기 - 6.병합 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void Merge(vector& v, int left, int mid, int right) { int i = left; // 왼쪽 부분 시작지점 int j = mid + 1; // 오른쪽 부분 시작지점 int k = left; // 원소를 넣을 위치 vector sortedVec(v.size()); // 정렬된 벡터를 저장할 공간 // 왼쪽부분과 오른쪽 부분의 원소들을 하나씩 차례로 비교하여 더 작은 원소를 sortedVec에 넣음. // 왼쪽 부분과 오른쪽 부분은 이미 오름차순으로 정렬되어있는 상태이므로 .. 2023. 7. 19. [백준 2750번][C++] 수 정렬하기 - 5. 삽입 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void InsertionSort(vector& v) { for (int i = 1; i = 0; j--) { if (insertVal swap 아님 // -> 뒤의 원소에 앞의 원소의 값을 넣음 v[j + 1] = v[j]; insertIndex--; } else { /.. 2023. 7. 18. [백준 2750번][C++] 수 정렬하기 - 4. 힙 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void MakeMaxHeap(vector& v) { // 최대힙을 생성하는 함수 // 완전이진트리의 노드번호는 1번부터 시작하기때문에 0번 인덱스를 1번으로 취급해야함 // 0번을 시작으로할때 // 자식노드번호가 홀수인 경우, 부모인덱스 = 자식 인덱스 / 2 // 자식노드번호가 짝수인 경우, 부모인덱스 = 자식 인덱스 / 2 - 1 for (int i = 1; i 가장 큰 수라면 밑 부터 차례.. 2023. 7. 17. [백준 2750번][C++] 수 정렬하기 - 3. 퀵 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; int Partition(vector& v, int left, int right) { // left번 인덱스부터 right번 인덱스를 pivot번 인덱스의 원소를 기준으로 큰 값, 작은 값을 나눔 int pivot = left; // 기준 인덱스 값(고정) int swap = left; // 중간중간 swap에 사용될 인덱스 값 for (int i = left + 1; i v[i]) { swap++; // swap(i swap) int temp = v[i]; v[i] = v[swap]; v[swap] = te.. 2023. 7. 16. [백준 2750번][C++] 수 정렬하기 - 2. 선택 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { int N; cin >> N; vector v; // 원소 입력 while (N > 0) { int x; cin >> x; v.push_back(x); N--; } // 2. 선택정렬 for (int i = 0; i < v.size() - 1; i++) // 마지막 원소는 정렬할 필요없음(이미정렬되어있으므로) { // 최소값의 인덱스와 값을 저장할 공간 생성 int minVal = v[i]; int minIndex = i; for (int j = i + 1; j < v.size(); j.. 2023. 7. 16. [백준 2750번][C++] 수 정렬하기 - 1. 버블 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { int N; cin >> N; vector v; // 원소 입력 while (N > 0) { int x; cin >> x; v.push_back(x); N--; } // 1. 버블 정렬 for (int i = v.size() - 1; i > 0; i--) { for (int j = 0; j v[j + 1]) { int temp = v[j]; v[j] = v[j + 1]; v[j + 1] = temp; } } } // 원소 출력 for (int i.. 2023. 7. 15. 이전 1 다음
