자료구조튜터링-8.정렬

문제 설명

파일로부터 n개의 실수 데이터를 1차원 배열로 입력받아 오름차순으로 정렬하는 3가지 알고리즘(삽입정렬, 퀵정렬, 힙정렬)들을 구현한 후 정렬 결과와 원소의 실제 실행 시간(또는 비교 횟수)를 구해서 화면에 출력한다.

삽입 정렬

정렬되어 있는 앞 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복하는 정렬이다. 최선의 경우 비교 횟수는 n-1번이며 최악의 경우는 n(n-1)/2번으로 오더가 n^2이다.

퀵 정렬

평균적으로 가장 빠른 정렬 방법으로 분할정복 기법을 이용한다. 축값(pivot)을 중심으로 하나의 리스트를 축값보다 작은 부분리스트와 축값보다 큰 부분리스트로 분할하고, 각 부분리스트를 다시 퀵정렬하는 재귀호출 과정을 통해 정렬한다. 최선의 경우 패스 수는 nlog2n이며, 각 패스 안에서의 비교횟수는 n으로 총 비교횟수는 nlog2n이다. 극도로 불균등하게 부분리스트로 분할되는 최악의 경우 패스 수는 n이며, 각 패스 안에서의 비교횟수도 n으로 총 비교 횟수는 n^2이 된다.

힙 정렬

힙을 이용하여 정렬한다. 먼저 정렬해야 할 n개의 원소들을 최대 힙으로 구성한 후 루트(최대값)과 가장 마지막 원소를 교환한 다음, 마지막 원소(최대값)을 제외하고 downheap을 반복적으로 수행하며 정렬한다. n개의 원소를 최대 힙으로 구성하기 위해서는 o(n)만큼의 시간이 소요되고, downheap 연산을 n-1번 수행해야 하므로의 시간이 걸린다. 따라서 전체적으로 O(nlogn2) 시간이 걸린다.

코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SWAP(a, b, c){c = a; a = b; b = c;} //a와 b의 데이터를 바꿈

void insert(int n, double list[], int *pcom) { // 삽입정렬
	int i, j; //왼쪽 인덱스는 정렬이 안되고 오른쪽 인덱스는 정렬됨
	double key;
	for (i = 2; i <= n; i++) {
		key = list[i]; //정렬안된 왼쪽 인덱스의 가장 첫 원소를 key로 정함
		for (j = i - 1;  (*pcom)++ >= 0&& j >= 1 && list[j] > key; j--) { //정렬된 오른쪽 원소들과 비교하며
			list[j + 1] = list[j]; //key값의 올바른 위치 정함
		}
		list[j + 1] = key;
	}
}

int partition(double list[], int **ppcom, int left, int right) { //퀵정렬
	double temp = 0;
	int low = left;
	int high = right + 1;
	double pivot = list[left]; //가장 왼쪽 데이터 pivot으로 정한 후
	do {
		do
			low++;
		while ((**ppcom)++ >= 0 && (low <= right) && (list[low] < pivot)); //왼쪽에서 pivot보다 큰 수 찾음
		do
			high--;
		while ((**ppcom)++ >= 0 && (high >= left) && (list[high] > pivot)); //오른쪽에서 pivot보다 작은 수 찾아서
		if (low < high) SWAP(list[low], list[high], temp); //바꿈
	} while (low < high); //low가 high보다 작을 때 반복하며
	SWAP(list[left], list[high], temp); //마지막으로 high와 pivot값 바꿔서 pivot을 올바른 위치에 정렬함
	return high; //정렬된 pivot index 반환함
}

void quick(double list[], int *pcom, int left, int right) { //퀵정렬
	if (left < right) { 
		int q = partition(list, &pcom, left, right); //pivot 정렬 후 위치 반환 받음
		quick(list, pcom, left, (q - 1)); //pivot의 왼쪽 list에 대해 다시 퀵정렬
		quick(list, pcom, (q + 1), right); //pivot의 오른쪽 list에 대해 다시 퀵정렬
	}
}

void adjust(double list[], int root, int n, int **ppcom) { //힙정렬
	double rootkey = list[root]; //rootkey설정
	int child = 2 * root; //root의 왼쪽 자식 노드
	while (child <= n) { //root가 오른쪽 자식 노드도 있으면
		if ((child < n) && ((**ppcom)++ >= 0) && (list[child] < list[(child + 1)])) //왼쪽자식노드와 오른쪽 자식 노드 중
			child++; //더 큰 값 선택
		if (((**ppcom)++ >= 0) && (rootkey > list[child])) break; //자식 노드가 rootkey보다 크다면
		else {
			list[(child / 2)] = list[child]; //자식노드의 데이터 부모노드에 저장
			child = 2 * child; //다음 자식노드와 rootkey 다시 비교
		}
	}
	list[(child / 2)] = rootkey; //rootkey 올바른 자리에 정렬
}

void heap(double list[], int n, int *pcom) { //힙정렬
	int i;
	double temp = 0;
	for (i = (n / 2); i >= 1; i--) //작은 heap부터 
		adjust(list, i, n, &pcom); //최대힙 정렬을 함
	for (i = (n - 1); i >= 1; i--) {
		SWAP(list[1], list[i + 1], temp); //최대값(첫 인덱스)을 정렬 안 된 부분의 가장 끝 데이터와 바꾸고
		adjust(list, 1, i, &pcom); //첫 인덱스로 올라온 데이터를 downheap으로 정렬함
	}
}

int main(void) {
	FILE *fp = NULL; //파일 포인터 변수
	int n, com_i = 0, com_q = 0, com_h = 0; // 비교 횟수

	double *list_i = NULL; //insert 정렬 데이터 담을 list
	double *list_q = NULL; //quick 정렬 데이터 담을 list
	double *list_h = NULL; //heap 정렬 데이터 담을 list
	double d = 0;
	char filename[] = "r_data3.txt"; // 파일 열고
	fp = fopen("c://r_data3.txt", "r");
	fscanf(fp, "%d", &n); //첫 데이터(데이터 수) 입력 받은 후
	list_i = (double*)malloc(sizeof(double)*(n + 1)); //데이터수 + 1 만큼 배열 생성
	list_q = (double*)malloc(sizeof(double)*(n + 1));
	list_h = (double*)malloc(sizeof(double)*(n + 1));
	for (int i = 1; i <= n; i++) { //인덱스의 1번부터 데이터 수 만큼
		fscanf(fp, "%lf", &d); //데이터 저장
		list_i[i] = d;
		list_q[i] = d;
		list_h[i] = d;
	}

	insert(n, list_i, &com_i); //삽입정렬
	quick(list_q, &com_q, 1, n);
	heap(list_h, n, &com_h);

	fclose(fp); //파일 닫고

	printf("========== 삽입정렬 ==========\n"); //정렬된 데이터 출력
	printf("입력 파일 = %s (n = %d)\n", filename, n);
	printf("정렬 결과 = ");
	for (int i = 1; i <= 10; i++) {
		printf("%f ", list_i[i]);
	}
	printf("\n\t    ...\n\t    ");
	for (int j = n - 9; j <= n; j++) {
		printf("%f ", list_i[j]);
	}
	printf("\n비교 횟수 = %d\n", com_i);

	printf("\n========== 퀵정렬 ==========\n"); //정렬된 데이터 출력
	printf("입력 파일 = %s (n = %d)\n", filename, n);
	printf("정렬 결과 = ");
	for (int i = 1; i <= 10; i++) {
		printf("%f ", list_q[i]);
	}
	printf("\n\t    ...\n\t    ");
	for (int j = n - 9; j <= n; j++) {
		printf("%f ", list_q[j]);
	}
	printf("\n비교 횟수 = %d\n", com_q);

	printf("\n========== 힙정렬 ==========\n"); //정렬된 데이터 출력
	printf("입력 파일 = %s (n = %d)\n", filename, n);
	printf("정렬 결과 = ");
	for (int i = 1; i <= 10; i++) {
		printf("%f ", list_h[i]);
	}
	printf("\n\t    ...\n\t    ");
	for (int j = n - 9; j <= n; j++) {
		printf("%f ", list_h[j]);
	}
	printf("\n비교 횟수 = %d\n", com_h);

	free(list_i); //할당받은 데이터 free시킴
	free(list_q);
	free(list_h);
}

Dataset(d_data1.txt)

1000
34984.1379 34946.5054 34828.1038 34769.0368 34761.348 34749.3474 34731.5817 34711.6811 34630.7671 34625.2033 34548.8834 34538.6211 34530.0604 34494.6243 34477.5488 34457.0416 34450.2868 34328.7218 34276.9021 34266.0823 34190.3322 34179.3518 34124.548 34114.8123 34083.3726 34018.5786 34014.9219 33910.6842 33881.1894 33798.7756 33678.6101 33676.8022 33662.9995 33659.422 33629.1515 33598.6154 33573.6905 33555.8566 33546.5415 33482.6286 33472.5346 33434.1639 33403.9013 33388.4054 33369.3465 33365.5374 33300.0686 33242.6963 33217.5132 33196.0854 33184.8223 33169.7543 33095.6787 33035.4237 32972.0933 32909.5417 32869.2346 32866.5123 32850.8855 32833.5221 32829.544 32748.6088 32708.9312 32701.2116 32659.3833 32654.1624 32645.4747 32556.1553 32555.296 32544.5923 32522.8832 32521.7863 32503.2335 32495.0817 32493.9804 32439.6849 32415.7406 32406.4163 32359.8682 32355.099 32333.515 32289.1398 32193.9461 32188.5866 32177.5961 32175.27 32131.5655 32124.9847 32082.2196 31992.7585 31984.914 31979.7709 31959.0078 31953.0927 31937.7433 31919.3631 31845.5683 31781.0325 31780.0498 31776.1751 31751.6616 31719.8792 31654.3188 31628.174 31608.9936 31500.7565 31429.1147 31381.2457 31323.7399 31322.6232 31219.2117 31169.7116 31068.6522 31043.6769 31026.0139 31023.3791 30978.211 30962.7726 30902.5125 30873.9991 30854.5627 30822.4911 30815.1398 30761.1919 30713.0767 30532.1665 30450.2796 30428.4128 30416.599 30409.8989 30344.7738 30336.4372 30327.7272 30321.9786 30315.7103 30277.1407 30158.228 30147.7367 30124.4044 30123.4164 29997.3033 29993.4296 29981.9295 29965.4695 29920.3926 29859.8419 29812.4622 29778.1756 29631.7497 29597.4946 29552.0487 29488.1655 29481.6219 29478.6534 29465.4852 29379.5436 29371.8821 29318.8163 29232.4432 29227.8242 29073.8916 29004.1813 28955.4252 28906.0191 28891.8091 28880.8897 28838.4435 28737.8177 28707.5025 28643.0224 28629.4522 28624.8643 28622.7034 28617.7527 28506.7816 28475.7383 28432.9103 28391.6075 28349.8145 28324.8449 28296.4104 28272.4787 28226.5069 28209.8359 28134.5634 28124.8053 28037.5073 28002.9172 27995.8191 27960.8178 27958.1439 27828.3544 27824.5265 27791.2924 27749.7963 27738.9466 27725.1733 27663.053 27584.5114 27553.4302 27530.1037 27441.1123 27416.2758 27395.5885 27383.691 27366.7421 27359.246 27316.5096 27311.8867 27295.8392 27273.3661 27225.2608 27204.4298 27148.152 27117.1099 27099.0778 27017.2111 26963.6952 26948.1427 26823.6809 26785.0747 26706.4017 26687.9323 26553.8893 26459.8761 26444.3463 26438.5346 26429.2257 26363.9536 26352.2914 26317.8621 26314.9726 26202.9232 26069.1959 26017.4918 25971.2816 25918.375 25870.4395 25867.7954 25845.1223 25843.5513 25836.0027 25831.6621 25812.5734 25795.6748 25791.5307 25763.1759 25760.249 25719.8365 25695.4571 25687.233 25670.3094 25660.7097 25656.0353 25653.7799 25618.5244 25500.0176 25489.7004 25482.1053 25478.8216 25414.9561 25397.5405 25344.0929 25293.6654 25255.8969 25200.4818 25164.7674 25161.3222 25154.5128 25132.3023 25123.4653 25117.082 25039.1234 25023.4357 24973.6817 24917.2744 24907.8884 24815.8564 24784.9741 24763.2597 24756.661 24740.2456 24728.2999 24698.5672 24693.8069 24674.0141 24661.5113 24631.4425 24605.0222 24582.6036 24570.7908 24507.7169 24502.8781 24462.1905 24456.8213 24378.3863 24344.632 24336.3689 24313.8161 24307.9101 24291.4614 24198.9999 24181.5299 24176.7087 24069.6142 24058.8016 24035.9613 23972.7125 23950.8381 23911.231 23903.583 23878.3794 23829.5838 23819.9427 23806.9321 23739.2293 23737.6205 23727.6573 23694.6032 23668.1872 23614.9519 23603.5828 23558.3958 23493.3507 23461.3869 23344.0757 23343.8401 23341.9003 23327.3607 23325.0471 23291.2727 23209.0138 23185.1782 23122.4872 23016.0342 22995.8964 22994.3398 22936.5616 22914.8075 22911.8968 22909.5612 22881.6611 22865.1124 22857.9846 22752.1742 22655.8752 22642.4524 22635.7267 22607.0985 22508.8636 22492.1241 22476.7765 22441.3278 22433.9738 22426.3739 22406.6625 22391.6366 22323.1989 22314.0514 22300.1521 22289.3983 22268.5546 22264.1999 22263.1657 22225.9741 22107.8548 22105.6135 22092.6477 22045.3847 21923.6816 21896.2129 21802.7687 21792.2246 21788.7427 21746.5411 21726.1084 21720.5841 21715.1319 21714.7084 21692.8965 21682.1336 21525.7085 21448.7101 21421.7565 21378.6065 21307.0504 21267.5757 21215.2669 21206.6383 21174.2006 21142.5014 21111.7225 21067.5518 21062.5711 21047.8083 20966.1041 20904.7623 20894.4974 20740.5581 20732.8415 20583.81 20558.5595 20523.7646 20504.2101 20414.5857 20406.8152 20389.2004 20353.239 20331.0406 20328.6994 20232.3094 20224.0158 20210.0208 20164.6556 20124.9242 20100.326 20097.9195 20067.3793 20062.392 20035.5407 20027.7639 20012.3166 19993.8885 19978.0585 19964.7508 19937.6202 19923.7577 19921.08 19851.6678 19834.7864 19788.6305 19715.3191 19699.8397 19690.7733 19550.7494 19536.2279 19465.9037 19390.0817 19339.1673 19320.9887 19295.9717 19265.0978 19162.947 19137.986 19127.0087 19112.1968 19030.9279 19023.4926 18982.516 18964.1073 18962.6728 18957.5354 18930.7585 18857.025 18800.7612 18783.2521 18772.2969 18741.2893 18738.939 18698.8539 18666.9601 18606.0278 18595.0225 18575.9092 18534.2247 18530.4649 18387.1789 18358.4963 18243.8235 18197.5427 18151.1533 18137.9774 18056.5345 17991.0277 17961.2918 17828.8818 17803.6149 17768.226 17759.2933 17742.248 17725.4936 17718.9595 17704.2781 17700.5455 17588.3103 17558.4345 17518.0478 17513.9948 17503.6137 17454.8612 17445.8238 17438.3727 17350.3199 17314.6555 17298.9122 17289.7523 17288.6635 17279.46 17249.8137 17237.1034 17236.6647 17228.7523 17216.2897 17193.6926 17192.9111 17191.7654 17141.2813 17140.9926 17049.5442 16956.5459 16842.7083 16797.7338 16795.5784 16771.6846 16734.4311 16699.4667 16687.661 16656.2542 16604.6488 16581.7882 16492.7131 16457.3327 16437.3512 16435.32 16399.9692 16385.0611 16383.5501 16378.6941 16316.865 16310.5382 16271.5229 16249.2198 16184.7519 16117.5692 16078.9441 15975.3179 15969.1585 15882.2202 15879.8747 15875.2949 15829.2309 15792.9694 15783.8636 15692.6663 15684.1184 15660.169 15647.9697 15637.0901 15612.4049 15557.3276 15447.7812 15446.5986 15125.1829 15049.2587 15044.2775 14985.5445 14966.5126 14947.8296 14849.839 14820.6368 14788.8103 14748.0102 14736.8142 14717.0462 14599.3792 14536.7098 14506.8475 14501.7263 14420.5794 14352.6682 14346.9074 14342.1294 14318.3771 14205.842 14177.1255 14130.2237 14103.195 14059.0588 14030.5263 13980.9279 13918.2078 13848.0224 13828.8099 13776.9774 13766.884 13697.4222 13654.034 13611.4767 13607.9075 13590.3408 13584.5497 13551.56 13546.0998 13530.0535 13521.5105 13480.4507 13468.1868 13375.6336 13365.1824 13335.7522 13283.4452 13172.8924 13158.8104 13131.9508 13125.2998 13079.1066 12981.3362 12922.3664 12890.0643 12879.8743 12830.2488 12822.9546 12807.2591 12799.1 12761.1338 12751.6868 12704.9809 12702.7189 12698.4519 12676.4876 12662.5364 12557.9393 12548.8757 12538.3454 12525.1675 12474.8233 12371.2661 12330.3524 12323.4817 12271.3774 12244.0712 12214.9473 12195.346 12155.0195 12110.8736 12037.7586 12024.9788 12019.2983 12017.9246 11975.6977 11954.8843 11910.8746 11901.4642 11883.9698 11875.1269 11872.4628 11864.8638 11861.9476 11853.7179 11841.4474 11812.4748 11811.7269 11768.5412 11681.0833 11673.1348 11643.7079 11585.0367 11577.6264 11576.6135 11554.5762 11460.2024 11372.8696 11360.674 11284.4456 11231.1114 11220.7004 11206.6109 11119.2094 11060.8459 11059.6536 11050.7352 11019.013 10872.7237 10864.9165 10840.192 10824.773 10776.0997 10745.6299 10658.7549 10641.5982 10640.3814 10628.1821 10552.412 10535.3765 10534.5274 10532.5853 10529.4792 10500.391 10445.2381 10426.6478 10420.28 10406.4738 10391.788 10389.3326 10348.9206 10337.8053 10327.8453 10244.0054 10206.5544 10202.138 10189.446 10172.4582 10166.4462 10124.6258 10091.237 10053.4733 10022.0867 10007.6846 9938.2886 9815.6898 9724.2683 9702.1472 9663.814 9642.0829 9611.5781 9570.5857 9552.4538 9543.7128 9523.0702 9495.1586 9417.311 9408.6687 9401.6393 9390.4351 9359.9973 9301.6548 9276.5658 9270.5962 9215.3252 9213.3329 9139.874 9125.7233 9104.3198 9035.1348 9022.1622 9005.4445 9003.5963 8985.2276 8983.0081 8957.5236 8941.5498 8930.4706 8860.7255 8819.0952 8807.6373 8804.7327 8763.9382 8730.3733 8700.4146 8680.768 8648.4023 8644.1694 8630.8462 8617.3848 8554.4216 8493.4978 8473.5991 8469.904 8426.6214 8376.066 8247.0118 8230.4752 8212.0554 8208.595 8085.2259 8010.0749 7958.718 7922.2423 7896.5838 7872.7553 7848.7593 7762.7629 7748.8135 7734.2611 7697.4541 7668.0974 7646.0566 7573.0981 7566.9461 7544.6866 7497.7665 7383.2193 7373.6783 7339.802 7286.6456 7285.3167 7244.0971 7224.8694 7216.8652 7116.1409 7071.5695 7068.0042 7056.5538 7044.5901 7033.7016 7016.06 6972.8677 6931.5833 6917.8966 6899.7814 6886.6453 6873.6017 6865.3225 6840.7742 6832.1875 6822.1011 6790.0312 6757.4431 6739.8605 6721.7096 6687.0765 6676.2716 6614.9606 6609.5436 6582.1405 6559.759 6524.6485 6518.1865 6430.144 6381.9341 6341.7368 6333.7777 6324.9326 6177.7954 6175.6023 6153.6697 6114.0716 6082.1891 6049.1073 6031.362 6028.01 6014.1533 5876.6563 5773.1169 5770.0677 5716.5942 5624.9265 5613.5099 5607.6935 5562.6882 5499.6871 5416.5397 5396.2693 5388.8209 5320.8306 5304.7853 5277.8265 5237.892 5210.1878 5167.9469 5154.9334 5114.0936 5113.097 5108.0555 4917.9084 4841.9678 4732.6668 4721.6548 4674.2212 4667.8899 4641.8588 4634.016 4606.6283 4598.0555 4583.7923 4452.0076 4428.0028 4413.385 4357.0185 4340.4168 4331.3694 4317.5591 4309.5811 4299.3132 4198.6259 4102.6255 4050.8155 4010.11 3989.3302 3968.2625 3941.2579 3878.5372 3809.0752 3796.0671 3740.6982 3684.8156 3683.7803 3646.3937 3586.7757 3574.1139 3506.9456 3455.4022 3438.126 3424.9734 3418.7374 3388.3328 3309.2303 3289.9317 3285.7208 3138.7396 3067.3402 3017.7611 2935.1141 2901.4291 2894.7528 2888.8607 2876.1115 2847.0395 2809.9441 2784.5064 2692.9016 2639.8655 2584.4883 2473.8532 2467.432 2425.516 2420.4121 2404.3821 2390.7605 2291.7503 2266.1776 2251.2834 2249.4104 2241.848 2235.7242 2172.6065 2143.2725 2073.9734 2059.2494 2040.1964 1992.5206 1967.1822 1934.6877 1926.7469 1923.9722 1918.4894 1902.9401 1822.7693 1793.9098 1683.9921 1629.7067 1628.3793 1595.8989 1576.5063 1547.7709 1528.99 1468.1844 1417.8779 1397.0888 1333.8413 1323.3661 1302.1264 1300.3154 1284.2897 1263.2511 1225.9055 1207.527 1206.8174 1193.9081 1165.2129 1158.4547 1155.6021 1079.1032 1056.6033 1011.2735 994.0313 948.8914 927.5855 868.9127 823.1312 822.2888 817.6334 808.0928 771.8399 745.9508 721.9953 694.7522 661.7128 604.1237 576.6119 568.7607 453.0381 357.6539 341.3964 309.1407 272.7945 247.802 232.1264 231.2615 227.3659 219.5062 209.4667 186.6163 177.1573 174.0658 171.5271 163.8831 158.901 109.6181 68.636

Dataset(a_data1.txt)

1000
40.7425 56.7188 61.2118 66.2228 68.2104 134.378 137.5913 155.8475 194.8303 211.1809 218.9985 240.5506 243.263 273.5229 283.7739 300.4666 347.0022 392.2238 446.7525 450.3512 479.7945 492.8313 541.753 565.2784 569.1443 576.572 584.4611 786.3926 829.0853 844.7691 862.4472 887.0393 911.6595 923.2856 938.2637 957.3679 1007.4219 1078.6965 1090.009 1175.1398 1214.9199 1241.5299 1275.7056 1279.2797 1298.9889 1365.2026 1630.5766 1664.2075 1689.6667 1703.1051 1803.3713 1840.7957 1856.7096 1979.576 1997.317 2043.4296 2070.3664 2083.3648 2110.9853 2166.7557 2238.1031 2247.8258 2248.7245 2280.7912 2304.4963 2314.6652 2337.7178 2372.5835 2390.1483 2460.4608 2468.6169 2491.4905 2499.0563 2504.0063 2601.4552 2690.5757 2734.7753 2773.9639 2783.8544 2797.2174 2869.0072 2942.2555 3041.1722 3059.7192 3113.6914 3239.7127 3265.6934 3286.4986 3334.2388 3464.951 3466.0249 3480.1301 3516.9662 3524.4211 3599.9175 3624.3216 3638.0888 3692.1474 3705.1326 3790.956 3880.9784 3937.3957 4097.8119 4098.5495 4110.9716 4145.2685 4229.9082 4273.7039 4351.5755 4432.7521 4450.9142 4468.4166 4561.0127 4583.9007 4648.2891 4676.5557 4684.4211 4746.7001 4767.6984 4786.393 4798.8073 4871.3004 4910.1708 4936.1119 5146.929 5204.4831 5230.5664 5272.6748 5331.2378 5340.6329 5363.6031 5407.0658 5416.2876 5449.593 5454.8399 5464.516 5561.8342 5621.8769 5622.9906 5680.0411 5715.553 5728.1044 5766.4104 5771.4474 5827.2686 5844.1125 5856.8959 5863.4343 5888.0375 5915.5736 5933.6492 5964.2986 5981.9741 6000.6928 6052.1061 6132.1966 6139.7053 6145.4033 6172.0284 6187.3732 6203.3518 6227.9181 6254.328 6272.5763 6291.7237 6319.3123 6324.3823 6339.7917 6386.2634 6408.9064 6434.856 6435.6308 6457.0047 6498.9851 6523.5413 6525.6286 6566.0222 6569.7375 6621.5923 6648.0331 6651.5266 6756.1299 6790.8083 6808.3157 6831.9237 6870.2176 6906.4173 7032.1466 7046.2422 7075.7092 7090.0985 7108.3446 7135.7308 7143.3531 7149.3871 7267.2458 7272.4332 7275.7293 7290.0457 7307.1556 7311.9236 7346.0846 7415.0005 7477.6627 7547.7029 7557.3829 7618.3563 7626.3022 7636.2043 7665.0135 7722.7313 7779.4271 7788.5589 7865.9181 7892.9003 7908.9671 7909.8626 8016.693 8084.0609 8121.3205 8141.7967 8163.3646 8175.2932 8177.2497 8181.5706 8191.4959 8315.9015 8393.5306 8401.5705 8496.1153 8506.6785 8525.9945 8561.3899 8570.9799 8662.9043 8686.3448 8739.5614 8754.1645 8780.6133 8859.3811 8908.3125 8971.3659 9004.4605 9035.0251 9060.1327 9083.5082 9090.1811 9161.9805 9205.4936 9219.7088 9281.553 9294.1883 9307.9311 9326.9856 9409.2713 9424.0302 9429.4886 9447.4432 9454.5476 9463.3987 9479.7162 9643.4253 9677.6001 9752.1145 9773.8938 9848.1399 9879.3036 9898.3744 9924.4602 9928.1735 9933.1752 9962.7593 10058.7255 10107.371 10169.8685 10247.3613 10271.5601 10292.8233 10306.1045 10315.3849 10427.0495 10464.1049 10480.1484 10501.9832 10583.8096 10586.174 10662.5133 10692.1532 10735.7291 10739.7608 10748.8422 10846.4692 10850.7398 10855.5569 10988.2311 11053.6381 11112.5911 11136.4275 11218.4551 11294.5028 11324.5728 11354.5641 11382.8756 11383.588 11463.7458 11513.2571 11518.1114 11543.2019 11555.1598 11577.005 11581.1423 11659.809 11662.2638 11695.692 11743.5174 11798.7246 11870.6116 11883.8488 11942.5516 12003.8916 12056.1065 12138.0216 12186.7207 12224.0797 12343.8201 12381.8709 12395.3807 12398.0744 12411.2721 12447.2937 12527.4045 12536.0796 12586.7227 12611.9378 12658.6755 12704.8084 12725.9853 12728.2198 12771.0087 12798.1318 12832.5732 12841.5139 12858.1195 12872.4025 12884.4328 12888.6369 12944.9497 12960.6634 13019.8807 13044.2086 13046.0961 13053.7492 13118.0879 13119.5534 13143.096 13256.2437 13274.2096 13304.8361 13308.8038 13309.7968 13315.5189 13339.9995 13375.5747 13393.4647 13406.8221 13425.9139 13477.1625 13603.2393 13606.1979 13608.405 13660.073 13709.8653 13776.57 13781.8973 13783.7484 13826.0171 13829.4883 13893.3337 13917.8588 13919.9372 13974.2317 13977.9356 14046.1709 14048.3058 14091.603 14103.1349 14108.2841 14150.2668 14194.515 14201.589 14266.8115 14371.3654 14374.3406 14414.8086 14426.605 14495.8442 14523.1177 14534.1502 14595.2641 14637.6079 14657.7301 14686.1292 14717.8956 14720.1493 14723.0445 14729.9209 14738.3363 14762.3389 14794.5001 14804.2553 14807.8776 14829.3839 14881.5642 14947.3315 14956.4605 14961.0383 15005.8089 15022.9318 15049.0815 15091.6444 15092.8575 15095.2957 15134.1874 15179.4579 15379.8472 15395.342 15415.635 15422.3353 15430.2556 15431.8949 15434.9565 15445.004 15457.4132 15481.9811 15542.7189 15545.3439 15583.2076 15616.893 15645.6785 15653.1517 15680.12 15689.6257 15707.7216 15731.3817 15737.9074 15740.3398 15792.1472 15841.9045 15879.1573 15898.417 15941.1578 16001.7608 16055.7608 16082.4297 16089.0506 16113.2941 16130.1803 16188.6859 16207.2811 16209.802 16215.1052 16221.0127 16285.5128 16327.8299 16404.8569 16427.6606 16526.8864 16576.5848 16593.3785 16643.4072 16669.9201 16685.6645 16696.4666 16716.5299 16751.5365 16790.2762 16870.2551 16875.0006 16890.8773 16951.0827 16977.435 16982.3904 16985.9862 17038.6472 17050.7106 17058.6528 17118.2619 17146.713 17165.1892 17198.0907 17278.6893 17291.5695 17307.4208 17325.6694 17333.8562 17411.1791 17424.3756 17500.4317 17528.0485 17541.0809 17561.5917 17691.9467 17714.0468 17735.5485 17751.233 17772.5923 17779.4603 17831.4338 17847.3415 17848.7925 17858.2056 17864.851 17866.7513 17870.7485 17936.9433 17956.0963 18002.1405 18005.6688 18030.1597 18077.4661 18107.1986 18119.6499 18135.1417 18145.4441 18176.7537 18198.5445 18212.3317 18213.8192 18236.8909 18301.1726 18315.2997 18319.0454 18430.1156 18457.0696 18497.7619 18511.3894 18543.1223 18602.2218 18613.5712 18758.7335 18765.5956 18775.2178 18822.169 18878.5462 18880.1322 18935.7956 18944.8547 19015.7405 19058.0199 19118.2549 19201.0008 19207.127 19265.964 19292.7059 19333.2207 19351.9959 19360.6968 19404.4216 19464.0479 19558.2699 19565.049 19571.5011 19604.6751 19611.1956 19619.3634 19697.2285 19743.8282 19793.7387 19799.0123 19814.9094 19827.7857 19845.6502 19857.8774 20017.8722 20028.9274 20032.4097 20102.7499 20111.5658 20135.2459 20153.9302 20199.176 20273.4553 20311.0687 20312.3087 20422.4429 20456.3665 20466.0978 20477.2325 20510.5297 20565.3846 20570.192 20598.8668 20766.7341 20772.7327 20788.554 20803.3885 20811.0542 20816.0019 20849.7519 20913.3784 20964.6908 20974.376 20982.0423 20994.2147 21024.6047 21054.849 21058.1085 21082.0402 21083.1099 21237.6757 21246.1987 21251.0023 21312.1732 21338.5424 21369.3663 21443.565 21485.7788 21586.775 21640.8655 21645.2002 21661.3559 21703.0674 21710.7082 21740.8907 21747.2111 21809.465 21833.851 21868.753 21876.7722 21926.9374 21968.7132 21987.4933 22033.5649 22201.6481 22238.0782 22257.3606 22269.7427 22286.3399 22310.4709 22449.3676 22532.5092 22619.0763 22685.5419 22734.34 22752.2718 22755.483 22765.7747 22801.8291 22851.7062 22916.2162 22917.2102 22933.9841 22938.6382 22972.2032 22994.8164 23011.9207 23056.6763 23145.3487 23184.0837 23191.9223 23248.5137 23262.7492 23278.1234 23282.1366 23298.1434 23321.4004 23329.4404 23421.5597 23449.5342 23461.6441 23474.8689 23546.5197 23573.8173 23584.0981 23592.3977 23625.0502 23626.3524 23652.0106 23721.3247 23725.5797 23794.2119 23809.3382 23890.0061 23961.9879 23978.0201 23989.2627 24056.9109 24094.995 24124.3741 24127.826 24143.4418 24161.9633 24168.681 24178.1387 24179.8164 24320.3656 24340.3117 24465.7736 24502.3805 24525.53 24533.2442 24642.9 24654.1004 24720.242 24723.6451 24753.3981 24790.3674 24797.4496 24934.0221 24951.7591 24967.0015 24985.6888 25017.4321 25021.8691 25025.4429 25055.6595 25217.0055 25250.1044 25255.8587 25261.667 25277.4456 25303.0606 25310.957 25331.8463 25463.4341 25465.2011 25466.7523 25491.908 25517.6928 25527.1153 25594.6678 25598.8643 25610.2946 25801.4376 25908.4414 25913.2512 25921.3199 26027.525 26077.4401 26087.5586 26092.0281 26121.009 26217.244 26218.6513 26265.4154 26270.3529 26312.1228 26325.4773 26330.9289 26350.3239 26381.4768 26408.9134 26429.9621 26548.5614 26553.6513 26554.0501 26587.787 26594.5975 26658.152 26678.1674 26685.9979 26739.2204 26750.401 26768.6891 26771.3372 26796.0374 26846.4679 26857.2515 26858.0311 26899.7274 26948.3586 26963.969 26985.8847 26996.1797 27019.6392 27197.38 27217.0939 27261.094 27297.8274 27359.9565 27412.7506 27437.1168 27474.0341 27485.8718 27539.622 27544.8083 27553.7961 27577.6005 27581.5069 27664.112 27689.5219 27700.1395 27729.6388 27754.8671 27767.7375 27820.9605 27831.4644 27870.794 27940.5202 27970.7335 28013.7624 28045.1631 28154.8259 28166.5206 28177.8724 28209.1382 28258.8388 28305.9364 28314.1481 28338.338 28377.5779 28389.4428 28454.7839 28459.3284 28466.0686 28488.1194 28523.7901 28561.7956 28564.9183 28566.8873 28695.6357 28720.5967 28724.746 28781.7496 28797.1094 28813.5431 28938.2648 28959.758 28973.0539 29027.968 29069.0273 29112.9381 29155.3734 29287.8563 29327.963 29358.6711 29417.6878 29450.5719 29475.7347 29481.2499 29493.5435 29498.3537 29525.9218 29530.8131 29544.1141 29553.149 29624.5296 29656.7254 29707.3024 29711.7242 29717.866 29718.9498 29757.6285 29777.9768 29789.1089 29791.2186 29835.1866 29849.2595 29852.8009 29937.8158 29979.2793 29997.3902 30016.5764 30022.4619 30023.5186 30025.9441 30029.8208 30070.2991 30148.1514 30164.5083 30349.6483 30376.2134 30478.9454 30491.1547 30549.8453 30582.6263 30600.377 30609.6225 30716.4593 30718.1589 30720.6521 30722.1572 30756.1288 30794.288 30830.2174 30871.4034 30903.663 30966.2543 30996.9848 31005.3476 31034.9167 31035.4634 31085.2605 31091.1538 31099.9535 31113.0652 31198.0675 31208.8815 31215.2416 31258.7925 31283.3286 31311.3018 31443.0677 31515.7175 31537.2453 31565.9945 31568.2595 31677.3379 31946.0104 31966.1521 31969.5934 31975.9783 32120.8894 32134.705 32139.7641 32158.9572 32230.3024 32238.5594 32395.909 32447.6539 32493.5328 32592.917 32604.2755 32606.2428 32632.4286 32733.0479 32748.075 32789.5186 32792.1432 32803.3109 32848.4942 32858.6328 32891.5104 32894.1457 32913.9446 32921.2195 32958.6186 33015.7693 33088.5134 33100.8918 33117.5064 33138.6322 33182.0293 33199.0429 33222.9531 33229.2728 33232.7657 33280.9773 33326.1138 33344.2759 33357.4443 33359.052 33362.2873 33384.4197 33434.8529 33594.0327 33624.412 33663.2442 33676.261 33707.789 33715.9599 33720.9101 33735.7223 33748.2008 33761.249 33798.8296 33816.14 33817.6147 33829.6913 33840.1551 33865.8715 33894.6696 33911.4982 33954.8359 33999.8779 34018.8678 34055.5321 34056.9505 34095.7995 34097.7873 34131.8863 34149.5116 34195.6009 34206.3623 34275.291 34288.4675 34364.6828 34436.5865 34479.4961 34577.6951 34648.1061 34713.3598 34801.3018 34829.9512 34861.5442 34885.3926 34889.9088 34896.8071 34905.4899 34981.2372