본문 바로가기

전공공부/알고리즘 공부6

(정렬) 정리 정렬 알고리즘 시간 복잡도 실제 소요시간 8 10,000 100,000 600,000 1,000,000 선택정렬 O(n^2) 0.000 0.131 12.523 452.249 1256.739 버블정렬 O(n^2) 0.000 0.522 53.826 1934.580 삽입정렬 O(n) ~ O(n^2) 0.000 0.045 4.515 161.678 449.955 퀵정렬 O(nlogn) 0.000 0.003 0.162 5.186 14.549 합병정렬 O(nlogn) 0.005 1.496 26.911 87.604 268.532 2022. 3. 25.
(정렬) 버블정렬 pseudo code 입력 : 크기가 n인 배열 A 출력 : 정렬된 배열 A for pass = 1 to n-1 for i = 1 to n-pass if(A[i-1]>A[i]) A[i-1]A[i] return 배열 A c 코드 #include #include #include void swap(int* n1, int* n2) { int tmp = *n1; *n1 = *n2; *n2 = tmp; } void BubbleSort(int* A, int num) { for (int i = 0; i A[k]) { swap(&A[k - 1], &A[k]); } } } } 실행시간 8개 : 0.0.. 2022. 3. 24.
(정렬) 삽입 정렬 pseudo code 입력: 크기가 n인 배열 A 출력: 정렬된 배열 A for i = 1 to n-1 { CurrentElement = A[i] j = 0) and (A[j]>CurrentElement){ A[j+1] = A[j] j left) { A[j + 1] = A[j]; j = j - 1; } A[j + 1] = left; } } 실행시간 8개 : 0.000 10,000개 : 0.045 100,000개 : 4.515 600,000개 : 161.678 1,000,000개 : 449.955 2022. 3. 24.
(정렬) 퀵정렬 pseudo code QuickSort(A, left, right) 입력: 배열 A[left]~A[right] 출력: 정렬된 배열 A[left]~A[right] if(left < right){ 피봇을 A[left]~A[right] 중에서 선택하고, 피봇을 A[left]와 자리를 바꾼 후, 피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left]~A[p-1]로 옮기고, 피봇보다 큰 숫자들은 A[p+1]~A[right]로 옮기며, 피봇은 A[p]에 놓는다. QuickSort(A, left,p-1); QuickSort(A,p+1,right); } c 코드 #include #include #include void swap(int* n1, int* n2) { int tmp = *n1; *n1 = *.. 2022. 3. 23.

티스토리툴바