1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
3346
3347
3348
3349
3350
3351
3352
3353
3354
3355
3356
3357
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
3436
3437
3438
3439
3440
3441
3442
3443
3444
3445
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456
3457
3458
3459
3460
3461
3462
3463
3464
3465
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
3529
3530
3531
3532
3533
3534
3535
3536
3537
3538
3539
3540
3541
3542
3543
3544
3545
3546
3547
3548
3549
3550
3551
3552
3553
3554
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
4036
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
4096
4097
4098
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
4223
4224
4225
4226
4227
4228
4229
4230
4231
4232
4233
4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
4303
4304
4305
4306
4307
4308
4309
4310
4311
4312
4313
4314
4315
4316
4317
4318
4319
4320
4321
4322
4323
4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
4336
4337
4338
4339
4340
4341
4342
4343
4344
4345
4346
4347
4348
4349
4350
4351
4352
4353
4354
4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
4366
4367
4368
4369
4370
4371
4372
4373
4374
4375
4376
4377
4378
4379
4380
4381
4382
4383
4384
4385
4386
4387
4388
4389
4390
4391
4392
4393
4394
4395
4396
4397
4398
4399
4400
4401
4402
4403
4404
4405
4406
4407
4408
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440
4441
4442
4443
4444
4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
4458
4459
4460
4461
4462
4463
4464
4465
4466
4467
4468
4469
4470
4471
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538
4539
4540
4541
4542
4543
4544
4545
4546
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
4658
4659
4660
4661
4662
4663
4664
4665
4666
4667
4668
4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
4686
4687
4688
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
4738
4739
4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
4761
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
4796
4797
4798
4799
4800
4801
4802
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813
4814
4815
4816
4817
4818
4819
4820
4821
4822
4823
4824
4825
4826
4827
4828
4829
4830
4831
4832
4833
4834
4835
4836
4837
4838
4839
4840
4841
4842
4843
4844
4845
4846
4847
4848
4849
4850
4851
4852
4853
4854
4855
4856
4857
4858
4859
4860
4861
4862
4863
4864
4865
4866
4867
4868
4869
4870
4871
4872
4873
4874
4875
4876
4877
4878
4879
4880
4881
4882
4883
4884
4885
4886
4887
4888
4889
4890
4891
4892
4893
4894
4895
4896
4897
4898
4899
4900
4901
4902
4903
4904
4905
4906
4907
4908
4909
4910
4911
4912
4913
4914
4915
4916
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
4947
4948
4949
4950
4951
4952
4953
4954
4955
4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
4968
4969
4970
4971
4972
4973
4974
4975
4976
4977
4978
4979
4980
4981
4982
4983
4984
4985
4986
4987
4988
4989
4990
4991
4992
4993
4994
4995
4996
4997
4998
4999
5000
5001
5002
5003
5004
5005
5006
5007
5008
5009
5010
5011
5012
5013
5014
5015
5016
5017
5018
5019
5020
5021
5022
5023
5024
5025
5026
5027
5028
5029
5030
5031
5032
5033
5034
5035
5036
5037
5038
5039
5040
5041
5042
5043
5044
5045
5046
5047
5048
5049
5050
5051
5052
5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
5097
5098
5099
5100
5101
5102
5103
5104
5105
5106
5107
5108
5109
5110
5111
5112
5113
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
5135
5136
5137
5138
5139
5140
5141
5142
5143
5144
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154
5155
5156
5157
5158
5159
5160
5161
5162
5163
5164
5165
5166
5167
5168
5169
5170
5171
5172
5173
5174
5175
5176
5177
5178
5179
5180
5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
5202
5203
5204
5205
5206
5207
5208
5209
5210
5211
5212
5213
5214
5215
5216
5217
5218
5219
5220
5221
5222
5223
5224
5225
5226
5227
5228
5229
5230
5231
5232
5233
5234
5235
5236
5237
5238
5239
5240
5241
5242
5243
5244
5245
5246
5247
5248
5249
5250
5251
5252
5253
5254
5255
5256
5257
5258
5259
5260
5261
5262
5263
5264
5265
5266
5267
5268
5269
5270
5271
5272
5273
5274
5275
5276
5277
5278
5279
5280
5281
5282
5283
5284
5285
5286
5287
5288
5289
5290
5291
5292
5293
5294
5295
5296
5297
5298
5299
5300
5301
5302
5303
5304
5305
5306
5307
5308
5309
5310
5311
5312
5313
5314
5315
5316
5317
5318
5319
5320
5321
5322
5323
5324
5325
5326
5327
5328
5329
5330
5331
5332
5333
5334
5335
5336
5337
5338
5339
5340
5341
5342
5343
5344
5345
5346
5347
5348
5349
5350
5351
5352
5353
5354
5355
5356
5357
5358
5359
5360
5361
5362
5363
5364
5365
5366
5367
5368
5369
5370
5371
5372
5373
5374
5375
5376
5377
5378
5379
5380
5381
5382
5383
5384
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
5398
5399
5400
5401
5402
5403
5404
5405
5406
5407
5408
5409
5410
5411
5412
5413
5414
5415
5416
5417
5418
5419
5420
5421
5422
5423
5424
5425
5426
5427
5428
5429
5430
5431
5432
5433
5434
5435
5436
5437
5438
5439
5440
5441
5442
5443
5444
5445
5446
5447
5448
5449
5450
5451
5452
5453
5454
5455
5456
5457
5458
5459
5460
5461
5462
5463
5464
5465
5466
5467
5468
5469
5470
5471
5472
5473
5474
5475
5476
5477
5478
5479
5480
5481
5482
5483
5484
5485
5486
5487
5488
5489
5490
5491
5492
5493
5494
5495
5496
5497
5498
5499
5500
5501
5502
5503
5504
5505
5506
5507
5508
5509
5510
5511
5512
5513
5514
5515
5516
5517
5518
5519
5520
5521
5522
5523
5524
5525
5526
5527
5528
5529
5530
5531
5532
5533
5534
5535
5536
5537
5538
5539
5540
5541
5542
5543
5544
5545
5546
5547
5548
5549
5550
5551
5552
5553
5554
5555
5556
5557
5558
5559
5560
5561
5562
5563
5564
5565
5566
5567
5568
5569
5570
5571
5572
5573
5574
5575
5576
5577
5578
5579
5580
5581
5582
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
5607
5608
5609
5610
5611
5612
5613
5614
5615
5616
5617
5618
5619
5620
5621
5622
5623
5624
5625
5626
5627
5628
5629
5630
5631
5632
5633
5634
5635
5636
5637
5638
5639
5640
5641
5642
5643
5644
5645
5646
5647
5648
5649
5650
5651
5652
5653
5654
5655
5656
5657
5658
5659
5660
5661
5662
5663
5664
5665
5666
5667
5668
5669
5670
5671
5672
5673
5674
5675
5676
5677
5678
5679
5680
5681
5682
5683
5684
5685
5686
5687
5688
5689
5690
5691
5692
5693
5694
5695
5696
5697
5698
5699
5700
5701
5702
5703
5704
5705
5706
5707
5708
5709
5710
5711
5712
5713
5714
5715
5716
5717
5718
5719
5720
5721
5722
5723
5724
5725
5726
5727
5728
5729
5730
5731
5732
5733
5734
5735
5736
5737
5738
5739
5740
5741
5742
5743
5744
5745
5746
5747
5748
5749
5750
5751
5752
5753
5754
5755
5756
5757
5758
5759
5760
5761
5762
5763
5764
5765
5766
5767
5768
5769
5770
5771
5772
5773
5774
5775
5776
5777
5778
5779
5780
5781
5782
5783
5784
5785
5786
5787
5788
5789
5790
5791
5792
5793
5794
5795
5796
5797
5798
5799
5800
5801
5802
5803
5804
5805
5806
5807
5808
5809
5810
5811
5812
5813
5814
5815
5816
5817
5818
5819
5820
5821
5822
5823
5824
5825
5826
5827
5828
5829
5830
5831
5832
5833
5834
5835
5836
5837
5838
5839
5840
5841
5842
5843
5844
5845
5846
5847
5848
5849
5850
5851
5852
5853
5854
5855
5856
5857
5858
5859
5860
5861
5862
5863
5864
5865
5866
5867
5868
5869
5870
5871
5872
5873
5874
5875
5876
5877
5878
5879
5880
5881
5882
5883
5884
5885
5886
5887
5888
5889
5890
5891
5892
5893
5894
5895
5896
5897
5898
5899
5900
5901
5902
5903
5904
5905
5906
5907
5908
5909
5910
5911
5912
5913
5914
5915
5916
5917
5918
5919
5920
5921
5922
5923
5924
5925
5926
5927
5928
5929
5930
5931
5932
5933
5934
5935
5936
5937
5938
5939
5940
5941
5942
5943
5944
5945
5946
5947
5948
5949
5950
5951
5952
5953
5954
5955
5956
5957
5958
5959
5960
5961
5962
5963
5964
5965
5966
5967
5968
5969
5970
5971
5972
5973
5974
5975
5976
5977
5978
5979
5980
5981
5982
5983
5984
5985
5986
5987
5988
5989
5990
5991
5992
5993
5994
5995
5996
5997
5998
5999
6000
6001
6002
6003
6004
6005
6006
6007
6008
6009
6010
6011
6012
6013
6014
6015
6016
6017
6018
6019
6020
6021
6022
6023
6024
6025
6026
6027
6028
6029
6030
6031
6032
6033
6034
6035
6036
6037
6038
6039
6040
6041
6042
6043
6044
6045
6046
6047
6048
6049
6050
6051
6052
6053
6054
6055
6056
6057
6058
6059
6060
6061
6062
6063
6064
6065
6066
6067
6068
6069
6070
6071
6072
6073
6074
6075
6076
6077
6078
6079
6080
6081
6082
6083
6084
6085
6086
6087
6088
6089
6090
6091
6092
6093
6094
6095
6096
6097
6098
6099
6100
6101
6102
6103
6104
6105
6106
6107
6108
6109
6110
6111
6112
6113
6114
6115
6116
6117
6118
6119
6120
6121
6122
6123
6124
6125
6126
6127
6128
6129
6130
6131
6132
6133
6134
6135
6136
6137
6138
6139
6140
6141
6142
6143
6144
6145
6146
6147
6148
6149
6150
6151
6152
6153
6154
6155
6156
6157
6158
6159
6160
6161
6162
6163
6164
6165
6166
6167
6168
6169
6170
6171
6172
6173
6174
6175
6176
6177
6178
6179
6180
6181
6182
6183
6184
6185
6186
6187
6188
6189
6190
6191
6192
6193
6194
6195
6196
6197
6198
6199
6200
6201
6202
6203
6204
6205
6206
6207
6208
6209
6210
6211
6212
6213
6214
6215
6216
6217
6218
6219
6220
6221
6222
6223
6224
6225
6226
6227
6228
6229
6230
6231
6232
6233
6234
6235
6236
6237
6238
6239
6240
6241
6242
6243
6244
6245
6246
6247
6248
6249
6250
6251
6252
6253
6254
6255
6256
6257
6258
6259
6260
6261
6262
6263
6264
6265
6266
6267
6268
6269
6270
6271
6272
6273
6274
6275
6276
6277
6278
6279
6280
6281
6282
6283
6284
6285
6286
6287
6288
6289
6290
6291
6292
6293
6294
6295
6296
6297
6298
6299
6300
6301
6302
6303
6304
6305
6306
6307
6308
6309
6310
6311
6312
6313
6314
6315
6316
6317
6318
6319
6320
6321
6322
6323
6324
6325
6326
6327
6328
6329
6330
6331
6332
6333
6334
6335
6336
6337
6338
6339
6340
6341
6342
6343
6344
6345
6346
6347
6348
6349
6350
6351
6352
6353
6354
6355
6356
6357
6358
6359
6360
6361
6362
6363
6364
6365
6366
6367
6368
6369
6370
6371
6372
6373
6374
6375
6376
6377
6378
6379
6380
6381
6382
6383
6384
6385
6386
6387
6388
6389
6390
6391
6392
6393
6394
6395
6396
6397
6398
6399
6400
6401
6402
6403
6404
6405
6406
6407
6408
6409
6410
6411
6412
6413
6414
6415
6416
6417
6418
6419
6420
6421
6422
6423
6424
6425
6426
6427
6428
6429
6430
6431
6432
6433
6434
6435
6436
6437
6438
6439
6440
6441
6442
6443
6444
6445
6446
6447
6448
6449
6450
6451
6452
6453
6454
6455
6456
6457
6458
6459
6460
6461
6462
6463
6464
6465
6466
6467
6468
6469
6470
6471
6472
6473
6474
6475
6476
6477
6478
6479
6480
6481
6482
6483
6484
6485
6486
6487
6488
6489
6490
6491
6492
6493
6494
6495
6496
6497
6498
6499
6500
6501
6502
6503
6504
6505
6506
6507
6508
6509
6510
6511
6512
6513
6514
6515
6516
6517
6518
6519
6520
6521
6522
6523
6524
6525
6526
6527
6528
6529
6530
6531
6532
6533
6534
6535
6536
6537
6538
6539
6540
6541
6542
6543
6544
6545
6546
6547
6548
6549
6550
6551
6552
6553
6554
6555
6556
6557
6558
6559
6560
6561
6562
6563
6564
6565
6566
6567
6568
6569
6570
6571
6572
6573
6574
6575
6576
6577
6578
6579
6580
6581
6582
6583
6584
6585
6586
6587
6588
6589
6590
6591
6592
6593
6594
6595
6596
6597
6598
6599
6600
6601
6602
6603
6604
6605
6606
6607
6608
6609
6610
6611
6612
6613
6614
6615
6616
6617
6618
6619
6620
6621
6622
6623
6624
6625
6626
6627
6628
6629
6630
6631
6632
6633
6634
6635
6636
6637
6638
6639
6640
6641
6642
6643
6644
6645
6646
6647
6648
6649
6650
6651
6652
6653
6654
6655
6656
6657
6658
6659
6660
6661
6662
6663
6664
6665
6666
6667
6668
6669
6670
6671
6672
6673
6674
6675
6676
6677
6678
6679
6680
6681
6682
6683
6684
6685
6686
6687
6688
6689
6690
6691
6692
6693
6694
6695
6696
6697
6698
6699
6700
6701
6702
6703
6704
6705
6706
6707
6708
6709
6710
6711
6712
6713
6714
6715
6716
6717
6718
6719
6720
6721
6722
6723
6724
6725
6726
6727
6728
6729
6730
6731
6732
6733
6734
6735
6736
6737
6738
6739
6740
6741
6742
6743
6744
6745
6746
6747
6748
6749
6750
6751
6752
6753
6754
6755
6756
6757
6758
6759
6760
6761
6762
6763
6764
6765
6766
6767
6768
6769
6770
6771
6772
6773
6774
6775
6776
6777
6778
6779
6780
6781
6782
6783
6784
6785
6786
6787
6788
6789
6790
6791
6792
6793
6794
6795
6796
6797
6798
6799
6800
6801
6802
6803
6804
6805
6806
6807
6808
6809
6810
6811
6812
6813
6814
6815
6816
6817
6818
6819
6820
6821
6822
6823
6824
6825
6826
6827
6828
6829
6830
6831
6832
6833
6834
6835
6836
6837
6838
6839
6840
6841
6842
6843
6844
6845
6846
6847
6848
6849
6850
6851
6852
6853
6854
6855
6856
6857
6858
6859
6860
6861
6862
6863
6864
6865
6866
6867
6868
6869
6870
6871
6872
6873
6874
6875
6876
6877
6878
6879
6880
6881
6882
6883
6884
6885
6886
6887
6888
6889
6890
6891
6892
6893
6894
6895
6896
6897
6898
6899
6900
6901
6902
6903
6904
6905
6906
6907
6908
6909
6910
6911
6912
6913
6914
6915
6916
6917
6918
6919
6920
6921
6922
6923
6924
6925
6926
6927
6928
6929
6930
6931
6932
6933
6934
6935
6936
6937
6938
6939
6940
6941
6942
6943
6944
6945
6946
6947
6948
6949
6950
6951
6952
6953
6954
6955
6956
6957
6958
6959
6960
6961
6962
6963
6964
6965
6966
6967
6968
6969
6970
6971
6972
6973
6974
6975
6976
6977
6978
6979
6980
6981
6982
6983
6984
6985
6986
6987
6988
6989
6990
6991
6992
6993
6994
6995
6996
6997
6998
6999
7000
7001
7002
7003
7004
7005
7006
7007
7008
7009
7010
7011
7012
7013
7014
7015
7016
7017
7018
7019
7020
7021
7022
7023
7024
7025
7026
7027
7028
7029
7030
7031
7032
7033
7034
7035
7036
7037
7038
7039
7040
7041
7042
7043
7044
7045
7046
7047
7048
7049
7050
7051
7052
7053
7054
7055
7056
7057
7058
7059
7060
7061
7062
7063
7064
7065
7066
7067
7068
7069
7070
7071
7072
7073
7074
7075
7076
7077
7078
7079
7080
7081
7082
7083
7084
7085
7086
7087
7088
7089
7090
7091
7092
7093
7094
7095
7096
7097
7098
7099
7100
7101
7102
7103
7104
7105
7106
7107
7108
7109
7110
7111
7112
7113
7114
7115
7116
7117
7118
7119
7120
7121
7122
7123
7124
7125
7126
7127
7128
7129
7130
7131
7132
7133
7134
7135
7136
7137
7138
7139
7140
7141
7142
7143
7144
7145
7146
7147
7148
7149
7150
7151
7152
7153
7154
7155
7156
7157
7158
7159
7160
7161
7162
7163
7164
7165
7166
7167
7168
7169
7170
7171
7172
7173
7174
7175
7176
7177
7178
7179
7180
7181
7182
7183
7184
7185
7186
7187
7188
7189
7190
7191
7192
7193
7194
7195
7196
7197
7198
7199
7200
7201
7202
7203
7204
7205
7206
7207
7208
7209
7210
7211
7212
7213
7214
7215
7216
7217
7218
7219
7220
7221
7222
7223
7224
7225
7226
7227
7228
7229
7230
7231
7232
7233
7234
7235
7236
7237
7238
7239
7240
7241
7242
7243
7244
7245
7246
7247
7248
7249
7250
7251
7252
7253
7254
7255
7256
7257
7258
7259
7260
7261
7262
7263
7264
7265
7266
7267
7268
7269
7270
7271
7272
7273
7274
7275
7276
7277
7278
7279
7280
7281
7282
7283
7284
7285
7286
7287
7288
7289
7290
7291
7292
7293
7294
7295
7296
7297
7298
7299
7300
7301
7302
7303
7304
7305
7306
7307
7308
7309
7310
7311
7312
7313
7314
7315
7316
7317
7318
7319
7320
7321
7322
7323
7324
7325
7326
7327
7328
7329
7330
7331
7332
7333
7334
7335
7336
7337
7338
7339
7340
7341
7342
7343
7344
7345
7346
7347
7348
7349
7350
7351
7352
7353
7354
7355
7356
7357
7358
7359
7360
7361
7362
7363
7364
7365
7366
7367
7368
7369
7370
7371
7372
7373
7374
7375
7376
7377
7378
7379
7380
7381
7382
7383
7384
7385
7386
7387
7388
7389
7390
7391
7392
7393
7394
7395
7396
7397
7398
7399
7400
7401
7402
7403
7404
7405
7406
7407
7408
7409
7410
7411
7412
7413
7414
7415
7416
7417
7418
7419
7420
7421
7422
7423
7424
7425
7426
7427
7428
7429
7430
7431
7432
7433
7434
7435
7436
7437
7438
7439
7440
7441
7442
7443
7444
7445
7446
7447
7448
7449
7450
7451
7452
7453
7454
7455
7456
7457
7458
7459
7460
7461
7462
7463
7464
7465
7466
7467
7468
7469
7470
7471
7472
7473
7474
7475
7476
7477
7478
7479
7480
7481
7482
7483
7484
7485
7486
7487
7488
7489
7490
7491
7492
7493
7494
7495
7496
7497
7498
7499
7500
7501
7502
7503
7504
7505
7506
7507
7508
7509
7510
7511
7512
7513
7514
7515
7516
7517
7518
7519
7520
7521
7522
7523
7524
7525
7526
7527
7528
7529
7530
7531
7532
7533
7534
7535
7536
7537
7538
7539
7540
7541
7542
7543
7544
7545
7546
7547
7548
7549
7550
7551
7552
7553
7554
7555
7556
7557
7558
7559
7560
7561
7562
7563
7564
7565
7566
7567
7568
7569
7570
7571
7572
7573
7574
7575
7576
7577
7578
7579
7580
7581
7582
7583
7584
7585
7586
7587
7588
7589
7590
7591
7592
7593
7594
7595
7596
7597
7598
7599
7600
7601
7602
7603
7604
7605
7606
7607
7608
7609
7610
7611
7612
7613
7614
7615
7616
7617
7618
7619
7620
7621
7622
7623
7624
7625
7626
7627
7628
7629
7630
7631
7632
7633
7634
7635
7636
7637
7638
7639
7640
7641
7642
7643
7644
7645
7646
7647
7648
7649
7650
7651
7652
7653
7654
7655
7656
7657
7658
7659
7660
7661
7662
7663
7664
7665
7666
7667
7668
7669
7670
7671
7672
7673
7674
7675
7676
7677
7678
7679
7680
7681
7682
7683
7684
7685
7686
7687
7688
7689
7690
7691
7692
7693
7694
7695
7696
7697
7698
7699
7700
7701
7702
7703
7704
7705
7706
7707
7708
7709
7710
7711
7712
7713
7714
7715
7716
7717
7718
7719
7720
7721
7722
7723
7724
7725
7726
7727
7728
7729
7730
7731
7732
7733
7734
7735
7736
7737
7738
7739
7740
7741
7742
7743
7744
7745
7746
7747
7748
7749
7750
7751
7752
7753
7754
7755
7756
7757
7758
7759
7760
7761
7762
7763
7764
7765
7766
7767
7768
7769
7770
7771
7772
7773
7774
7775
7776
7777
7778
7779
7780
7781
7782
7783
7784
7785
7786
7787
7788
7789
7790
7791
7792
7793
7794
7795
7796
7797
7798
7799
7800
7801
7802
7803
7804
7805
7806
7807
7808
7809
7810
7811
7812
7813
7814
7815
7816
7817
7818
7819
7820
7821
7822
7823
7824
7825
7826
7827
7828
7829
7830
7831
7832
7833
7834
7835
7836
7837
7838
7839
7840
7841
7842
7843
7844
7845
7846
7847
7848
7849
7850
7851
7852
7853
7854
7855
7856
7857
7858
7859
7860
7861
7862
7863
7864
7865
7866
7867
7868
7869
7870
7871
7872
7873
7874
7875
7876
7877
7878
7879
7880
7881
7882
7883
7884
7885
7886
7887
7888
7889
7890
7891
7892
7893
7894
7895
7896
7897
7898
7899
7900
7901
7902
7903
7904
7905
7906
7907
7908
7909
7910
7911
7912
7913
7914
7915
7916
7917
7918
7919
7920
7921
7922
7923
7924
7925
7926
7927
7928
7929
7930
7931
7932
7933
7934
7935
7936
7937
7938
7939
7940
7941
7942
7943
7944
7945
7946
7947
7948
7949
7950
7951
7952
7953
7954
7955
7956
7957
7958
7959
7960
7961
7962
7963
7964
7965
7966
7967
7968
7969
7970
7971
7972
7973
7974
7975
7976
7977
7978
7979
7980
7981
7982
7983
7984
7985
7986
7987
7988
7989
7990
7991
7992
7993
7994
7995
7996
7997
7998
7999
8000
8001
8002
8003
8004
8005
8006
8007
8008
8009
8010
8011
8012
8013
8014
8015
8016
8017
8018
8019
8020
8021
8022
8023
8024
8025
8026
8027
8028
8029
8030
8031
8032
8033
8034
8035
8036
8037
8038
8039
8040
8041
8042
8043
8044
8045
8046
8047
8048
8049
8050
8051
8052
8053
8054
8055
8056
8057
8058
8059
8060
8061
8062
1
00:00:00,000 --> 00:00:11,100

2
00:00:11,100 --> 00:00:12,300
>> TALARE 1: Hej alla!

3
00:00:12,300 --> 00:00:13,890
Välkommen tillbaka till avsnitt.

4
00:00:13,890 --> 00:00:17,480
Så glad att se så många av er både här,
och alla som tittar på nätet.

5
00:00:17,480 --> 00:00:18,760

6
00:00:18,760 --> 00:00:20,920
Så, som vanligt välkommen tillbaka.

7
00:00:20,920 --> 00:00:24,360
Jag hoppas att ni alla haft en härlig
helg, full av vila, avkoppling.

8
00:00:24,360 --> 00:00:26,026
Det var vackert ute igår.

9
00:00:26,026 --> 00:00:27,525
Så, jag hoppas du haft utomhus.

10
00:00:27,525 --> 00:00:28,840

11
00:00:28,840 --> 00:00:30,610
>> Så först ett par meddelanden.

12
00:00:30,610 --> 00:00:31,920

13
00:00:31,920 --> 00:00:32,700
Betygs.

14
00:00:32,700 --> 00:00:37,350
Så, de flesta av er bör ha fått en
maila mig om din Scratch Pset,

15
00:00:37,350 --> 00:00:39,920
liksom omdöme för Pset 1.

16
00:00:39,920 --> 00:00:41,000

17
00:00:41,000 --> 00:00:42,220
Så, bara ett par saker.

18
00:00:42,220 --> 00:00:45,150
Var noga med att använda check50 i style50.

19
00:00:45,150 --> 00:00:47,250
Dessa är tänkta att vara
resurser för er killar,

20
00:00:47,250 --> 00:00:50,660
att se till att du får
så många poäng som du kan

21
00:00:50,660 --> 00:00:52,390
utan att i onödan förlora dem.

22
00:00:52,390 --> 00:00:54,407
Så saker som stil
är mycket viktiga.

23
00:00:54,407 --> 00:00:55,740
Vi kommer att ta bort det.

24
00:00:55,740 --> 00:00:58,115
Några av er kanske redan har
märkt att från din Pset.

25
00:00:58,115 --> 00:00:58,920

26
00:00:58,920 --> 00:01:01,450
Och check50 är bara en
riktigt enkelt sätt att se till

27
00:01:01,450 --> 00:01:05,050
att vi faktiskt är åter vad
måste returneras till användaren,

28
00:01:05,050 --> 00:01:06,690
och att allt fungerar korrekt.

29
00:01:06,690 --> 00:01:08,690

30
00:01:08,690 --> 00:01:12,040
>> På den andra anteckningen, se till att din
ladda upp saker till rätt mapp.

31
00:01:12,040 --> 00:01:14,470
Det gör mitt liv bara en
Lite svårare

32
00:01:14,470 --> 00:01:18,836
Om du laddar upp Pset 2 i Pset 1
för när jag hämta saker,

33
00:01:18,836 --> 00:01:20,085
de inte hämtas.

34
00:01:20,085 --> 00:01:21,690

35
00:01:21,690 --> 00:01:24,560
Och jag vet att det är lite wonky
i ett system för att vänja sig,

36
00:01:24,560 --> 00:01:26,950
men bara vara super
försiktig, om så bara för mig,

37
00:01:26,950 --> 00:01:30,080
så att när du får e-post
på liknande 02:00 och jag är betygssättning.

38
00:01:30,080 --> 00:01:33,710
Om inte orsaka jag måste titta
runt för din Pset.

39
00:01:33,710 --> 00:01:34,440
Cool.

40
00:01:34,440 --> 00:01:37,270
>> Jag vet att det är tidigt, men jag
helt fick tas på sängen

41
00:01:37,270 --> 00:01:40,800
av en uppsats som är på grund denna fredag, som
mina professorer var precis som, oh yeah.

42
00:01:40,800 --> 00:01:42,550
Kom ihåg, du har en
uppsats beror på fredagen.

43
00:01:42,550 --> 00:01:45,780
Så, jag vet ingen gillar
att tänka midterms,

44
00:01:45,780 --> 00:01:50,620
men din första frågesport är den 15 oktober,
vilket Oktober börjar denna vecka.

45
00:01:50,620 --> 00:01:53,290
Så kan det vara förr
än vad du förväntat är allt.

46
00:01:53,290 --> 00:01:57,510
Så att du inte kastat på sängen när
Jag nämner nästa veckas avsnitt som åh,

47
00:01:57,510 --> 00:02:00,560
din quiz nästa vecka, tänkte jag
Jag skulle ge dig lite mer

48
00:02:00,560 --> 00:02:01,500
av en huvuden upp nu.

49
00:02:01,500 --> 00:02:02,970

50
00:02:02,970 --> 00:02:04,660
>> Så ditt problem inställd, nummer tre.

51
00:02:04,660 --> 00:02:07,070
Hur människor har läst
spec av nyfikenhet?

52
00:02:07,070 --> 00:02:08,560

53
00:02:08,560 --> 00:02:09,199
OK.

54
00:02:09,199 --> 00:02:10,229
Vi fick ett par.

55
00:02:10,229 --> 00:02:12,320
Typ av minskning från förra
vecka men det är OK.

56
00:02:12,320 --> 00:02:13,650
Jag vet att det var vackert ute.

57
00:02:13,650 --> 00:02:15,120

58
00:02:15,120 --> 00:02:16,660
Så Break Out.

59
00:02:16,660 --> 00:02:21,010
Definitivt när du får gjort
idag läsa din spec minst

60
00:02:21,010 --> 00:02:25,240
Försök som laddar ner
distributions kod och kör

61
00:02:25,240 --> 00:02:27,430
liksom den första initiala
sak som de ber dig att.

62
00:02:27,430 --> 00:02:28,681

63
00:02:28,681 --> 00:02:32,590
Eftersom vi använder
distributions kod och ett bibliotek

64
00:02:32,590 --> 00:02:36,790
att vi bara har using-- --Det är bara
andra gången vi har gjort detta Pset,

65
00:02:36,790 --> 00:02:38,650
galna saker kan hända
med apparaten,

66
00:02:38,650 --> 00:02:41,370
och du vill finna att
ute nu kontra senare.

67
00:02:41,370 --> 00:02:45,570
>> För om det är torsdag kväll eller är det
Onsdag natt och av någon anledning

68
00:02:45,570 --> 00:02:48,912
apparaten bara inte
vill köra med biblioteket

69
00:02:48,912 --> 00:02:50,620
eller med fördelningen
kod, det betyder

70
00:02:50,620 --> 00:02:52,309
du kan inte ens börja göra kodningen.

71
00:02:52,309 --> 00:02:54,100
Eftersom du inte kan kontrollera
för att se om det fungerar.

72
00:02:54,100 --> 00:02:55,975
Din kommer inte att kunna
att se om det sammanställer.

73
00:02:55,975 --> 00:03:00,500
Du vill ta hand om dem som i början av
veckan, när man fortfarande kan maila mig

74
00:03:00,500 --> 00:03:03,100
eller någon av de andra TF,
och vi kan få dem fast.

75
00:03:03,100 --> 00:03:05,410
Eftersom dessa är frågor
som kommer att stoppa dig

76
00:03:05,410 --> 00:03:07,120
från att göra några verkliga framsteg.

77
00:03:07,120 --> 00:03:10,055
Det är inte som en bugg, som
du kan liksom bara hoppa över.

78
00:03:10,055 --> 00:03:10,712

79
00:03:10,712 --> 00:03:13,420
Om du har problem med din
apparaten eller distributionskoden,

80
00:03:13,420 --> 00:03:16,211
du verkligen vill att sett
hand om förr snarare än senare.

81
00:03:16,211 --> 00:03:20,410
Så även om du inte tänker faktiskt
börja koda, ladda ner distributionen

82
00:03:20,410 --> 00:03:24,040
kod, läs spec, se till att
allt fungerar där.

83
00:03:24,040 --> 00:03:25,134
OK?

84
00:03:25,134 --> 00:03:27,675
Om du bara kan göra det, jag
lovar ditt liv kommer att bli lättare.

85
00:03:27,675 --> 00:03:28,800

86
00:03:28,800 --> 00:03:31,410
Och så du förmodligen kommer
att göra det just nu rätt?

87
00:03:31,410 --> 00:03:32,100
OK.

88
00:03:32,100 --> 00:03:33,950
Så, några frågor där?

89
00:03:33,950 --> 00:03:35,850
Any logistiska saker?

90
00:03:35,850 --> 00:03:36,910
Alla är bra?

91
00:03:36,910 --> 00:03:38,270
OK.

92
00:03:38,270 --> 00:03:41,700
>> Disclaimer för de av
dig i rummet och på nätet.

93
00:03:41,700 --> 00:03:45,437
Jag kommer att försöka byta
mellan PowerPoint i apparaten

94
00:03:45,437 --> 00:03:47,270
eftersom vi kommer
att göra lite kodning

95
00:03:47,270 --> 00:03:53,630
idag på allmän begäran av anonyma
förslag enkät jag skickade ut förra veckan.

96
00:03:53,630 --> 00:03:55,480
Så kommer vi att göra lite kodning.

97
00:03:55,480 --> 00:03:57,800
Så, om ni också vill
att brand upp dina apparater,

98
00:03:57,800 --> 00:04:02,910
och du bör ha fått ett e-postmeddelande
från mig, med en exempelfil.

99
00:04:02,910 --> 00:04:04,310
Du får gärna göra det.

100
00:04:04,310 --> 00:04:07,340
>> Så vi kommer att prata om
GDB, vilket är en debugger.

101
00:04:07,340 --> 00:04:09,970
Det kommer att hjälpa dig
sorts räkna ut var

102
00:04:09,970 --> 00:04:11,860
det går fel i din kod.

103
00:04:11,860 --> 00:04:15,370
Det är egentligen bara ett sätt för dig att kliva
genom din kod eftersom det händer,

104
00:04:15,370 --> 00:04:19,100
och kunna skriva ut variabler
eller se vad som egentligen händer

105
00:04:19,100 --> 00:04:22,980
under huven verserna ditt program
bara kör, det är som faulting,

106
00:04:22,980 --> 00:04:25,030
och du är som, ingen aning
vad som just hände här.

107
00:04:25,030 --> 00:04:26,730
Jag vet inte vilken linje det misslyckades på.

108
00:04:26,730 --> 00:04:29,040
Jag vet inte var det gick fel.

109
00:04:29,040 --> 00:04:31,280
Så, GDB kommer att hjälpa dig med det.

110
00:04:31,280 --> 00:04:35,240
Dessutom, om du bestämmer dig för att
fortsätter ja, och ta 61,

111
00:04:35,240 --> 00:04:38,430
Det kommer verkligen, verkligen vara din
bästa vän, för jag kan berätta för dig

112
00:04:38,430 --> 00:04:40,840
eftersom jag går igenom den klassen.

113
00:04:40,840 --> 00:04:43,620
>> Vi kommer att titta på digital
sök, som om ni kommer ihåg

114
00:04:43,620 --> 00:04:47,540
den stora telefonboken exempel
skådespel från klass.

115
00:04:47,540 --> 00:04:50,620
Vi kommer att genomföra det, och
promenader genom att lite mer,

116
00:04:50,620 --> 00:04:54,650
och sedan ska vi gå igenom fyra
olika slag, som är Bubble,

117
00:04:54,650 --> 00:04:56,285
Urval, Insättning, och sammanfoga.

118
00:04:56,285 --> 00:04:57,830

119
00:04:57,830 --> 00:04:58,330
Cool.

120
00:04:58,330 --> 00:05:00,390
Så, GDB som jag nämnde, är en debugger.

121
00:05:00,390 --> 00:05:01,400

122
00:05:01,400 --> 00:05:09,370
Och dessa är typ av de stora
saker, de stora funktioner eller kommandon

123
00:05:09,370 --> 00:05:13,240
som du använder i GDB, och jag kommer att gå
dig genom en demo av den i en sekund.

124
00:05:13,240 --> 00:05:15,360
>> Så detta är inte bara
kommer att bo abstrakta.

125
00:05:15,360 --> 00:05:18,000
Jag ska försöka göra det så konkret
som möjligt för er.

126
00:05:18,000 --> 00:05:19,870
Så, bryta.

127
00:05:19,870 --> 00:05:22,200
Det ska antingen vara break
liknande, några nummer, vilket

128
00:05:22,200 --> 00:05:26,900
representerar en rad i programmet,
eller så kan du namnge en funktion.

129
00:05:26,900 --> 00:05:30,150
Så, om du säger break,
det kommer att stanna vid huvud,

130
00:05:30,150 --> 00:05:32,400
och låta dig gå igenom den funktionen.

131
00:05:32,400 --> 00:05:36,350
>> Likaså om du har någon extern
fungerar som Swap eller Cube,

132
00:05:36,350 --> 00:05:38,450
att vi tittade på i förra veckan.

133
00:05:38,450 --> 00:05:41,780
Om du säger att bryta en av dem,
när ditt program slår det,

134
00:05:41,780 --> 00:05:44,290
Det väntar på dig att
tala om vad de ska göra.

135
00:05:44,290 --> 00:05:47,860
Innan det kommer bara köra så att du
kunde faktiskt steg inuti funktionen

136
00:05:47,860 --> 00:05:49,020
och se vad som händer.

137
00:05:49,020 --> 00:05:50,370

138
00:05:50,370 --> 00:05:53,515
Så hoppar Nästa strax över
nästa rad, går över funktioner.

139
00:05:53,515 --> 00:05:54,730

140
00:05:54,730 --> 00:05:55,560
Step.

141
00:05:55,560 --> 00:05:56,810
Dessa är alla lite abstrakt.

142
00:05:56,810 --> 00:06:00,530
Så, jag ska bara köra igenom dem,
men du kommer att se dem i bruk i en sekund.

143
00:06:00,530 --> 00:06:01,810
>> Kliv in i en funktion.

144
00:06:01,810 --> 00:06:04,170
Så när jag sa,
som med Swap, skulle det

145
00:06:04,170 --> 00:06:07,110
kan du faktiskt som om du är
som fysiskt kliva inne,

146
00:06:07,110 --> 00:06:10,990
du kan bråka med dessa variabler, print
reda på vad de är, se vad som händer.

147
00:06:10,990 --> 00:06:12,140

148
00:06:12,140 --> 00:06:14,830
Lista kommer bokstavligen bara ut
ut det omgivande kod.

149
00:06:14,830 --> 00:06:17,570
Så, om du slags glömmer
var du är i ditt program,

150
00:06:17,570 --> 00:06:19,880
eller du undrar
vad som händer runt omkring,

151
00:06:19,880 --> 00:06:23,790
Detta kommer bara skriva ut ett segment
av vilja fem eller sex rader runt den.

152
00:06:23,790 --> 00:06:26,080
Så kan du få orienterad
om var du befinner dig.

153
00:06:26,080 --> 00:06:27,230

154
00:06:27,230 --> 00:06:28,650
>> Skriv några variabel.

155
00:06:28,650 --> 00:06:34,590
Så, om du har nyckeln som
i Caesar, som vi ska titta på.

156
00:06:34,590 --> 00:06:36,220
Du kan säga Print Key på någon punkt.

157
00:06:36,220 --> 00:06:40,070
Den ska berätta vad värdet är så
att, kanske någonstans på vägen,

158
00:06:40,070 --> 00:06:42,070
Du har skrivit över din nyckel.

159
00:06:42,070 --> 00:06:45,495
Du kan faktiskt säga att eftersom
Du kan faktiskt konstatera att värdet.

160
00:06:45,495 --> 00:06:46,500

161
00:06:46,500 --> 00:06:48,780
>> I lokalbefolkningen, bara utskrifter
ut dina lokala variabler.

162
00:06:48,780 --> 00:06:53,120
Så, när du är i en slinga,
och du bara vill se ut som, oh.

163
00:06:53,120 --> 00:06:54,270
Vad är mitt jag?

164
00:06:54,270 --> 00:06:57,020
Vad är detta nyckelvärde
att jag initiera här?

165
00:06:57,020 --> 00:06:58,537
Vad är budskapet i detta läge?

166
00:06:58,537 --> 00:07:00,370
Det kommer bara att skriva ut alla
av dem, så att du

167
00:07:00,370 --> 00:07:04,330
behöver inte individuellt
säga, Print I. ut meddelande.

168
00:07:04,330 --> 00:07:04,970
Skriv Key.

169
00:07:04,970 --> 00:07:06,190

170
00:07:06,190 --> 00:07:07,700
Och sedan Display.

171
00:07:07,700 --> 00:07:10,370
Vad det gör är som ni
stega igenom programmet,

172
00:07:10,370 --> 00:07:13,980
det ska bara se till att det är
visar några viss variabel

173
00:07:13,980 --> 00:07:14,780
vid varje punkt.

174
00:07:14,780 --> 00:07:17,160
Så att du also-- --den är
typ av en genväg där

175
00:07:17,160 --> 00:07:19,530
du behöver inte hålla på som, oh.

176
00:07:19,530 --> 00:07:23,150
Skriv Key eller Skriv I. Det bara
kommer automatiskt att göra det åt dig.

177
00:07:23,150 --> 00:07:25,959
>> Så med det, vi kommer
för att se hur det går.

178
00:07:25,959 --> 00:07:28,000
Jag ska försöka och switch
över till min apparat.

179
00:07:28,000 --> 00:07:30,200

180
00:07:30,200 --> 00:07:31,271
Se om jag kan göra det här.

181
00:07:31,271 --> 00:07:31,770
Alla.

182
00:07:31,770 --> 00:07:40,970

183
00:07:40,970 --> 00:07:42,370
Vi kommer bara att spegla den.

184
00:07:42,370 --> 00:07:44,530
Det finns inget galet
på min laptop ändå.

185
00:07:44,530 --> 00:07:49,600

186
00:07:49,600 --> 00:07:50,100
OK.

187
00:07:50,100 --> 00:07:57,030

188
00:07:57,030 --> 00:08:01,054
Detta måste vara den här.

189
00:08:01,054 --> 00:08:01,795
Den är så liten.

190
00:08:01,795 --> 00:08:03,730

191
00:08:03,730 --> 00:08:05,120
Låt oss se om vi kan göra det här.

192
00:08:05,120 --> 00:08:09,970

193
00:08:09,970 --> 00:08:10,940
>> OK.

194
00:08:10,940 --> 00:08:15,305
Alice är uppenbarligen kämpar
här bara en liten bit,

195
00:08:15,305 --> 00:08:17,995
men vi kommer att få det i en momento.

196
00:08:17,995 --> 00:08:20,810

197
00:08:20,810 --> 00:08:22,020
OK.

198
00:08:22,020 --> 00:08:25,900
Vi kommer bara att öka denna.

199
00:08:25,900 --> 00:08:28,770

200
00:08:28,770 --> 00:08:29,380
OK.

201
00:08:29,380 --> 00:08:31,679
Kan alla sorts ser det?

202
00:08:31,679 --> 00:08:32,470
Kanske lite?

203
00:08:32,470 --> 00:08:33,594
Jag vet att det är lite små.

204
00:08:33,594 --> 00:08:34,570

205
00:08:34,570 --> 00:08:37,530
Du kan inte riktigt räkna ut
hur man gör det här större.

206
00:08:37,530 --> 00:08:38,350
Om någon vet.

207
00:08:38,350 --> 00:08:40,309
Finns det någon som vet hur man gör det större?

208
00:08:40,309 --> 00:08:40,932
OK.

209
00:08:40,932 --> 00:08:42,140
Vi kommer att rulla med det.

210
00:08:42,140 --> 00:08:45,801
Spelar ingen roll ändå eftersom det är bara
det är den kod som ni bör

211
00:08:45,801 --> 00:08:46,300
har.

212
00:08:46,300 --> 00:08:48,310
>> Vad är viktigare
är terminalen här.

213
00:08:48,310 --> 00:08:52,840

214
00:08:52,840 --> 00:08:58,690
Och vi har här Varför är det så liten?

215
00:08:58,690 --> 00:09:02,325

216
00:09:02,325 --> 00:09:02,825
Inställningar.

217
00:09:02,825 --> 00:09:07,920

218
00:09:07,920 --> 00:09:08,420
Oh.

219
00:09:08,420 --> 00:09:09,500
Sann Ike.

220
00:09:09,500 --> 00:09:10,880
Hur är det?

221
00:09:10,880 --> 00:09:11,770
Av det.

222
00:09:11,770 --> 00:09:19,370

223
00:09:19,370 --> 00:09:21,810
Är det bättre för alla?

224
00:09:21,810 --> 00:09:22,525
OK ,.

225
00:09:22,525 --> 00:09:23,025
Cool.

226
00:09:23,025 --> 00:09:25,830

227
00:09:25,830 --> 00:09:28,220
>> Du vet när du är i en CS
klass tekniska svårigheter

228
00:09:28,220 --> 00:09:32,971
är typ av en del av the--
Så, låt oss klara detta.

229
00:09:32,971 --> 00:09:33,470
OK.

230
00:09:33,470 --> 00:09:38,060
Så här i avsnittet,
som vi hade här.

231
00:09:38,060 --> 00:09:40,830
Caesar är en körbar fil.

232
00:09:40,830 --> 00:09:41,800
Så jag gjorde det.

233
00:09:41,800 --> 00:09:46,370
Så, är en sak att inse med GDB
att det fungerar bara på körbara filer.

234
00:09:46,370 --> 00:09:48,040
Så kan du inte köra det på en dotsy.

235
00:09:48,040 --> 00:09:50,532
Du måste faktiskt göra
Se till att din kod sammanställer,

236
00:09:50,532 --> 00:09:51,865
och att det faktiskt kan köras.

237
00:09:51,865 --> 00:09:52,970

238
00:09:52,970 --> 00:09:56,186
>> Så, se till att om det inte gör det
sammanställa, få den att kompilera,

239
00:09:56,186 --> 00:09:57,810
så att du kan slags kör igenom den.

240
00:09:57,810 --> 00:10:04,590
Så, för att starta GDB, allt du gör,
Gloria typ GDB, och sedan bara den

241
00:10:04,590 --> 00:10:06,250
fil som du vill.

242
00:10:06,250 --> 00:10:08,240
Jag stavar alltid Caesar.

243
00:10:08,240 --> 00:10:11,730
Men du vill vara säker på
eftersom det är en körbar,

244
00:10:11,730 --> 00:10:14,210
ti s dot blixt så att
innebär att du kommer

245
00:10:14,210 --> 00:10:19,240
att köra CSI du kommer att köra
Detta filer antingen med debugger.

246
00:10:19,240 --> 00:10:19,910
OK.

247
00:10:19,910 --> 00:10:22,885
Så, du gör det, får du
denna typ av rotvälska.

248
00:10:22,885 --> 00:10:24,250

249
00:10:24,250 --> 00:10:25,750
Det är bara allt om debugger.

250
00:10:25,750 --> 00:10:28,200
Du behöver verkligen inte till
oroa sig för det just nu.

251
00:10:28,200 --> 00:10:31,460
Och som ni ser har vi denna
öppna parens, BNP, nära parens,

252
00:10:31,460 --> 00:10:34,690
och bara typ av ser ut
vår kommandorad, eller hur?

253
00:10:34,690 --> 00:10:37,010
>> Så, vad vi vill do--
--So, Det första

254
00:10:37,010 --> 00:10:39,570
är att vi vill välja
en plats för att bryta den.

255
00:10:39,570 --> 00:10:42,332
Så det finns ett programfel
i detta Caesar programmet

256
00:10:42,332 --> 00:10:44,290
att jag presentera, att
vi kommer att ta reda på.

257
00:10:44,290 --> 00:10:45,330

258
00:10:45,330 --> 00:10:56,350
Det Vad det är det tar ingången
Barfoo med stora bokstäver, och av någon anledning

259
00:10:56,350 --> 00:11:01,950
Det ändrar inte A. Det lämnar bara
det ensam, är allt annat rätt,

260
00:11:01,950 --> 00:11:03,980
men den andra bokstaven
A är oförändrad.

261
00:11:03,980 --> 00:11:07,120
Så vi ska försöka
räkna ut varför det är.

262
00:11:07,120 --> 00:11:10,440
Så, det första du normalt
vill göra när du börjar på GDB

263
00:11:10,440 --> 00:11:12,010
är räkna ut var att bryta den.

264
00:11:12,010 --> 00:11:14,956
>> Så Caesar är en ganska kort program.

265
00:11:14,956 --> 00:11:16,330
Vi har bara en funktion, eller hur?

266
00:11:16,330 --> 00:11:18,520
Vad var vår funktion i Caesar?

267
00:11:18,520 --> 00:11:19,590

268
00:11:19,590 --> 00:11:24,350
Det finns bara en funktion, Main rätt?

269
00:11:24,350 --> 00:11:26,490
Main är en funktion
för alla dina program.

270
00:11:26,490 --> 00:11:29,230
Om du inte har Main, kanske jag
vara lite orolig just nu,

271
00:11:29,230 --> 00:11:31,000
men jag hoppas att ni alla hade huvud där.

272
00:11:31,000 --> 00:11:34,150
Så, vad vi kan göra är att vi kan
bara bryta Main, bara så där.

273
00:11:34,150 --> 00:11:35,190
Så står det, OK.

274
00:11:35,190 --> 00:11:37,430
Vi sätter vår brytpunkt där.

275
00:11:37,430 --> 00:11:42,870
>> Så, nu är det sak att komma ihåg Caesar
tar en Kommandoradsargumentet rätt

276
00:11:42,870 --> 00:11:45,150
och vi har inte gjort det någonstans än.

277
00:11:45,150 --> 00:11:47,560
Så, vad du gör är när
du faktiskt går att köra

278
00:11:47,560 --> 00:11:51,540
programmet, alla program som du är
körs i GDB som behöver kommandoraden

279
00:11:51,540 --> 00:11:55,010
argument, du kommer att mata
när du börjar köra den.

280
00:11:55,010 --> 00:11:59,280
Så i det här fallet, vi gör
Kör med en nyckel av tre.

281
00:11:59,280 --> 00:12:00,770

282
00:12:00,770 --> 00:12:02,040
Och det kommer faktiskt börja.

283
00:12:02,040 --> 00:12:08,480
>> Så, om ni ser här, vi har
Om RC inte är lika med två.

284
00:12:08,480 --> 00:12:12,210
Så om ni har alla
den fil som jag skickade ut upp

285
00:12:12,210 --> 00:12:15,100
ser du att det är som
första raden våran funktion, eller hur?

286
00:12:15,100 --> 00:12:17,890
Det är kontroll för att se om vi har
rätt antal argument.

287
00:12:17,890 --> 00:12:20,620
Så, om du undrar
om RC är korrekt,

288
00:12:20,620 --> 00:12:23,250
du kan göra något precis som Print RC.

289
00:12:23,250 --> 00:12:24,380

290
00:12:24,380 --> 00:12:28,640
RC är två, vilket är
vad vi förväntat oss, eller hur?

291
00:12:28,640 --> 00:12:32,010
>> Så kan vi gå på Nästa,
och fortsätter genom.

292
00:12:32,010 --> 00:12:33,200
Så, har vi några viktiga där.

293
00:12:33,200 --> 00:12:34,260

294
00:12:34,260 --> 00:12:37,090
Och vi kan skriva ut vår nyckel
att se till att det är korrekt.

295
00:12:37,090 --> 00:12:38,380

296
00:12:38,380 --> 00:12:39,500
Intressant.

297
00:12:39,500 --> 00:12:41,210
Inte riktigt vad vi förväntat oss.

298
00:12:41,210 --> 00:12:44,810
Så, för en sak att inse
med GDB också är

299
00:12:44,810 --> 00:12:49,000
att det inte är förrän du faktiskt hit
Därefter att den linje som du just såg

300
00:12:49,000 --> 00:12:50,720
faktiskt exekveras.

301
00:12:50,720 --> 00:12:53,870
Så i det här fallet Key
har inte tilldelats ännu.

302
00:12:53,870 --> 00:12:57,050
Så, är nyckeln vissa skräp värde
som du ser på botten där.

303
00:12:57,050 --> 00:13:03,680
Negativ $ 120-- --Det är en miljard
och något udda saker rätt?

304
00:13:03,680 --> 00:13:05,340
Det är inte nyckeln som vi förväntade oss.

305
00:13:05,340 --> 00:13:10,720
Men om vi träffade på Nästa och sedan vi
försök och tryckknapp, det är tre.

306
00:13:10,720 --> 00:13:11,710
>> Alla se det?

307
00:13:11,710 --> 00:13:13,780
Så, om du får något
att du är som, vänta.

308
00:13:13,780 --> 00:13:15,540
Detta är helt
fel, och jag vet inte

309
00:13:15,540 --> 00:13:20,150
Hur detta skulle hända eftersom allt jag vill ha
göra är att tilldela ett nummer, en variabel,

310
00:13:20,150 --> 00:13:22,900
försöka slå Därefter försöker skriva ut
det igen, och se om det fungerar.

311
00:13:22,900 --> 00:13:27,830
Eftersom det är bara att köra och
faktiskt tilldela något efter dig

312
00:13:27,830 --> 00:13:29,340
hit Nästa.

313
00:13:29,340 --> 00:13:30,336
Vettigt att alla?

314
00:13:30,336 --> 00:13:30,836
Uh huh?

315
00:13:30,836 --> 00:13:33,220
>> TALARE 2: När du random
siffror vad betyder det?

316
00:13:33,220 --> 00:13:34,790
>> TALARE 1: Det är bara slumpmässigt.

317
00:13:34,790 --> 00:13:35,710
Det är bara skräp.

318
00:13:35,710 --> 00:13:38,320
Det är bara något som din
Datorn kommer att slumpmässigt tilldela.

319
00:13:38,320 --> 00:13:39,721

320
00:13:39,721 --> 00:13:40,220
Cool.

321
00:13:40,220 --> 00:13:45,760
Så, nu kan vi gå igenom, och så
Nu har vi denna klartext getString.

322
00:13:45,760 --> 00:13:48,600
Så, låt mig bara presentera vad
kommer att hända när vi träffar Next här.

323
00:13:48,600 --> 00:13:51,320
Vår GDB slags försvinner, eller hur?

324
00:13:51,320 --> 00:13:55,720
Det beror getString
Nu utför, eller hur?

325
00:13:55,720 --> 00:14:01,460
Så när vi såg klartext lika
GetString, öppna parens och parens,

326
00:14:01,460 --> 00:14:04,380
och vi drabbades Därefter har det
faktiskt utförs nu.

327
00:14:04,380 --> 00:14:06,580
Så är det att vänta på
oss att mata in något.

328
00:14:06,580 --> 00:14:13,560
>> Så vi kommer att mata våra livsmedel som
är vad det inte som jag sa

329
00:14:13,560 --> 00:14:18,020
och som bara säger att det är
körts, att den slutna

330
00:14:18,020 --> 00:14:19,980
Fästet gör att det är
att komma ut i nämnda slinga.

331
00:14:19,980 --> 00:14:21,170

332
00:14:21,170 --> 00:14:25,420
Så kan vi träffa på Nästa, och nu, när jag är
att du är alla bekanta från Caesar,

333
00:14:25,420 --> 00:14:27,260
Detta är, vad är denna linje kommer att göra.

334
00:14:27,260 --> 00:14:32,030
Det är för Int I är lika med 0, lika med N
Strlen, vanlig text, och sedan

335
00:14:32,030 --> 00:14:33,960
Jag är mindre än n, jag, plus, plus.

336
00:14:33,960 --> 00:14:35,210
Vad är denna slinga ska göra?

337
00:14:35,210 --> 00:14:37,900

338
00:14:37,900 --> 00:14:39,160
Öppna ditt meddelande.

339
00:14:39,160 --> 00:14:39,770
Cool.

340
00:14:39,770 --> 00:14:41,330
Så, låt oss börja göra det.

341
00:14:41,330 --> 00:14:47,210
>> Så, bör detta tillstånd
matcha, för vår första?

342
00:14:47,210 --> 00:14:52,250
Om det är ett B, det är ren text I. Vi
kan få information om våra lokalbefolkningen.

343
00:14:52,250 --> 00:14:53,610

344
00:14:53,610 --> 00:14:57,970
Så, är jag noll, och om sex, vilket
Vi förväntar oss, och vår nyckel är tre.

345
00:14:57,970 --> 00:14:59,227
Allt som vettigt, eller hur?

346
00:14:59,227 --> 00:15:01,310
Dessa siffror är alla
exakt vad de borde vara.

347
00:15:01,310 --> 00:15:02,590

348
00:15:02,590 --> 00:15:03,870
Så, hum?

349
00:15:03,870 --> 00:15:05,620
TALARE 3: Jag har
slumptal för gruvan.

350
00:15:05,620 --> 00:15:09,156

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: Tja, kan vi check-- --Vi
kan prata om det på en sekund.

352
00:15:12,030 --> 00:15:14,110

353
00:15:14,110 --> 00:15:15,750
Men du bör vara att få detta.

354
00:15:15,750 --> 00:15:17,700

355
00:15:17,700 --> 00:15:20,130
Så, om vi har ett kapital
B för vår första,

356
00:15:20,130 --> 00:15:22,080
detta villkor ska fånga den, eller hur?

357
00:15:22,080 --> 00:15:27,120
Så om vi slog Därefter ser vi
att denna Om faktiskt utför.

358
00:15:27,120 --> 00:15:29,220
För om du följer
tillsammans i din kod,

359
00:15:29,220 --> 00:15:33,460
denna linje här, där klartext I
skall ersättas med denna aritmetik,

360
00:15:33,460 --> 00:15:35,720
endast körs om Om
tillståndet är korrekt rätt?

361
00:15:35,720 --> 00:15:36,905

362
00:15:36,905 --> 00:15:40,240
>> GDB kommer bara att visa dig
saker som faktiskt utför.

363
00:15:40,240 --> 00:15:45,140
Så om detta Om villkoret inte uppfylldes, det
bara att hoppa till nästa rad.

364
00:15:45,140 --> 00:15:46,540
OK?

365
00:15:46,540 --> 00:15:48,510
Så har vi det.

366
00:15:48,510 --> 00:15:51,171
Detta fäste betyder att det är
stängd ur denna loop nu.

367
00:15:51,171 --> 00:15:52,420
Så det kommer att börja igen.

368
00:15:52,420 --> 00:15:54,760

369
00:15:54,760 --> 00:15:56,280
Bara så där.

370
00:15:56,280 --> 00:15:59,120
Så att vi kan få info
om våra lokalbefolkningen här,

371
00:15:59,120 --> 00:16:02,575
och vi ser att vår första
brev har förändrats, eller hur?

372
00:16:02,575 --> 00:16:05,150
Det är nu ett E, som det ska vara.

373
00:16:05,150 --> 00:16:07,360
Så kan vi fortsätta på.

374
00:16:07,360 --> 00:16:08,500
>> Och vi har denna kontroll.

375
00:16:08,500 --> 00:16:09,916
Och denna kontroll bör fungera, eller hur?

376
00:16:09,916 --> 00:16:12,570
Det är A. Det bör ändras
tre bokstäver framåt.

377
00:16:12,570 --> 00:16:14,320

378
00:16:14,320 --> 00:16:16,530
Men om du märker, vi
få något annat.

379
00:16:16,530 --> 00:16:17,580

380
00:16:17,580 --> 00:16:22,860
Så i detta fall här uppe, fångade den
det, och så denna linje avrättades,

381
00:16:22,860 --> 00:16:28,620
som modifierats vår B.
Men, i detta fallet här,

382
00:16:28,620 --> 00:16:32,860
Vi har att det bara hoppade över det,
och gick till [? L SIFF. ?]

383
00:16:32,860 --> 00:16:34,660
Så något händer där.

384
00:16:34,660 --> 00:16:37,780
Vad som är att berätta är att,
Vi vet att den ska hinna hit,

385
00:16:37,780 --> 00:16:39,200
men det är det inte.

386
00:16:39,200 --> 00:16:42,210
Kan någon se vad vår
Problemet ligger i den linjen?

387
00:16:42,210 --> 00:16:45,380

388
00:16:45,380 --> 00:16:46,969
Det är en mycket liten sak.

389
00:16:46,969 --> 00:16:48,510
Och du kan även titta på din kod.

390
00:16:48,510 --> 00:16:49,980

391
00:16:49,980 --> 00:16:54,940
Det är också line-- glömma vad linjen är det
i there-- men det är i [OHÖRBAR].

392
00:16:54,940 --> 00:16:55,480
Ja?

393
00:16:55,480 --> 00:16:58,639
>> TALARE 4: Det är på mer än
sida om du läser det i boken.

394
00:16:58,639 --> 00:16:59,430
TALARE 1: Exakt.

395
00:16:59,430 --> 00:17:02,620
Så, debugger kunde inte berätta
du det, men det debugger

396
00:17:02,620 --> 00:17:05,880
kan få dig ner till en linje
som du vet fungerar inte.

397
00:17:05,880 --> 00:17:09,319
Och ibland, när speciellt
senare på terminen, när

398
00:17:09,319 --> 00:17:12,910
du arbetar med ett hundratal, en
hundra några rader kod, och du

399
00:17:12,910 --> 00:17:16,190
vet inte var det är inte,
Detta är ett bra sätt att göra det.

400
00:17:16,190 --> 00:17:17,900

401
00:17:17,900 --> 00:17:18,989
Så hittade vi vår bugg.

402
00:17:18,989 --> 00:17:21,530
Du kan fixa det i filen,
och då kan du köra den igen,

403
00:17:21,530 --> 00:17:23,029
och allt skulle fungera perfekt.

404
00:17:23,029 --> 00:17:24,970

405
00:17:24,970 --> 00:17:30,590
Och det största är
Detta kan tyckas, OK.

406
00:17:30,590 --> 00:17:31,090
Yeah.

407
00:17:31,090 --> 00:17:31,370
Cool.

408
00:17:31,370 --> 00:17:32,744
Du visste vad du letar efter.

409
00:17:32,744 --> 00:17:34,910
Så, du visste vad du ska göra.

410
00:17:34,910 --> 00:17:39,021
>> GDB kan vara super bra eftersom du
kan skriva ut alla dessa saker som du

411
00:17:39,021 --> 00:17:39,520
skulle inte.

412
00:17:39,520 --> 00:17:41,160
Det är mycket mer användbar än printf.

413
00:17:41,160 --> 00:17:43,440
Hur många av er använder
liknande printf Information

414
00:17:43,440 --> 00:17:46,200
att räkna ut var en bugg var, eller hur?

415
00:17:46,200 --> 00:17:48,450
Så med detta, behöver du inte
måste hålla gå tillbaka,

416
00:17:48,450 --> 00:17:51,139
och gillar kommentera i
Printf eller kommentera bort,

417
00:17:51,139 --> 00:17:52,930
och räkna ut vad
du ska skriva ut.

418
00:17:52,930 --> 00:17:55,670
Detta egentligen bara ger dig möjlighet att
gå igenom, skriva ut saker

419
00:17:55,670 --> 00:18:00,000
när du går igenom, så kan du
observera hur de förändras i realtid,

420
00:18:00,000 --> 00:18:02,190
som ditt program körs.

421
00:18:02,190 --> 00:18:04,390
>> Och det tar lite
lite tid att vänja sig.

422
00:18:04,390 --> 00:18:07,850
Jag rekommenderar starkt bara typ
av att vara lite frustrerad med det

423
00:18:07,850 --> 00:18:08,930
för just nu.

424
00:18:08,930 --> 00:18:13,450
Om du tillbringar en timme över
nästa vecka att lära sig använda GDB,

425
00:18:13,450 --> 00:18:16,140
du kommer att rädda dig själv
så mycket tid längre fram.

426
00:18:16,140 --> 00:18:18,750
Och bokstavligt. Vi berättar
detta till människor varje år,

427
00:18:18,750 --> 00:18:23,890
och jag minns när jag tog
klass, var jag vill, jag kommer att bli bra.

428
00:18:23,890 --> 00:18:24,700
Nej.

429
00:18:24,700 --> 00:18:27,030
Pset 6 kom och jag var
liksom, jag ska lära

430
00:18:27,030 --> 00:18:29,500
hur man använder GDB eftersom jag inte
veta vad som händer här.

431
00:18:29,500 --> 00:18:32,940
>> Så om du tar dig tid så
använda den på mindre program

432
00:18:32,940 --> 00:18:35,697
att du kommer att vara
arbetar med, som att jobba

433
00:18:35,697 --> 00:18:37,530
igenom något liknande
Visionäre, som den här.

434
00:18:37,530 --> 00:18:38,800

435
00:18:38,800 --> 00:18:42,850
Eller om du vill ha extra praxis, jag är säker på
Jag kunde komma på buggiga program,

436
00:18:42,850 --> 00:18:45,300
för dig att felsöka om du vill.

437
00:18:45,300 --> 00:18:49,300
>> Men om du bara tar lite tid att komma
van vid det, bara leka med den,

438
00:18:49,300 --> 00:18:50,550
Det kommer verkligen att tjäna dig väl.

439
00:18:50,550 --> 00:18:52,591
Och det är verkligen en av
de saker som du bara

440
00:18:52,591 --> 00:18:57,340
måste försöka, och få händerna smutsiga
med, innan man verkligen förstår det.

441
00:18:57,340 --> 00:19:02,090
Jag verkligen bara förstod det en gång
Jag var tvungen att felsöka saker med den,

442
00:19:02,090 --> 00:19:08,170
och det är mycket trevligare att ha en uppfattning om
hur man felsöka förr snarare än senare.

443
00:19:08,170 --> 00:19:08,850
OK.

444
00:19:08,850 --> 00:19:09,625
Cool.

445
00:19:09,625 --> 00:19:12,960
Jag vet att det är ungefär som
en snabbkurs i GDB,

446
00:19:12,960 --> 00:19:16,400
och jag kommer definitivt att arbeta på att få
dessa för att se större nästa gång.

447
00:19:16,400 --> 00:19:17,590

448
00:19:17,590 --> 00:19:18,280
Cool.

449
00:19:18,280 --> 00:19:20,390
>> Så om vi går tillbaka till vår PowerPoint.

450
00:19:20,390 --> 00:19:27,194

451
00:19:27,194 --> 00:19:28,110
Kommer detta att fungera?

452
00:19:28,110 --> 00:19:29,711

453
00:19:29,711 --> 00:19:30,210
AWH.

454
00:19:30,210 --> 00:19:31,101
Ja.

455
00:19:31,101 --> 00:19:31,600
OK.

456
00:19:31,600 --> 00:19:35,480
Så, om du någonsin behöver någon av
dem igen, det finns i listan.

457
00:19:35,480 --> 00:19:37,160

458
00:19:37,160 --> 00:19:40,830
Så Binary Search, som alla
minns den stora skådespel av David

459
00:19:40,830 --> 00:19:42,259
rippning telefonböcker i hälften.

460
00:19:42,259 --> 00:19:44,050
Jag vet inte riktigt får
telefonböcker längre,

461
00:19:44,050 --> 00:19:46,530
eftersom som var gör du
få telefonböcker nuförtiden?

462
00:19:46,530 --> 00:19:48,220
Jag vet faktiskt inte.

463
00:19:48,220 --> 00:19:49,840

464
00:19:49,840 --> 00:19:50,590
Binary Search.

465
00:19:50,590 --> 00:19:52,464
Kommer någon ihåg
hur Binary Search fungerar?

466
00:19:52,464 --> 00:19:54,380

467
00:19:54,380 --> 00:19:55,220
Någon alls?

468
00:19:55,220 --> 00:19:56,325
Yeah?

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Du vet när
man tittar på vilken halvlek

470
00:19:58,283 --> 00:20:01,146
det skulle vara i, Baserat på detta,
och bli av med den andra hälften.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1 Exakt.

472
00:20:01,896 --> 00:20:06,290
Så, Binary Search, är det slags en--
--Vi vill kalla det söndra och härska.

473
00:20:06,290 --> 00:20:09,170
Så, vad du ska göra är
du ser i mitten,

474
00:20:09,170 --> 00:20:11,990
och du får se om det matchar
vad du letar efter.

475
00:20:11,990 --> 00:20:15,420
Och om det inte gör det, då du försöker
räkna ut, kommer det att vara kvar

476
00:20:15,420 --> 00:20:16,450
hälften eller den högra halvan.

477
00:20:16,450 --> 00:20:19,325
Så kan det vara om du letar
på något som är alfabetiskt,

478
00:20:19,325 --> 00:20:20,720
du ser, oh.

479
00:20:20,720 --> 00:20:22,750
Har Allison kommer före M?

480
00:20:22,750 --> 00:20:23,250
Ja.

481
00:20:23,250 --> 00:20:25,030
Så, ska vi
titta på den första halvleken.

482
00:20:25,030 --> 00:20:26,450
>> Eller det kan vara som med siffror.

483
00:20:26,450 --> 00:20:28,830
Allt som du kan
jämföra, kan det sorteras.

484
00:20:28,830 --> 00:20:29,920

485
00:20:29,920 --> 00:20:31,260
Du kan använda binär sökning på.

486
00:20:31,260 --> 00:20:32,340

487
00:20:32,340 --> 00:20:37,455
Så, någon som minns detta
graf eller vad det här är?

488
00:20:37,455 --> 00:20:39,520
Det är Asymptotic komplexitet.

489
00:20:39,520 --> 00:20:42,830
Så, detta diagram bara
beskriver hur lång tid det

490
00:20:42,830 --> 00:20:46,230
tar dig att lösa ett problem som
du ökar antalet saker

491
00:20:46,230 --> 00:20:47,090
som du använder.

492
00:20:47,090 --> 00:20:51,260
>> Så vi har N, som är linjär tid.

493
00:20:51,260 --> 00:20:54,560
Om N över två, som är något
bättre, växer fortfarande supersnabb.

494
00:20:54,560 --> 00:20:58,360
Och sedan har vi Login, vilket är
vad vi anser Binary Search.

495
00:20:58,360 --> 00:21:03,630
Om vi ​​märker, eftersom ditt problem
blir mycket och mycket större,

496
00:21:03,630 --> 00:21:06,600
den tid det tar att lösa det
egentligen inte ökar så mycket.

497
00:21:06,600 --> 00:21:09,010
Det är som jämförbara
här i början.

498
00:21:09,010 --> 00:21:10,060
Du är som, OK.

499
00:21:10,060 --> 00:21:13,000
Allt här egentligen inte
Oavsett vilken som vi använder,

500
00:21:13,000 --> 00:21:16,220
men du får ut till en miljon, en miljard.

501
00:21:16,220 --> 00:21:20,010
Du försöker hitta some-- --you're
att försöka hitta en nål i en höstack.

502
00:21:20,010 --> 00:21:21,550
>> Jag tror att du vill ha det här problemet.

503
00:21:21,550 --> 00:21:25,850
Du vill ha denna komplexitet, inte
linjär grund för allt du

504
00:21:25,850 --> 00:21:30,049
vet din gonna söka igenom
varje enskild nål, ting av hö,

505
00:21:30,049 --> 00:21:31,340
försöker leta efter din nål.

506
00:21:31,340 --> 00:21:34,730
Och det är inte alltför roligt i min mening.

507
00:21:34,730 --> 00:21:35,500
Jag gillar snabbt.

508
00:21:35,500 --> 00:21:36,620
Jag gillar effektiv.

509
00:21:36,620 --> 00:21:40,450
Och så hårt arbetande studenter Er
killar är, vet du arbeta smartare,

510
00:21:40,450 --> 00:21:43,010
inte hårdare typ sak, hur man
kan kompensera dessa algoritmer.

511
00:21:43,010 --> 00:21:45,110

512
00:21:45,110 --> 00:21:47,910
>> Så vi kommer att gå
genom bara ett snabbt exempel.

513
00:21:47,910 --> 00:21:51,090
Jag tycker att ni borde ha
en hand på Binary Search,

514
00:21:51,090 --> 00:21:54,352
men om någon är lite
fuzzy, vill förstärka det,

515
00:21:54,352 --> 00:21:56,310
vi ska bara gå
genom ett exempel här.

516
00:21:56,310 --> 00:21:59,490
Så vi söker om
arrayen innehåller sju.

517
00:21:59,490 --> 00:22:00,540

518
00:22:00,540 --> 00:22:06,010
>> Så, är första vi gör
titta i mitten, eller hur?

519
00:22:06,010 --> 00:22:09,340
Och även du kommer att kunna koda
Binär sökning på bara en sekund.

520
00:22:09,340 --> 00:22:11,310
Så det kommer att bli kul.

521
00:22:11,310 --> 00:22:13,710
Så vi tittar på
mitten små arrayer 3.

522
00:22:13,710 --> 00:22:15,501
Betyder tre lika 7?

523
00:22:15,501 --> 00:22:16,000
Inte.

524
00:22:16,000 --> 00:22:18,670

525
00:22:18,670 --> 00:22:19,550
Det är sex.

526
00:22:19,550 --> 00:22:21,480
Så, är det mindre än
eller större än sju?

527
00:22:21,480 --> 00:22:23,080

528
00:22:23,080 --> 00:22:23,960
Mindre än.

529
00:22:23,960 --> 00:22:24,570
Ja.

530
00:22:24,570 --> 00:22:25,170
Fina jobb killar.

531
00:22:25,170 --> 00:22:25,569

532
00:22:25,569 --> 00:22:27,360
Jag känner att jag gillar jag borde
ha godis eftersom jag

533
00:22:27,360 --> 00:22:29,460
vill kasta ut den i varven.

534
00:22:29,460 --> 00:22:30,270
Det är vad jag kommer att göra nästa vecka.

535
00:22:30,270 --> 00:22:31,436
Det kommer att hålla er vassa.

536
00:22:31,436 --> 00:22:32,560

537
00:22:32,560 --> 00:22:34,690
>> Så vi kasta bort det
första halvlek, eller hur?

538
00:22:34,690 --> 00:22:35,670
det var mindre än.

539
00:22:35,670 --> 00:22:39,325
Vi vet att allt
på den vänstra sidan

540
00:22:39,325 --> 00:22:41,700
kommer att vara mindre än vad
vi är faktiskt ute efter.

541
00:22:41,700 --> 00:22:43,491
Så det finns ingen anledning att
uppmärksamma det.

542
00:22:43,491 --> 00:22:45,120
Bara glöm det.

543
00:22:45,120 --> 00:22:48,720
Så, nu tittar vi på vår högra sida,
och vi ser i mitten där borta,

544
00:22:48,720 --> 00:22:50,510
och nu är det nio.

545
00:22:50,510 --> 00:22:55,510
Så, 9 är-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Större än vad vi är
söker, eller hur?

547
00:22:57,470 --> 00:22:59,860
Så vi kommer att kasta
bort allt till höger.

548
00:22:59,860 --> 00:23:00,970

549
00:23:00,970 --> 00:23:01,940
Gillar det.

550
00:23:01,940 --> 00:23:03,700
Nu är alla vi kvar med är en.

551
00:23:03,700 --> 00:23:07,760
Så vi kolla, detta är en vad
Vi är ute efter? det är.

552
00:23:07,760 --> 00:23:08,970
Vi hittade vad vi ville ha.

553
00:23:08,970 --> 00:23:10,440

554
00:23:10,440 --> 00:23:11,690
Så vi är klara.

555
00:23:11,690 --> 00:23:12,550
Bilinjär Search.

556
00:23:12,550 --> 00:23:15,740
>> Och om du märker, vi
hade sju ingångar där.

557
00:23:15,740 --> 00:23:24,320
Det tog oss bara som tre gånger,
men om du gör som en miljard,

558
00:23:24,320 --> 00:23:28,190
ni vet hur många steg det skulle
ta om vi hade fyra miljarder saker?

559
00:23:28,190 --> 00:23:29,940

560
00:23:29,940 --> 00:23:30,455
Any gissningar?

561
00:23:30,455 --> 00:23:32,286

562
00:23:32,286 --> 00:23:33,960
Det är 32.

563
00:23:33,960 --> 00:23:37,110
32 steg för att hitta något
i en fyra miljarder

564
00:23:37,110 --> 00:23:39,650
elementgrupp på grund av potenser av två.

565
00:23:39,650 --> 00:23:43,550
Så två är att 32, är att fyra miljarder.

566
00:23:43,550 --> 00:23:50,430
>> Så ganska galet hur du fortfarande inom
som ett tämligen litet antal steg

567
00:23:50,430 --> 00:23:52,650
hitta något i
fyra miljarder element.

568
00:23:52,650 --> 00:23:55,730
Så på denna anmärkning, vi är
kommer att koda detta

569
00:23:55,730 --> 00:23:58,950
så ni kan faktiskt
typ av se hur detta fungerar.

570
00:23:58,950 --> 00:24:01,520
Okej, så ni kan koda.

571
00:24:01,520 --> 00:24:04,100
Jag kommer att låta er
prata lite.

572
00:24:04,100 --> 00:24:07,970
Lär känna människor runt omkring dig, vilket är
vad någon ville från förra avsnittet.

573
00:24:07,970 --> 00:24:10,280
>> Så lär känna människorna omkring dig.

574
00:24:10,280 --> 00:24:11,305
Prata om lite.

575
00:24:11,305 --> 00:24:12,580

576
00:24:12,580 --> 00:24:15,730
Och allt jag vill ha av dig
killar är just nu bara

577
00:24:15,730 --> 00:24:17,575
försöka skapa en översikt av pseudokod.

578
00:24:17,575 --> 00:24:18,075
OK?

579
00:24:18,075 --> 00:24:20,825

580
00:24:20,825 --> 00:24:21,325
Oj.

581
00:24:21,325 --> 00:24:23,320

582
00:24:23,320 --> 00:24:29,520
Allt jag vill ha av er är att du är
bara att fylla i denna stund fallet.

583
00:24:29,520 --> 00:24:32,170
Så jag har ställt dessa övre
och undre gränser som

584
00:24:32,170 --> 00:24:35,250
representerar början
och slutet av vår samling.

585
00:24:35,250 --> 00:24:40,440
Och du ska faktiskt
loopa igenom och räkna ut

586
00:24:40,440 --> 00:24:42,470
vad vi gör i denna stund slinga.

587
00:24:42,470 --> 00:24:45,810
>> Så om du kan lista out-- jag har
en ledtråd there-- vilka är de fall

588
00:24:45,810 --> 00:24:46,640
som vi har här?

589
00:24:46,640 --> 00:24:48,100

590
00:24:48,100 --> 00:24:51,560
Så om du vill ta reda på
fall kommer vi pseudokod dem

591
00:24:51,560 --> 00:24:53,350
och sedan ska vi faktiskt koda dem.

592
00:24:53,350 --> 00:24:55,330
Och det kommer att bli, jag
tänker, förhoppningsvis det ska

593
00:24:55,330 --> 00:24:56,788
vara lite enklare än du förväntar dig.

594
00:24:56,788 --> 00:24:57,554

595
00:24:57,554 --> 00:25:00,220
För det är inte så mycket kod,
faktiskt, vilket är riktigt coolt.

596
00:25:00,220 --> 00:25:34,110

597
00:25:34,110 --> 00:25:35,018
>> Mm-hm?

598
00:25:35,018 --> 00:25:35,893
>> STUDENTEN [OHÖRBAR]?

599
00:25:35,893 --> 00:25:36,984

600
00:25:36,984 --> 00:25:37,650
INSTRUKTÖR: Ja.

601
00:25:37,650 --> 00:25:38,595
Det var något
att hitta i mitten.

602
00:25:38,595 --> 00:25:39,552
>> STUDENT: Så vi kan använda det.

603
00:25:39,552 --> 00:25:39,770
OK.

604
00:25:39,770 --> 00:25:40,603
>> INSTRUKTÖR: Perfect.

605
00:25:40,603 --> 00:25:42,950
Så det är det första vi måste göra.

606
00:25:42,950 --> 00:25:44,330
Så hitta mitten.

607
00:25:44,330 --> 00:25:45,415

608
00:25:45,415 --> 00:25:45,915
Stor.

609
00:25:45,915 --> 00:25:47,770

610
00:25:47,770 --> 00:25:55,010
Så har du en idé om hur vi kan
faktiskt hitta mitten med koden?

611
00:25:55,010 --> 00:25:55,980
>> STUDENT: Ja.

612
00:25:55,980 --> 00:25:57,000
n över 2?

613
00:25:57,000 --> 00:25:58,500

614
00:25:58,500 --> 00:25:59,500
INSTRUKTÖR: Så n över 2.

615
00:25:59,500 --> 00:26:05,170
Så en sak att komma ihåg är att
din övre och undre gränser förändras.

616
00:26:05,170 --> 00:26:08,110
Vi håller bromsande delen
av arrayen som vi är ute efter att.

617
00:26:08,110 --> 00:26:11,970
Så n över 2 fungerar bara
för det första vi gör.

618
00:26:11,970 --> 00:26:17,810
Så tar övre och nedre i beaktande,
Hur kan vi få det mellersta elementet?

619
00:26:17,810 --> 00:26:20,640
Eftersom vi vill i mitten
mellan övre och nedre, eller hur?

620
00:26:20,640 --> 00:26:21,730

621
00:26:21,730 --> 00:26:22,494
Mm-hm?

622
00:26:22,494 --> 00:26:23,369
>> STUDENTEN [OHÖRBAR].

623
00:26:23,369 --> 00:26:26,170

624
00:26:26,170 --> 00:26:28,080
>> INSTRUKTÖR: Så vi har lite mitten.

625
00:26:28,080 --> 00:26:32,730
Och det ska vara övre plus lägre än 2.

626
00:26:32,730 --> 00:26:34,740

627
00:26:34,740 --> 00:26:35,690
Grymt.

628
00:26:35,690 --> 00:26:36,570
Det gå vi.

629
00:26:36,570 --> 00:26:37,280
En rad nedåt.

630
00:26:37,280 --> 00:26:38,560
Ni är på väg.

631
00:26:38,560 --> 00:26:41,400
Så nu när vi har vår
mitten, vad vill vi göra?

632
00:26:41,400 --> 00:26:45,050

633
00:26:45,050 --> 00:26:45,900
Bara i allmänhet.

634
00:26:45,900 --> 00:26:47,734
Du behöver inte att koda den.

635
00:26:47,734 --> 00:26:48,335
Ja.

636
00:26:48,335 --> 00:26:49,210
STUDENTEN [OHÖRBAR]?

637
00:26:49,210 --> 00:27:00,310

638
00:27:00,310 --> 00:27:10,310
INSTRUKTÖR: Så det är plus för att du är
hitta medelvärdet mellan de två

639
00:27:10,310 --> 00:27:10,810
av dem.

640
00:27:10,810 --> 00:27:11,890

641
00:27:11,890 --> 00:27:17,370
Så om du tänker på dem som slag
att öka in från sidorna,

642
00:27:17,370 --> 00:27:21,640
tänk på det när du närmar dig
mitten, du vill så.

643
00:27:21,640 --> 00:27:27,150
Så om du var på vardera sidan av
mitten, och vi har som 5 och 7.

644
00:27:27,150 --> 00:27:31,440
När du lägger ihop dem dig
få 12, delar du med 2, är 6.

645
00:27:31,440 --> 00:27:33,726
>> Ibland är det svårt att
förklara varför det fungerar,

646
00:27:33,726 --> 00:27:35,600
men om du arbetar igenom
ett exempel ibland,

647
00:27:35,600 --> 00:27:37,962
det hjälper dig att räkna ut om
det bör vara plus eller minus.

648
00:27:37,962 --> 00:27:38,846
Ja.

649
00:27:38,846 --> 00:27:40,830
>> STUDENTEN [OHÖRBAR]
exakt i mitten

650
00:27:40,830 --> 00:27:43,950
om de hade ett fall där
det finns en hel del mindre antal

651
00:27:43,950 --> 00:27:45,860
och som en stort antal?

652
00:27:45,860 --> 00:27:49,750
>> INSTRUKTÖR: Så allt du behöver
är i mitten av uppsättningen.

653
00:27:49,750 --> 00:27:53,010
Så om du hade ett gäng små siffror
och sedan en riktigt stor mängd

654
00:27:53,010 --> 00:27:54,799
i slutet, det spelar ingen roll.

655
00:27:54,799 --> 00:27:56,840
Det avgörande är att
de är sorterade, du bara

656
00:27:56,840 --> 00:27:59,339
vill titta på mitten av
arrayen eftersom du fortfarande

657
00:27:59,339 --> 00:28:00,700
skivning ditt problem i hälften.

658
00:28:00,700 --> 00:28:03,020

659
00:28:03,020 --> 00:28:03,680
Cool.

660
00:28:03,680 --> 00:28:06,430
Så nu när vi har
mitt, vad gör vi nu?

661
00:28:06,430 --> 00:28:07,150
>> STUDENTEN Jämför.

662
00:28:07,150 --> 00:28:08,150
INSTRUKTÖR: Den jämföra.

663
00:28:08,150 --> 00:28:11,670
Så jämför mitten till value_wanted.

664
00:28:11,670 --> 00:28:14,300

665
00:28:14,300 --> 00:28:15,160
Cool.

666
00:28:15,160 --> 00:28:17,950
Så ni ser här uppe har vi
detta värde som vi vill ha här uppe.

667
00:28:17,950 --> 00:28:22,012

668
00:28:22,012 --> 00:28:23,095
Kom ihåg att detta är en array.

669
00:28:23,095 --> 00:28:24,100

670
00:28:24,100 --> 00:28:26,970
Så mitt hänvisar till index.

671
00:28:26,970 --> 00:28:29,785
Så vi vill göra värden på mitten.

672
00:28:29,785 --> 00:28:32,380

673
00:28:32,380 --> 00:28:35,650
Glöm inte om du vill
att jämföra, dubbla jämlikar.

674
00:28:35,650 --> 00:28:38,250
Du gör enda lika är du
bara kommer att dela ut det,

675
00:28:38,250 --> 00:28:41,090
och sedan, naturligtvis, är det
kommer att vara det värde du vill ha.

676
00:28:41,090 --> 00:28:42,300
Så gör inte det.

677
00:28:42,300 --> 00:28:44,350
>> Så vi kommer att se om
värdena vid mitten

678
00:28:44,350 --> 00:28:46,460
är lika med värdet vi vill ha.

679
00:28:46,460 --> 00:28:47,749

680
00:28:47,749 --> 00:28:48,790
Glöm inte dina hängslen.

681
00:28:48,790 --> 00:28:50,520

682
00:28:50,520 --> 00:28:52,235
Dropbox bör försvinna.

683
00:28:52,235 --> 00:28:54,140

684
00:28:54,140 --> 00:28:56,200
Så vad gör vi i det här fallet?

685
00:28:56,200 --> 00:28:59,360
Om det är vad vi vill återvända?

686
00:28:59,360 --> 00:29:01,510

687
00:29:01,510 --> 00:29:02,626
Vi försöker säga.

688
00:29:02,626 --> 00:29:03,440
>> STUDENT: Skriv ut.

689
00:29:03,440 --> 00:29:05,314
>> INSTRUKTÖR: Tja, vi
vill inte skriva ut.

690
00:29:05,314 --> 00:29:08,220
Så det här är en bool här, så vi
vill returnera sant eller falskt.

691
00:29:08,220 --> 00:29:12,280
Vi säger, är detta nummer
en [? RRA? ?] Så om det är,

692
00:29:12,280 --> 00:29:13,788
vi tillbaka bara sant.

693
00:29:13,788 --> 00:29:16,780

694
00:29:16,780 --> 00:29:17,760
Om jag kan stava sant.

695
00:29:17,760 --> 00:29:18,830

696
00:29:18,830 --> 00:29:20,805
>> STUDENT: Varför skulle du inte returnera noll?

697
00:29:20,805 --> 00:29:22,930
INSTRUKTÖR: Så du kunde
returnera noll om du ville.

698
00:29:22,930 --> 00:29:26,780
Men i detta fall eftersom
vår funktion returnerar en bool,

699
00:29:26,780 --> 00:29:28,962
Vi behöver gå tillbaka antingen sant eller falskt.

700
00:29:28,962 --> 00:29:30,920
STUDENT: När du är
säger boolska uttrycket,

701
00:29:30,920 --> 00:29:33,450
kan du ställa in den lika med falskt?

702
00:29:33,450 --> 00:29:39,860
Som om jag vill säga, om detta villkor
inte uppfylls, som är övre lika falskt.

703
00:29:39,860 --> 00:29:42,332
Kommer det att förstå om du bara
sätta falskt på andra sidan?

704
00:29:42,332 --> 00:29:43,040
INSTRUKTÖR: Ja.

705
00:29:43,040 --> 00:29:44,820
Så egentligen om du är
någonsin göra något

706
00:29:44,820 --> 00:29:49,600
som är övre eller lägre,
som returnerar sant eller falskt

707
00:29:49,600 --> 00:29:53,850
och det är faktiskt dålig stil till
säg lika lika sant eller jämlikar

708
00:29:53,850 --> 00:29:54,840
lika falskt.

709
00:29:54,840 --> 00:30:00,210
Du vill använda detta resultat
som själv som din check.

710
00:30:00,210 --> 00:30:04,720

711
00:30:04,720 --> 00:30:05,860
Inte vad jag ville.

712
00:30:05,860 --> 00:30:08,150

713
00:30:08,150 --> 00:30:09,240
Det är vad jag ville ha.

714
00:30:09,240 --> 00:30:13,205
Så i fallet med du frågar
om något liknande spara i c.

715
00:30:13,205 --> 00:30:16,320

716
00:30:16,320 --> 00:30:25,150
>> Så om vi har int main (void)
och ungefär så här.

717
00:30:25,150 --> 00:30:31,922
Och du har om är övre
av lite input och du är

718
00:30:31,922 --> 00:30:33,630
frågar om du kan göra
ungefär så här?

719
00:30:33,630 --> 00:30:35,010

720
00:30:35,010 --> 00:30:35,679
Rätt?

721
00:30:35,679 --> 00:30:37,470
STUDENT: Jag försökte
att göra det [OHÖRBAR].

722
00:30:37,470 --> 00:30:38,450
För om it's--

723
00:30:38,450 --> 00:30:39,200
INSTRUKTÖR: Rätt.

724
00:30:39,200 --> 00:30:41,197
Så du vill att detta ska vara falska, eller hur?

725
00:30:41,197 --> 00:30:41,780
STUDENT: Ja.

726
00:30:41,780 --> 00:30:45,960
INSTRUKTÖR: Så i detta fall du
vill att den ska köra om det inte är sant.

727
00:30:45,960 --> 00:30:50,510
Så cool sak du gör det finns det.

728
00:30:50,510 --> 00:30:52,900

729
00:30:52,900 --> 00:30:55,650
Så minns utrop
punkt förnekar saker?

730
00:30:55,650 --> 00:30:58,270
Det står [OHÖRBAR] betyder inte.

731
00:30:58,270 --> 00:31:03,590
Så om vi tittar på just
denna del här, skulle du

732
00:31:03,590 --> 00:31:05,740
säger att utvärderas till
falsk som du vill.

733
00:31:05,740 --> 00:31:06,790

734
00:31:06,790 --> 00:31:09,880
Inte falskt är sant, som
innebär detta skulle exekvera.

735
00:31:09,880 --> 00:31:11,037
Är det vettigt?

736
00:31:11,037 --> 00:31:11,620
STUDENT: Ja.

737
00:31:11,620 --> 00:31:12,453
INSTRUKTÖR: Awesome.

738
00:31:12,453 --> 00:31:13,800

739
00:31:13,800 --> 00:31:14,300
OK.

740
00:31:14,300 --> 00:31:16,330
Så vi kunde bara tillbaka
sant i detta fall.

741
00:31:16,330 --> 00:31:20,357
Så nu har vi två andra
fall i det här fallet.

742
00:31:20,357 --> 00:31:21,565
Vilka är våra två andra fall?

743
00:31:21,565 --> 00:31:31,610

744
00:31:31,610 --> 00:31:32,900
Låt oss bara göra det här sättet.

745
00:31:32,900 --> 00:31:40,660
Så låt oss börja med annat
Om värden på mitten

746
00:31:40,660 --> 00:31:43,230
är mindre än det värde som vi vill ha.

747
00:31:43,230 --> 00:31:47,200

748
00:31:47,200 --> 00:31:52,020
Så vårt värde i mitten är mindre
än det värde som vi letar efter.

749
00:31:52,020 --> 00:31:53,765

750
00:31:53,765 --> 00:31:56,720
>> Så som bundet gör du
tror att vi vill uppdatera?

751
00:31:56,720 --> 00:31:57,870

752
00:31:57,870 --> 00:31:58,780
Övre eller nedre?

753
00:31:58,780 --> 00:32:01,440

754
00:32:01,440 --> 00:32:01,940
Övre?

755
00:32:01,940 --> 00:32:03,230

756
00:32:03,230 --> 00:32:06,470
Så vilken sida av matrisen
kommer vi att titta på?

757
00:32:06,470 --> 00:32:07,500
>> STUDENTEN Den lägre.

758
00:32:07,500 --> 00:32:09,750
>> INSTRUKTÖR: Vi kommer vi
att titta till vänster.

759
00:32:09,750 --> 00:32:11,120
Så annars om litet värde är lägre.

760
00:32:11,120 --> 00:32:14,730
Så din mittersta värdet här
är mindre än vad vi vill.

761
00:32:14,730 --> 00:32:17,202
Så vi vill ta
höger sida av vår array.

762
00:32:17,202 --> 00:32:18,910
Så vi kommer att
uppdatera vår nedre gräns.

763
00:32:18,910 --> 00:32:20,210

764
00:32:20,210 --> 00:32:23,020
Så vi ska överlåta vår lägre.

765
00:32:23,020 --> 00:32:25,221
Och vad tror du lägre borde vara?

766
00:32:25,221 --> 00:32:26,304
STUDENT: Det mittersta värdet?

767
00:32:26,304 --> 00:32:27,446

768
00:32:27,446 --> 00:32:28,820
INSTRUKTÖR: Så mitt value--

769
00:32:28,820 --> 00:32:30,136
STUDENT: Plus 1.

770
00:32:30,136 --> 00:32:31,010
INSTRUKTÖR: --plus 1.

771
00:32:31,010 --> 00:32:32,300

772
00:32:32,300 --> 00:32:34,380
Kan någon berätta för mig varför
vi har det plus 1?

773
00:32:34,380 --> 00:32:35,730
>> STUDENT: [? Inget värde?]
är lika med den.

774
00:32:35,730 --> 00:32:36,120
>> INSTRUKTÖR: Rätt.

775
00:32:36,120 --> 00:32:38,661
Eftersom vi redan vet att
vår mittersta värdet inte är lika med

776
00:32:38,661 --> 00:32:42,750
det och vi vill utesluta det
från alla efterföljande sökningar.

777
00:32:42,750 --> 00:32:46,360
Om du glömmer att plus 1, detta
kommer att gilla slinga på obestämd tid.

778
00:32:46,360 --> 00:32:49,620
Och du kommer bara att fångas i en
oändlig loop och då kommer du segfault

779
00:32:49,620 --> 00:32:50,370
och det går dåligt.

780
00:32:50,370 --> 00:32:54,780
Så alltid se till att du inte är
inklusive det värde som du bara

781
00:32:54,780 --> 00:32:55,380
såg på.

782
00:32:55,380 --> 00:32:58,530
Så vi tar hand om det med ett plus 1.

783
00:32:58,530 --> 00:33:04,840
>> Så nu har vi vår sista villkoret
som jag alltid för säkerhets skull

784
00:33:04,840 --> 00:33:12,664
Du kan kolla här, annars om värdet på
mitten är större än värdet

785
00:33:12,664 --> 00:33:13,163
vi vill ha.

786
00:33:13,163 --> 00:33:16,260

787
00:33:16,260 --> 00:33:20,230
Det betyder att vi vill
den vänstra halvan.

788
00:33:20,230 --> 00:33:21,350

789
00:33:21,350 --> 00:33:23,260
Så som man ska vi uppdatera?

790
00:33:23,260 --> 00:33:23,760
Övre.

791
00:33:23,760 --> 00:33:25,470

792
00:33:25,470 --> 00:33:26,970
Och vad är det här man ska vara lika?

793
00:33:26,970 --> 00:33:31,630

794
00:33:31,630 --> 00:33:33,690
USA minus en grund,
Naturligtvis vill vi

795
00:33:33,690 --> 00:33:38,370
att se till att vi inte är
titta på det mittersta värdet igen.

796
00:33:38,370 --> 00:33:41,830

797
00:33:41,830 --> 00:33:45,110
Och så har vi det.

798
00:33:45,110 --> 00:33:45,610
Det var allt.

799
00:33:45,610 --> 00:33:46,820
Det är allt binär sökning är.

800
00:33:46,820 --> 00:33:48,190
Det är inte så illa, eller hur?

801
00:33:48,190 --> 00:33:51,590
Det är som 10 rader
kod med blanktecken.

802
00:33:51,590 --> 00:33:57,510
Så mycket kraftfull, mycket användbar, kommer du
att använda den i en av dina senare psets.

803
00:33:57,510 --> 00:33:59,360
Kanske inte den här, men senare.

804
00:33:59,360 --> 00:34:00,670
Så lär det.

805
00:34:00,670 --> 00:34:01,510
Älskar det.

806
00:34:01,510 --> 00:34:02,980
Den kommer att behandla dig väl.

807
00:34:02,980 --> 00:34:05,370
Så är det någon som har någon
frågor om binär sökning?

808
00:34:05,370 --> 00:34:06,196
Ja.

809
00:34:06,196 --> 00:34:09,840
>> STUDENT: Spelar det någon roll
om din n är jämnt eller udda?

810
00:34:09,840 --> 00:34:10,750
>> INSTRUKTÖR: Nej.

811
00:34:10,750 --> 00:34:18,150
Eftersom vi kastade den till mitten som
en int, kommer det bara korta av den.

812
00:34:18,150 --> 00:34:21,600
Så det kommer att förbli ett heltal och det kommer
småningom sortera igenom allt.

813
00:34:21,600 --> 00:34:23,909
Så du behöver inte oroa dig för det.

814
00:34:23,909 --> 00:34:24,580
Alla bra?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Grymt.

817
00:34:26,850 --> 00:34:27,919
Cool.

818
00:34:27,919 --> 00:34:30,836
Så, ni fick detta.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
Bildspel.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
Så när vi talade om, jag vet
David nämnts komplexitetsdrifttider.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Så i bästa fall är det bara
en, som vi kallar konstant tid.

825
00:34:50,340 --> 00:34:51,909
Kan någon berätta för mig varför det kan vara?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Vilken typ av scenario som skulle innebära?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
Mm-hm.

830
00:34:58,760 --> 00:34:59,926
>> STUDENTEN [OHÖRBAR] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
INSTRUKTÖR: Så mitten är den
första element som vi kommer till, eller hur?

833
00:35:03,830 --> 00:35:08,167
Så antingen en matris med en eller
vad vi letar efter just

834
00:35:08,167 --> 00:35:09,750
råkar vara smack dab i mitten.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Så det är vårt bästa fall.

837
00:35:13,380 --> 00:35:17,540
Du får till verkliga problem, förmodligen inte
kommer att nå [OHÖRBAR] så ofta.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Hur är vår värsta fall?

840
00:35:19,750 --> 00:35:21,270
Vår värsta fall är log n.

841
00:35:21,270 --> 00:35:25,360
Och det har att göra med det hela
befogenheter två sak som jag talade om.

842
00:35:25,360 --> 00:35:30,930
>> Så i värsta fall skulle det innebära
att vi var tvungna att hugga arrayen ner

843
00:35:30,930 --> 00:35:33,270
tills det var en del av en.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Så vi var tvungna att hugga ner det i hälften
så många gånger som vi möjligen kunde.

846
00:35:38,930 --> 00:35:41,430
Det är därför det är log n eftersom
du bara hålla dividera med två.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Så antaganden, saker du
behöver veta om du någonsin

849
00:35:45,830 --> 00:35:48,050
kommer att använda en binär sökning.

850
00:35:48,050 --> 00:35:50,680
Dina element måste sorteras.

851
00:35:50,680 --> 00:35:53,890
De måste sorteras, eftersom
det är det enda sättet du

852
00:35:53,890 --> 00:35:57,060
kan veta om du kan
att kasta ut hälften av det.

853
00:35:57,060 --> 00:36:00,260
>> Om du hade denna rörig väska
av siffror och du säger,

854
00:36:00,260 --> 00:36:05,380
OK, jag ska kolla mitt
nummer och numret jag letar efter

855
00:36:05,380 --> 00:36:08,510
är mindre än så, jag ska bara
godtyckligt kasta ut hälften.

856
00:36:08,510 --> 00:36:11,130
Du skulle inte veta om din
nummer i den andra halvan.

857
00:36:11,130 --> 00:36:12,655
Din lista måste sorteras.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Vad bra, kan detta vara
går framåt en liten bit,

860
00:36:16,560 --> 00:36:18,360
men du måste ha direktåtkomst.

861
00:36:18,360 --> 00:36:21,940
Du måste kunna bara
gå till den mellersta del.

862
00:36:21,940 --> 00:36:25,110
Om du måste korsa
genom något

863
00:36:25,110 --> 00:36:28,630
eller så tar du extra steg
att komma till den mellersta del,

864
00:36:28,630 --> 00:36:31,750
det är inte log n längre eftersom
du lägger mer arbete i den.

865
00:36:31,750 --> 00:36:34,800
Och detta kommer att göra en liten
mer meningsfullt i två veckor,

866
00:36:34,800 --> 00:36:37,950
men jag bara typ av ville förord,
ge er en uppfattning om vad som är

867
00:36:37,950 --> 00:36:38,999
att komma.

868
00:36:38,999 --> 00:36:40,790
Men de är de två
viktiga antaganden

869
00:36:40,790 --> 00:36:44,804
som du behöver för en binär lista.

870
00:36:44,804 --> 00:36:45,720
Se till att den är sorterade.

871
00:36:45,720 --> 00:36:47,920
Det är den stora en för
ni just nu.

872
00:36:47,920 --> 00:36:52,170
Och på att vi kan gå in i
resten av våra slag.

873
00:36:52,170 --> 00:36:56,444
Så fyra sorts-- bubbla,
insättning, urval och sammanslagning.

874
00:36:56,444 --> 00:36:57,485
De är alla ganska häftigt.

875
00:36:57,485 --> 00:37:02,860
Om ni väljer att ta CS 124,
du kommer att lära dig om alla möjliga slag.

876
00:37:02,860 --> 00:37:07,575
Och om du är en XKCD fan, det
är en riktigt cool serie om

877
00:37:07,575 --> 00:37:11,530
gillar verkligen ineffektiva slag, som jag
starkt rekommendera att du ska titta på.

878
00:37:11,530 --> 00:37:16,170
En av dem är som panik sortera, vilket
är som, åh nej, tillbaka slumpvis rad.

879
00:37:16,170 --> 00:37:16,991
Avstängning systemet.

880
00:37:16,991 --> 00:37:17,490
Lämna.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Så geeky humor är alltid bra.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Så är det någon som minns snäll
av som bara en allmän uppfattning

885
00:37:25,750 --> 00:37:27,810
hur bubbla sortera fungerar.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Ni minns?

888
00:37:32,155 --> 00:37:32,755
>> STUDENT: Ja.

889
00:37:32,755 --> 00:37:33,970
>> INSTRUKTÖR: Gå för det.

890
00:37:33,970 --> 00:37:38,980
>> STUDENT: Så du går igenom och
om det är större, då du byter de två.

891
00:37:38,980 --> 00:37:39,820
>> INSTRUKTÖR: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Exakt.

893
00:37:40,564 --> 00:37:41,730
Så du bara iterera igenom.

894
00:37:41,730 --> 00:37:43,050
Du kontrollerar två nummer.

895
00:37:43,050 --> 00:37:46,510
Om man tidigare är större
än en efteråt,

896
00:37:46,510 --> 00:37:50,230
du bara byta dem så att i
detta sätt alla de högre siffror

897
00:37:50,230 --> 00:37:54,990
bubbla upp mot slutet av listan
och alla lägre siffror bubbla ner.

898
00:37:54,990 --> 00:37:59,355
>> Har han visa er den svala
ljudeffekt sortering video?

899
00:37:59,355 --> 00:38:00,480
Det är ganska häftigt.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Så när Robert sa bara, algoritmen
att du bara stega genom listan,

902
00:38:05,200 --> 00:38:07,930
byta intilliggande värdena
om de inte är i ordning.

903
00:38:07,930 --> 00:38:10,975
Och sedan bara fortsätta att upprepa
tills du inte gör några swappar.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Så inte illa, eller hur?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Så vi har bara en snabb exempel här.

908
00:38:16,319 --> 00:38:18,360
Så detta kommer att sortera
dem i stigande ordning.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Så när vi går igenom den första
tid, ser vi till åtta

911
00:38:23,470 --> 00:38:26,880
och sex är uppenbarligen inte
i ordning, vi byta dem.

912
00:38:26,880 --> 00:38:27,985
>> Så titta på nästa.

913
00:38:27,985 --> 00:38:29,430
Åtta och fyra inte är i ordning.

914
00:38:29,430 --> 00:38:30,450
Byta dem.

915
00:38:30,450 --> 00:38:32,530
Och sedan åtta och två, byta dem.

916
00:38:32,530 --> 00:38:33,470
Det gå vi.

917
00:38:33,470 --> 00:38:39,519
Så efter din första passet, du
vet att din största antalet

918
00:38:39,519 --> 00:38:41,810
kommer att vara hela vägen
upptill eftersom det är bara

919
00:38:41,810 --> 00:38:44,210
kommer att vara ständigt
större än allt annat

920
00:38:44,210 --> 00:38:46,810
och det är bara att bubbla
upp hela vägen till slutet där.

921
00:38:46,810 --> 00:38:48,226
Är det vettigt att alla?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Cool.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Så då tittar vi på vår andra passet.

926
00:38:53,920 --> 00:38:54,980
Sex och fyra, switch.

927
00:38:54,980 --> 00:38:55,920
Sex och två, switch.

928
00:38:55,920 --> 00:38:58,700
Och nu har vi ett par saker i ordning.

929
00:38:58,700 --> 00:39:02,240
Så för varje pass som vi
gör genom hela vår lista,

930
00:39:02,240 --> 00:39:06,320
Vi vet att som så många siffror
I slutet kommer har sorterats.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Så vi gör ett tredje pass,
som är en swap.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
Och sedan på vår fjärde
passera, vi har noll slots.

935
00:39:15,910 --> 00:39:18,570
Och så vi vet att vår
array har sorterats.

936
00:39:18,570 --> 00:39:20,900
>> Och det är den stora
sak med bubbel sort.

937
00:39:20,900 --> 00:39:23,720
Vi vet att när vi
har noll swappar, att

938
00:39:23,720 --> 00:39:26,497
innebär att allt
är i fullständig ordning.

939
00:39:26,497 --> 00:39:27,580
Det är typ hur vi kontrollerar.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Så vi kommer också att koda bubbla
slag som också är inte så illa.

942
00:39:36,480 --> 00:39:38,120
Ingen av dessa är så illa.

943
00:39:38,120 --> 00:39:40,210
Jag vet att de kan verka lite skrämmande.

944
00:39:40,210 --> 00:39:42,124
Jag vet när jag tog
klassen, även när jag

945
00:39:42,124 --> 00:39:44,290
undervisade klassen för
första gången förra året,

946
00:39:44,290 --> 00:39:46,165
Jag var ut, hur gör jag detta?

947
00:39:46,165 --> 00:39:48,540
Det är vettigt i teorin, men
hur ska vi egentligen göra det?

948
00:39:48,540 --> 00:39:51,420
Det är därför jag vill också gå
genom kod med er här.

949
00:39:51,420 --> 00:39:54,915
Så jag har en pseudo
för er den här gången.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Så bara ha detta i åtanke när
vi håller på att övergången över.

952
00:39:58,970 --> 00:40:04,210
Så vi har några räknare som
håller reda på våra swappar,

953
00:40:04,210 --> 00:40:08,370
eftersom vi måste se till
att vi kollar det.

954
00:40:08,370 --> 00:40:11,830
Och vi upprepa hela uppsättningen
som vi gjorde just med detta exempel.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Om elementet innan är större än
elementet efter var vi är på,

957
00:40:17,325 --> 00:40:20,760
Vi byter dem och vi öka vår
räknare eftersom så snart vi byta,

958
00:40:20,760 --> 00:40:23,850
Vi vill låta vår räknare vet.

959
00:40:23,850 --> 00:40:26,247
Några frågor där?

960
00:40:26,247 --> 00:40:27,580
Något verkar roligt här.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
STUDENT: Har du ställa räkneverket noll
varje gång du går genom öglan?

963
00:40:32,350 --> 00:40:34,339
Vill du inte fortsätta
tillbaka till noll varje gång?

964
00:40:34,339 --> 00:40:35,505
INSTRUKTÖR: Inte nödvändigtvis.

965
00:40:35,505 --> 00:40:39,710
Så vad som händer är att vi går igenom här.

966
00:40:39,710 --> 00:40:43,830
Så gör samtidigt, kom ihåg, detta
kommer att utföra en gång utan att misslyckas.

967
00:40:43,830 --> 00:40:46,480
Så det kommer att ställa in
räknaren är lika med noll,

968
00:40:46,480 --> 00:40:48,070
då det kommer att iterera igenom.

969
00:40:48,070 --> 00:40:50,590
Som det itererar igenom,
det kommer att uppdatera räknaren.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Som det uppdateras räknaren, när det är gjort,
när det har nått slutet av arrayen,

972
00:40:56,900 --> 00:41:00,830
Om vår lista inte har sorterats,
räknaren har uppdaterats.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Så då är det en kontroll utförs och det
säger, OK, är räknaren är större än noll.

975
00:41:07,150 --> 00:41:09,290
Om det är, gör det igen.

976
00:41:09,290 --> 00:41:14,340
Du vill återställa så att när du
går igenom, är räknaren är lika med noll.

977
00:41:14,340 --> 00:41:18,240
Om du går igenom en sorterad
array, förändrar ingenting,

978
00:41:18,240 --> 00:41:21,355
detta misslyckas, och du
returnera den sorterade listan.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Är det vettigt?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
STUDENT: Det kanske i lite.

983
00:41:26,356 --> 00:41:27,147
INSTRUKTÖR: OK.

984
00:41:27,147 --> 00:41:28,980
Om det finns någon annan
fråga som kommer upp.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Ja.

987
00:41:30,680 --> 00:41:33,760
>> STUDENTEN Vad skulle funktionen
vara för att byta element?

988
00:41:33,760 --> 00:41:36,900
>> INSTRUKTÖR: Så vi kan faktiskt skriva
att om vi ska just nu.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Cool.

991
00:41:38,300 --> 00:41:42,155
Så på att observera, är Alison går
för att växla tillbaka till apparaten.

992
00:41:42,155 --> 00:41:43,080
Det kommer att bli kul.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
Och vi har vår trevliga
bubbla sortera sak här.

995
00:41:47,390 --> 00:41:50,800
Så jag gjorde redan cykling
genom uppsättningen.

996
00:41:50,800 --> 00:41:53,030
Vi har våra swappar som
är lika med noll.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Så vi vill byta intilliggande
element om de är ur funktion.

999
00:41:58,440 --> 00:42:03,020
Så det första måste vi
gör är iterera igenom vår samling.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Så hur tycker du att vi kanske
iterera genom vår array?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Vi har för och jag är lika med 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Vi vill att jag ska vara mindre
än n minus 1 minus k.

1006
00:42:22,454 --> 00:42:23,870
Och jag ska förklara det på en sekund.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Så detta är en optimering här där,
minns hur jag sa efter varje pass

1009
00:42:32,830 --> 00:42:36,655
genom uppsättningen vi
vet att vad som än är on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Så efter ett pass vi
vet att detta är sorterad.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Efter två passager vi vet
att allt detta är sorterad.

1014
00:42:50,060 --> 00:42:52,750
Efter tre passager vi
vet som är sorterade.

1015
00:42:52,750 --> 00:42:55,620
Så långt jag iteration
genom uppsättningen här,

1016
00:42:55,620 --> 00:43:01,090
är det att se till att bara gå
genom vad vi vet är osorterat.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Det är bara en optimering.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Du kan skriva det naivt bara
iterera igenom allt,

1021
00:43:08,210 --> 00:43:09,970
Det skulle bara ta längre tid.

1022
00:43:09,970 --> 00:43:12,470
Med denna fyra slinga är det
bara en trevlig optimering

1023
00:43:12,470 --> 00:43:18,460
eftersom vi vet att efter varje helt
iteration genom uppsättningen här,

1024
00:43:18,460 --> 00:43:24,050
som varje hel slinga här, vi vet
att en av dessa komponenter

1025
00:43:24,050 --> 00:43:25,760
kommer att sorteras i slutet.

1026
00:43:25,760 --> 00:43:28,294
>> Så vi behöver inte oroa dig för dem.

1027
00:43:28,294 --> 00:43:29,710
Är det vettigt att alla?

1028
00:43:29,710 --> 00:43:30,950
Den coola lilla trick?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Så i så fall, om
vi iterera igenom,

1031
00:43:37,270 --> 00:43:50,590
vi vet att vi vill kontrollera om
array n och n plus 1 är i ordning.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
OK.

1034
00:43:53,559 --> 00:43:54,600
Så här är pseudokod.

1035
00:43:54,600 --> 00:43:57,540
Vi vill kolla om array n
och n plus 1 är i ordning.

1036
00:43:57,540 --> 00:43:59,520
Så vad kan vi ha det?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Det kommer att bli lite villkor.

1039
00:44:03,120 --> 00:44:04,220
Det kommer att bli en om.

1040
00:44:04,220 --> 00:44:07,066
>> STUDENT: Om matris n är
mindre än array n plus 1.

1041
00:44:07,066 --> 00:44:07,816
INSTRUKTÖR: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
Tja, mindre än eller större än.

1044
00:44:10,699 --> 00:44:11,615
STUDENT: Större än.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Då vill vi att byta dem.

1047
00:44:17,620 --> 00:44:18,570
Exakt.

1048
00:44:18,570 --> 00:44:23,570
Så nu får vi in ​​vad är det
mekanism för att byta dem?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Så vi gick igenom det här en kort stund,
en typ av swap-funktion förra veckan.

1051
00:44:28,137 --> 00:44:29,595
Finns det någon som minns hur det fungerade?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Så vi kan inte bara överlåta dem, eller hur?

1054
00:44:34,950 --> 00:44:36,640
Eftersom en av dem kommer att gå vilse.

1055
00:44:36,640 --> 00:44:41,696
Om vi ​​sagt A är lika med B och sedan B
är lika med A, alla en plötslig båda av dem

1056
00:44:41,696 --> 00:44:43,150
är bara lika med B.

1057
00:44:43,150 --> 00:44:45,720
>> Så vad vi har att göra är att vi
har en temporär variabel som är

1058
00:44:45,720 --> 00:44:49,055
kommer att hålla en av våra stund
vi är i färd med att byta.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Så vad vi har är att vi ska ha lite int
temp är lika att-- du kan tilldela den

1061
00:44:56,464 --> 00:44:59,130
till vilken du vill, bara
se till att du hålla reda på det--

1062
00:44:59,130 --> 00:45:01,840
så i det här fallet, kommer jag att
tilldela den till array n plus 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Så det kommer att innehåla
värde i det andra blocket

1065
00:45:07,674 --> 00:45:08,590
att vi tittar på.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> Och då vi kan göra är att vi kan gå
framåt och tilldela array n plus 1,

1068
00:45:13,240 --> 00:45:14,990
eftersom vi vet att vi
har detta värde lagras.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Detta är också en av de stora
saker-- Jag vet inte om någon av er

1071
00:45:19,270 --> 00:45:23,780
hade frågor där om du byter två
kodrader plötsligt saker fungerade.

1072
00:45:23,780 --> 00:45:25,880
Order är mycket viktigt i CS.

1073
00:45:25,880 --> 00:45:29,450
Så se till att du diagram
saker ut om det är möjligt

1074
00:45:29,450 --> 00:45:31,230
om vad som faktiskt händer.

1075
00:45:31,230 --> 00:45:34,256
Så nu ska vi
överlåta array n plus 1,

1076
00:45:34,256 --> 00:45:36,005
eftersom vi vet att vi
har detta värde lagras.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> Och vi kan tilldela till array
n eller i detta fall array i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
För många variabler.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
OK.

1083
00:45:55,470 --> 00:46:01,500
Så nu har vi tilldelas array i
plus 1 till lika vad som finns i arrayen i.

1084
00:46:01,500 --> 00:46:08,240
Och nu kan vi gå tillbaka och
tilldela array i vad?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Någon?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> STUDENTEN 10.

1089
00:46:14,010 --> 00:46:14,680
>> INSTRUKTÖR: 10.

1090
00:46:14,680 --> 00:46:15,180
Exakt.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
Och en sista sak.

1093
00:46:18,640 --> 00:46:21,840
Om vi ​​har bytt det nu,
Vad behöver vi göra?

1094
00:46:21,840 --> 00:46:23,740
Vad är en sak
det kommer att berätta

1095
00:46:23,740 --> 00:46:27,542
om vi någonsin avsluta det här programmet?

1096
00:46:27,542 --> 00:46:29,250
Vad säger oss att vi
har en sorterad lista?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Om vi ​​inte utför några swappar, eller hur?

1099
00:46:33,750 --> 00:46:36,900
Om swappar är lika med
noll vid slutet av denna.

1100
00:46:36,900 --> 00:46:42,975
Så varje gång du gör en swap, som vi
just gjorde här, vi vill uppdatera swappar.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
Och jag vet att det fanns en
fråga tidigare om kan du

1103
00:46:47,210 --> 00:46:49,689
använda noll eller ett i stället
av sant eller falskt.

1104
00:46:49,689 --> 00:46:50,980
Och det är vad det gör här.

1105
00:46:50,980 --> 00:46:52,750
Så detta säger om inte swappar.

1106
00:46:52,750 --> 00:47:01,310
Så om swappar är noll, som är-- jag alltid
få mina sanningar och mina falses blandas ihop.

1107
00:47:01,310 --> 00:47:03,960
Vi vill att vi ska utvärdera
till true, och det är inte.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Så om det är noll, då är det falskt.

1110
00:47:09,630 --> 00:47:12,560
Om du förnekar det med en
[? bang?] blir det sant.

1111
00:47:12,560 --> 00:47:13,975
Så då denna linje körs.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Sanningar och falska och
nollor och ettor blir galen.

1114
00:47:17,370 --> 00:47:20,690
Bara om du sakta gå
igenom det kommer det att vara meningsfullt.

1115
00:47:20,690 --> 00:47:23,320
Men det är vad denna lilla
bit kod här gör.

1116
00:47:23,320 --> 00:47:26,490
Så detta kontrollerar för att se
Vi har gjort några swappar.

1117
00:47:26,490 --> 00:47:30,054
Så om det är något annat än
noll, det kommer att vara falsk

1118
00:47:30,054 --> 00:47:31,970
och det hela är
kommer att exekvera på nytt.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
Cool?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> STUDENTEN Vad gör break göra?

1123
00:47:36,000 --> 00:47:38,990
>> INSTRUKTÖR: Bryt bara
bryter dig ut ur loopen.

1124
00:47:38,990 --> 00:47:41,570
Så i detta fall att det skulle
precis som avslutar programmet

1125
00:47:41,570 --> 00:47:43,828
och du skulle bara
har din sorterad lista.

1126
00:47:43,828 --> 00:47:44,536
STUDENT: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
INSTRUKTÖR: Jag är ledsen?

1129
00:47:49,010 --> 00:47:52,110
STUDENT: Eftersom vi tidigare
används skrivit 1 över skriven noll

1130
00:47:52,110 --> 00:47:54,170
att presentera att om
det kommer att fungera eller inte.

1131
00:47:54,170 --> 00:47:54,878
>> INSTRUKTÖR: Ja.

1132
00:47:54,878 --> 00:47:56,410
Så du kan returnera noll eller 1.

1133
00:47:56,410 --> 00:47:58,950
I det här fallet, eftersom vi är faktiskt inte
gör något med funktionen,

1134
00:47:58,950 --> 00:48:00,150
Vi vill bara att det ska gå sönder.

1135
00:48:00,150 --> 00:48:02,680
Vi vet inte riktigt bryr sig om det.

1136
00:48:02,680 --> 00:48:06,960
Brake är också bra om
den används för att bryta ut

1137
00:48:06,960 --> 00:48:10,710
av fyra slingor eller villkor som
du inte vill behålla utföra.

1138
00:48:10,710 --> 00:48:12,110
Det tar bara dig ur dem.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Det är lite av en nyans sak.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Det känns som det finns
en hel del för hand vinka,

1143
00:48:18,445 --> 00:48:19,740
som du kommer att lära dig mer om detta snart.

1144
00:48:19,740 --> 00:48:20,955
>> Men du kommer att lära dig mer om detta snart.

1145
00:48:20,955 --> 00:48:21,500
Jag lovar.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
OK.

1148
00:48:23,170 --> 00:48:24,840
Så gör alla får bubbla sortera?

1149
00:48:24,840 --> 00:48:25,550
Inte så illa.

1150
00:48:25,550 --> 00:48:31,910
Iterera igenom, swap saker med en
temp variabel, och vi är allt klart där?

1151
00:48:31,910 --> 00:48:32,960
Cool.

1152
00:48:32,960 --> 00:48:34,080
Grymt.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Tillbaka till PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Eventuella frågor i allmänhet
om dessa så långt?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
Cool.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
Mm-hm.

1161
00:48:43,695 --> 00:48:45,279
>> STUDENTEN [OHÖRBAR] int main oftast.

1162
00:48:45,279 --> 00:48:46,695
Måste man ha det för detta?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> INSTRUKTÖR: Så vi bara ute
precis vid den faktiska sorteringsalgoritm.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Om du hade det inom
som ett större program,

1167
00:48:56,350 --> 00:48:57,891
du skulle ha en int main någonstans.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Beroende på var du
använda denna algoritm,

1170
00:49:02,880 --> 00:49:05,860
Det skulle avgöra vad som är
som returneras av den.

1171
00:49:05,860 --> 00:49:09,960
Men för vårt fall, vi är strikt
titta på hur fungerar det egentligen

1172
00:49:09,960 --> 00:49:11,300
iterera genom en matris.

1173
00:49:11,300 --> 00:49:12,570
Så vi behöver inte oroa dig för det.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Så vi pratade om bästa fall och
värsta tänkbara scenarier för binär sökning.

1176
00:49:19,830 --> 00:49:22,470
Så det är också viktigt att göra
att för var och en av våra slag.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Så vad tror du är det värsta
fall runtime bubbla slag?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Ni minns?

1181
00:49:30,700 --> 00:49:31,784
>> STUDENT: N minus 1.

1182
00:49:31,784 --> 00:49:32,700
INSTRUKTÖR: N minus 1.

1183
00:49:32,700 --> 00:49:35,070
Så det innebär att det finns
n minus 1 jämförelser.

1184
00:49:35,070 --> 00:49:40,060
Så en sak att inse är
att på den första iterationen,

1185
00:49:40,060 --> 00:49:43,360
vi går igenom, vi jämför
dessa two-- så det är 1.

1186
00:49:43,360 --> 00:49:46,685
Dessa två, tre, fyra.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Så efter en iteration vi
redan har fyra jämförelser.

1189
00:49:55,050 --> 00:49:58,230
När jag pratar om körtid och n.

1190
00:49:58,230 --> 00:50:04,680
N representerar antalet jämförelser
som en funktion av hur många element

1191
00:50:04,680 --> 00:50:05,570
vi har.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Så vi går igenom, vi har fyra.

1194
00:50:08,860 --> 00:50:11,780
Nästa gång du vet gör vi inte
måste ta hand om detta.

1195
00:50:11,780 --> 00:50:15,140
Vi jämför dessa två,
dessa två, dessa två,

1196
00:50:15,140 --> 00:50:20,050
och om vi inte hade att optimering
med fyra slinga som jag skrev,

1197
00:50:20,050 --> 00:50:22,750
du skulle jämföra in här ändå.

1198
00:50:22,750 --> 00:50:26,170
Så du skulle behöva
köra igenom arrayen

1199
00:50:26,170 --> 00:50:34,380
och göra N jämförelser n
gånger, eftersom varje gång vi

1200
00:50:34,380 --> 00:50:36,670
köra igenom det vi sorterar en sak.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> Och varje gång vi kör igenom
arrayen, vi gör n jämförelser.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Så vår runtime för detta är
faktiskt n kvadrat, vilket

1205
00:50:46,330 --> 00:50:48,400
är mycket värre i vår
log slutet eftersom det

1206
00:50:48,400 --> 00:50:51,965
innebär om vi hade fyra
miljarder element, det

1207
00:50:51,965 --> 00:50:55,260
kommer att ta oss fyra miljarder
kvadrat i stället för 32.

1208
00:50:55,260 --> 00:51:01,240
Så inte den bästa runtime,
men för vissa saker,

1209
00:51:01,240 --> 00:51:04,610
du vet, om du är inom
ett visst antal element

1210
00:51:04,610 --> 00:51:06,540
bubbla slag kan vara bra att använda.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Så nu vad är det bästa fallet runtime?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
STUDENTEN Zero?

1215
00:51:14,940 --> 00:51:16,420
Eller 1?

1216
00:51:16,420 --> 00:51:18,140
>> INSTRUKTÖR: So 1 skulle
vara en jämförelse.

1217
00:51:18,140 --> 00:51:19,114
Höger.

1218
00:51:19,114 --> 00:51:20,002
>> STUDENT: N minus 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> INSTRUKTÖR: Så, ja.

1221
00:51:22,320 --> 00:51:22,990
Så n minus 1.

1222
00:51:22,990 --> 00:51:26,510
När du har ett koncept som n
minus 1, tenderar vi att bara släppa det

1223
00:51:26,510 --> 00:51:31,680
och vi bara säga n för att du har
att jämföra var och en av these-- varje par.

1224
00:51:31,680 --> 00:51:36,470
Så det skulle vara n minus 1, som vi
Vi skulle bara vilja säga är ungefär n.

1225
00:51:36,470 --> 00:51:39,280
När du arbetar med runtime,
allt är i approximerar.

1226
00:51:39,280 --> 00:51:43,860
Så länge exponenten är
korrekt, du är ganska bra.

1227
00:51:43,860 --> 00:51:45,700
>> Det är hur vi hanterar den.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Så att det bästa fallet är n, vilken
innebär att listan redan är sorterad,

1230
00:51:51,780 --> 00:51:54,320
och allt vi gör drivs via
och kontrollera att den är sorterade.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
Cool.

1233
00:51:56,855 --> 00:51:57,355
Okej.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Så som ni ser här, vi
bara har några fler grafer.

1236
00:52:01,920 --> 00:52:02,660
Så n kvadrat.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
Fun.

1239
00:52:05,120 --> 00:52:09,730
Mycket värre än n som vi ser, och
mycket, mycket värre än log 2n.

1240
00:52:09,730 --> 00:52:12,060
Och då får du också in i logg stockar.

1241
00:52:12,060 --> 00:52:18,020
Och du tar 124, får du in
som log stjärnan, som är som galen.

1242
00:52:18,020 --> 00:52:20,172
Så om du är intresserad,
lookup log stjärna.

1243
00:52:20,172 --> 00:52:20,880
Det är ganska kul.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Så vi har denna stora diagrammet.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Bara en huvuden upp, detta är en
underbart diagrammet att ha

1248
00:52:28,720 --> 00:52:31,350
för din halva tiden eftersom vi
lång tid att ställa dig dessa tunnar.

1249
00:52:31,350 --> 00:52:36,090
Så bara en huvuden upp, har detta på din
halva tiden på din fina fusklapp

1250
00:52:36,090 --> 00:52:36,616
där.

1251
00:52:36,616 --> 00:52:37,990
Så vi bara tittade på bubblan slag.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
I värsta fall, n kvadrat, bästa fall, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
Och vi kommer att titta på de andra.

1256
00:52:44,950 --> 00:52:47,940
>> Och som ni kan se, den enda
en som verkligen gör bra

1257
00:52:47,940 --> 00:52:50,910
är merge sort, som vi kommer att få in på varför.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Så vi kommer att gå till
nästa här-- val slag.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Finns det någon som minns hur
urval sorterar fungerat?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Gå för det.

1264
00:53:05,700 --> 00:53:08,210
>> STUDENT: I ​​grund och botten gå igenom
en beställning och skapa en ny lista.

1265
00:53:08,210 --> 00:53:11,001
Och precis som du sätter element
i, lägg dem på rätt plats

1266
00:53:11,001 --> 00:53:11,750
i den nya listan.

1267
00:53:11,750 --> 00:53:14,040
>> INSTRUKTÖR: Så det låter
mer som inför slag.

1268
00:53:14,040 --> 00:53:15,040
Men du är riktigt nära.

1269
00:53:15,040 --> 00:53:15,915
De är mycket lika.

1270
00:53:15,915 --> 00:53:17,440
Även jag får dem blandas ihop ibland.

1271
00:53:17,440 --> 00:53:18,981
Innan detta avsnitt jag var som, vänta.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
OK.

1274
00:53:20,630 --> 00:53:24,141
Så vad du vill
do är urval sortera,

1275
00:53:24,141 --> 00:53:25,890
det sätt du kan tänka dig
om det och hur

1276
00:53:25,890 --> 00:53:30,140
Jag ser till att jag försöker att inte få
dem blandas ihop, är det går igenom

1277
00:53:30,140 --> 00:53:33,280
och väljer den
minsta antalet och det

1278
00:53:33,280 --> 00:53:36,070
sätter det i början av din lista.

1279
00:53:36,070 --> 00:53:37,730
Det byter det med den första platsen.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
De har faktiskt en förebild för mig.

1282
00:53:45,370 --> 00:53:46,540
Grymt.

1283
00:53:46,540 --> 00:53:50,130
Så bara ett sätt att tänka på det-- urval
sortera, välja det minsta värdet.

1284
00:53:50,130 --> 00:53:51,940
Och vi kommer att
köra igenom ett exempel

1285
00:53:51,940 --> 00:53:55,320
som jag tror kommer att hjälpa eftersom
Jag tror visuella alltid hjälpa.

1286
00:53:55,320 --> 00:53:58,510
Så vi börjar med något
som är helt osorterat.

1287
00:53:58,510 --> 00:54:00,730
Rött är osorterade,
gröna kommer att sorteras.

1288
00:54:00,730 --> 00:54:02,190
Det kommer allt vettigt i en sekund.

1289
00:54:02,190 --> 00:54:08,950
>> Så vi går igenom och vi iterera
från början till slut.

1290
00:54:08,950 --> 00:54:12,320
Och vi säger, OK, 2 är
vår minsta antalet.

1291
00:54:12,320 --> 00:54:15,680
Så vi kommer att ta två och vi kommer
att flytta den till framsidan av vår array

1292
00:54:15,680 --> 00:54:17,734
eftersom det är den
minsta antalet har vi.

1293
00:54:17,734 --> 00:54:19,150
Så det är vad det gör här.

1294
00:54:19,150 --> 00:54:20,820
Det är bara att byta dessa två.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Så nu har vi en sortering
del och en osorterad del.

1297
00:54:25,450 --> 00:54:27,810
Och vad som är bra att komma ihåg
om urval sorterar

1298
00:54:27,810 --> 00:54:30,690
är vi bara välja
från osorterade delen.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Den sorterade delen du bara lämna ensam.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> STUDENT: Hur fungerar det vet vad som är
de minsta utan att jämföra

1303
00:54:38,452 --> 00:54:39,868
till varje annat värde i arrayen.

1304
00:54:39,868 --> 00:54:41,250
INSTRUKTÖR: Det gör det jämföra det.

1305
00:54:41,250 --> 00:54:42,041
Vi gillar hoppade över det.

1306
00:54:42,041 --> 00:54:43,850
Detta är bara allmänt övergripande.

1307
00:54:43,850 --> 00:54:44,831
Yeah.

1308
00:54:44,831 --> 00:54:47,205
När vi skriver koden är jag
säker på att du kommer att bli mer nöjda.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Men du lagrar denna första
elementet som den minsta.

1311
00:54:53,030 --> 00:54:56,110
Du jämföra och du
säger, OK, det är mindre?

1312
00:54:56,110 --> 00:54:56,660
Ja.

1313
00:54:56,660 --> 00:54:57,460
Håll det.

1314
00:54:57,460 --> 00:54:58,640
Här är det mindre?

1315
00:54:58,640 --> 00:54:59,660
Nej?

1316
00:54:59,660 --> 00:55:02,510
>> Detta är din minsta,
tilldela den till ditt värde.

1317
00:55:02,510 --> 00:55:06,340
Och du kommer att bli mycket lyckligare
När vi går igenom koden.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Så vi går igenom, vi byta den, så då
vi ser på detta osorterade delen.

1320
00:55:13,970 --> 00:55:15,810
Så vi kommer att välja tre.

1321
00:55:15,810 --> 00:55:18,890
Vi kommer att sätta upp det på vid
I slutet av vår sorterade delen.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
Och vi ska bara fortsätta göra
att göra det, och göra det.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Så det här är vår typ av pseudokod här.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Vi ska koda upp det här på en sekund.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Men bara något att gå
igenom på en hög nivå.

1330
00:55:37,270 --> 00:55:40,275
Du kommer att gå från
i är lika med 0 till n minus 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
Det är en annan optimering.

1333
00:55:43,530 --> 00:55:45,020
Oroa dig inte för mycket om det.

1334
00:55:45,020 --> 00:55:46,620
Så som ni sa.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Som Jakob sa, hur gör vi
hålla reda på vad vår minsta är?

1337
00:55:54,406 --> 00:55:55,030
Hur vet vi det?

1338
00:55:55,030 --> 00:55:57,060
Vi måste jämföra
allt i vår lista.

1339
00:55:57,060 --> 00:55:59,600
>> Så minimum är lika i.

1340
00:55:59,600 --> 00:56:03,870
Det är bara att säga i det här fallet
index för vår minsta värde.

1341
00:56:03,870 --> 00:56:07,660
Så då det kommer att iterera igenom
och det går från j är lika med i plus 1.

1342
00:56:07,660 --> 00:56:11,420
Så vi vet redan att
det är vår första elementet.

1343
00:56:11,420 --> 00:56:13,240
Vi behöver inte jämföra det med sig själv.

1344
00:56:13,240 --> 00:56:16,970
Så vi börjar jämföra det till nästa
en som är varför det är i plus 1 till n

1345
00:56:16,970 --> 00:56:20,110
minus 1, vilket är den
slutet av arrayen där.

1346
00:56:20,110 --> 00:56:25,090
Och vi sa att om array på
j är mindre än array min,

1347
00:56:25,090 --> 00:56:29,200
sedan omtilldela vi där
våra lägsta index är.

1348
00:56:29,200 --> 00:56:37,470
>> Och om min är inte lika med I, såsom
i där vi var tillbaka hit.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Så som när vi först gjorde detta.

1351
00:56:41,790 --> 00:56:49,310
I detta fall skulle det börja på
noll, skulle det hamna två.

1352
00:56:49,310 --> 00:56:53,010
Så min skulle inte lika i till slut.

1353
00:56:53,010 --> 00:56:55,720
Det låter oss veta att
vi behöver byta dem.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Jag känner mig som ett konkret exempel
kommer att bidra mycket mer än detta.

1356
00:57:00,470 --> 00:57:04,970
Så jag ska koda upp detta med er
just nu och jag tror det blir bättre.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Sorterar tenderar att arbeta på det sättet i det
Det är ofta bättre bara för att se dem.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Så vad vi vill göra är att
vi först vill ha den minsta

1361
00:57:17,280 --> 00:57:19,890
element i sin position i arrayen.

1362
00:57:19,890 --> 00:57:21,280
Exakt vad Jakob sade.

1363
00:57:21,280 --> 00:57:23,090
Du måste lagra den på något sätt.

1364
00:57:23,090 --> 00:57:25,900
Så vi kommer att börja här
iteration över arrayen.

1365
00:57:25,900 --> 00:57:28,970
Vi kommer att säga att det är vår
första bara för att börja med.

1366
00:57:28,970 --> 00:57:38,308
Så vi kommer att ha int
minsta är lika med array på i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Så en sak att lägga märke till, varje
tid denna slinga exekverar,

1369
00:57:45,050 --> 00:57:48,550
Vi börjar ett steg längre fram.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
När vi börjar vi tittar på detta.

1372
00:57:57,440 --> 00:58:00,840
Nästa gång vi iterera igenom,
vi börjar på den här

1373
00:58:00,840 --> 00:58:02,680
och tilldela det vår minsta värde.

1374
00:58:02,680 --> 00:58:10,450
Så det är mycket lik bubbla sortera
där vi vet att efter ett pass,

1375
00:58:10,450 --> 00:58:11,700
denna sista elementet sorteras.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Med valet sortera,
Det är precis tvärtom.

1378
00:58:15,120 --> 00:58:18,950
>> Vid varje pass, vet vi att
den första sorteras.

1379
00:58:18,950 --> 00:58:21,360
Efter det andra passet, det
andra kommer att sorteras.

1380
00:58:21,360 --> 00:58:26,470
Och som du såg med glid exemplen,
våra sorterade delen blir bara växer.

1381
00:58:26,470 --> 00:58:34,020
Så genom att sätta vår minsta
till arrayer i, allt det gör

1382
00:58:34,020 --> 00:58:37,340
är bromsande vad
vi tittar på så

1383
00:58:37,340 --> 00:58:40,164
för att minimera antalet
jämförelser vi gör.

1384
00:58:40,164 --> 00:58:41,770
Betyder det vettigt för alla?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Vill du att jag ska gå igenom det
åter långsammare eller i olika ord?

1387
00:58:46,380 --> 00:58:47,180
Jag är glad att.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
OK.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Så vi förvarar
värde vid denna punkt,

1392
00:58:55,540 --> 00:58:57,840
men vi vill också lagra index.

1393
00:58:57,840 --> 00:59:01,010
Så vi kommer att lagra
positionen för det minsta

1394
00:59:01,010 --> 00:59:02,770
en, som just kommer att vara i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Så nu Jacob är uppfyllt.

1397
00:59:05,440 --> 00:59:06,870
Vi har saker som lagras.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
Och nu måste vi titta igenom
den osorterade del av matrisen.

1400
00:59:11,870 --> 00:59:18,170
Så i detta fall
skulle vara vår osorterat.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Detta är i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Så vad vi ska göra
kommer att vara för en slinga.

1406
00:59:30,040 --> 00:59:32,066
Närhelst du behöver
iterera genom en matris,

1407
00:59:32,066 --> 00:59:33,440
ditt sinne kunde gå till för en slinga.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Så för vissa int k
equals-- vad vi tänker

1410
00:59:38,090 --> 00:59:39,700
k kommer att vara lika till att börja med?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Detta är vad vi satt som vår minsta
värde och vi vill jämföra den.

1413
00:59:44,766 --> 00:59:47,090
Vad vill vi jämföra det med?

1414
00:59:47,090 --> 00:59:48,730
Det kommer att vara så här nästa, eller hur?

1415
00:59:48,730 --> 00:59:53,200
Så vi vill k initieras
till i plus 1 för att starta.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> Och vi vill ha k vi i detta fall
redan har storlek lagrat upp här,

1418
01:00:02,800 --> 01:00:03,930
så vi kan bara använda storlek.

1419
01:00:03,930 --> 01:00:06,240
Storlek att vara storleken på matrisen.

1420
01:00:06,240 --> 01:00:09,620
Och vi bara vill
uppdatera k med ett varje gång.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Cool.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Så nu måste vi hitta
det minsta elementet här.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Så om vi iterera igenom, vi
vill säga, om array på k

1427
01:00:31,380 --> 01:00:37,080
är mindre än vår minsta value--
det är där vi faktiskt

1428
01:00:37,080 --> 01:00:42,950
hålla reda på vad som är
den minsta här--

1429
01:00:42,950 --> 01:00:47,740
då vill vi att omplacera
vad vår minsta värdet är.

1430
01:00:47,740 --> 01:00:50,645
>> Detta innebär att, åh, vi är
iterera igenom här.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Oavsett värdet här är
inte vårt minsta sak.

1433
01:00:53,740 --> 01:00:54,448
Vi vill inte ha det.

1434
01:00:54,448 --> 01:00:56,100
Vi vill dela ut det.

1435
01:00:56,100 --> 01:01:02,050
Så om vi omplacera den, vad gör
du tror kan vara i denna kod här?

1436
01:01:02,050 --> 01:01:04,160
Vi vill tilldela
minsta och placering.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Så vad är minsta nu?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
STUDENTEN Array k.

1441
01:01:09,130 --> 01:01:09,963
INSTRUKTÖR: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
Och vad är läget nu?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Vad är de index i
vår minsta värde?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
Det är bara k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Så array k, k, matchar de upp.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Så vi ville att omplacera det.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
Och sedan när vi hittat vår minsta,
så vid slutet av denna för slingan

1454
01:01:39,950 --> 01:01:45,100
här har vi hittat vad vår minsta
värdet är, så vi bara byta den.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
I detta fall, liksom säga vår
minsta värdet är här ute.

1457
01:01:50,816 --> 01:01:51,940
Detta är vår minsta värde.

1458
01:01:51,940 --> 01:01:57,690
>> Vi vill bara byta den här, som är
vad det swap-funktion i botten

1459
01:01:57,690 --> 01:02:01,270
gjorde, som vi just skrev upp
ihop ett par minuter sedan.

1460
01:02:01,270 --> 01:02:02,775
Så det ska se bekanta.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
Och då kommer det bara iterera
igenom tills den når hela vägen

1463
01:02:08,030 --> 01:02:13,100
till slutet, vilket innebär att du
har noll element som osorterade

1464
01:02:13,100 --> 01:02:14,800
och allt annat har sorterats.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Vettigt?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Lite mer konkret?

1469
01:02:19,280 --> 01:02:19,990
Koden hjälp?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> STUDENT: För en storlek, du aldrig
verkligen definiera det eller ändra det,

1472
01:02:26,410 --> 01:02:27,340
hur går det vet?

1473
01:02:27,340 --> 01:02:32,380
>> INSTRUKTÖR: Så en sak till
märker upp här är int storlek.

1474
01:02:32,380 --> 01:02:35,680
Så vi säger i denna sort-- sort
är en funktion i det här case-- det är

1475
01:02:35,680 --> 01:02:40,770
val sortera, det passerade
in med funktionen.

1476
01:02:40,770 --> 01:02:43,460
Så om det inte skickades
in, skulle du göra något

1477
01:02:43,460 --> 01:02:47,840
liknande med längden av uppsättningen
eller skulle du iterera igenom

1478
01:02:47,840 --> 01:02:49,390
att hitta längden.

1479
01:02:49,390 --> 01:02:52,680
Men eftersom det är passerat
i, kan vi bara använda den.

1480
01:02:52,680 --> 01:02:55,720
Du tar bara att användaren
gav dig en giltig storlek som

1481
01:02:55,720 --> 01:02:57,698
faktiskt representerar
en storlek på din array.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
Cool?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Om ni har några problem med dessa
eller vill ha mer praxis kodning sorterar

1486
01:03:05,870 --> 01:03:08,050
på egen hand, bör du
gå till study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Det är ett verktyg.

1489
01:03:12,670 --> 01:03:15,040
De har en pjäs som
Du kan faktiskt skriva.

1490
01:03:15,040 --> 01:03:16,180
De gör pseudokod.

1491
01:03:16,180 --> 01:03:19,310
De har fler videor och diabilder
inklusive de som jag använder här.

1492
01:03:19,310 --> 01:03:23,150
Så om du fortfarande känner dig
lite luddigt, prova att.

1493
01:03:23,150 --> 01:03:25,670
Som alltid, kom prata med mig också.

1494
01:03:25,670 --> 01:03:26,320
Fråga?

1495
01:03:26,320 --> 01:03:28,611
>> STUDENT: Säger du det
Storleken är som tidigare definierats?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
INSTRUKTÖR: Ja.

1498
01:03:29,900 --> 01:03:35,570
Storleken tidigare definierats upp
här i funktionsdeklarationen.

1499
01:03:35,570 --> 01:03:39,060
Så du antar att det har gått i
av användaren, och för enkelhets skull,

1500
01:03:39,060 --> 01:03:41,896
vi kommer att anta att
Användaren gav oss rätt storlek.

1501
01:03:41,896 --> 01:03:43,240
Cool.

1502
01:03:43,240 --> 01:03:44,390
Så det är val slag.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Killar, jag vet att vi lär oss en hel dag.

1505
01:03:47,640 --> 01:03:49,710
Det är en tät uppgifter för avdelning.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Så med detta kommer vi
för att gå till insättnings sort.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> OK.

1510
01:04:02,510 --> 01:04:06,100
Så innan vi måste göra
vår runtime analys här.

1511
01:04:06,100 --> 01:04:10,190
Så i bästa fall
beviljats ​​sedan jag visade dig

1512
01:04:10,190 --> 01:04:11,960
tabellen jag redan
slags gav det bort.

1513
01:04:11,960 --> 01:04:15,430
Men bästa fall runtime, vad tror vi?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Allt sorteras.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N i kvadrat.

1518
01:04:22,070 --> 01:04:24,780
Någon har en förklaring
för varför du tror?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> STUDENT: Du jämföra through--

1521
01:04:30,519 --> 01:04:31,268
INSTRUKTÖR: Rätt.

1522
01:04:31,268 --> 01:04:32,540
Du jämför igenom.

1523
01:04:32,540 --> 01:04:35,630
Vid varje iteration, trots att
vi nedräkning detta efter en,

1524
01:04:35,630 --> 01:04:38,950
du fortfarande söka igenom
allt för att hitta den minsta.

1525
01:04:38,950 --> 01:04:42,390
Så även om din minsta värde
är här i början,

1526
01:04:42,390 --> 01:04:44,710
du fortfarande jämföra det
mot allt annat

1527
01:04:44,710 --> 01:04:46,550
att se till att det är det minsta.

1528
01:04:46,550 --> 01:04:49,820
Så du kommer att sluta som löper genom
ca n kvadrat gånger.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Okej.

1531
01:04:51,590 --> 01:04:52,785
Och vad är det värsta?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Också n kvadrat eftersom du kommer
att göra det samma procedur.

1534
01:04:57,980 --> 01:05:01,670
Så i detta fall, val
sortera har något

1535
01:05:01,670 --> 01:05:04,010
som vi kallar också förväntade runtime.

1536
01:05:04,010 --> 01:05:07,400
Så i de andra, vi vet bara
de övre och undre gränser.

1537
01:05:07,400 --> 01:05:11,180
Beroende på hur galen vår
Listan är eller hur osorterat det är,

1538
01:05:11,180 --> 01:05:15,350
de varierar mellan n eller n kvadrat.

1539
01:05:15,350 --> 01:05:16,550
Vi vet inte.

1540
01:05:16,550 --> 01:05:22,820
>> Men eftersom valet sort har samma
värsta och bästa fall, berättar att för oss att

1541
01:05:22,820 --> 01:05:25,880
oavsett vilken typ av input vi
ha, oavsett om det är helt

1542
01:05:25,880 --> 01:05:29,130
sorterat eller fullständigt
vända sorteras, det är

1543
01:05:29,130 --> 01:05:30,740
kommer att ta lika lång tid.

1544
01:05:30,740 --> 01:05:33,760
Så i så fall, om du
minns från vårt bord,

1545
01:05:33,760 --> 01:05:38,610
det faktiskt hade ett värde som
dessa två typer har inte,

1546
01:05:38,610 --> 01:05:40,390
vilket är förväntat runtime.

1547
01:05:40,390 --> 01:05:43,350
Så vi vet att när
Vi kör val sortera,

1548
01:05:43,350 --> 01:05:45,380
det är garanterat
köra en n kvadrerade tid.

1549
01:05:45,380 --> 01:05:46,630
Det finns ingen variation där.

1550
01:05:46,630 --> 01:05:47,630
Det är bara väntat.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
Och, återigen, om du vill lära dig
mer, ta CS 124 under våren.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Okej.

1555
01:05:56,712 --> 01:05:57,545
Vi har sett den här.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Cool.

1558
01:05:59,030 --> 01:06:00,930
Så insättnings slag.

1559
01:06:00,930 --> 01:06:03,330
Och jag kommer nog
att flamma igenom detta.

1560
01:06:03,330 --> 01:06:05,440
Jag kommer inte att ha er koda den.

1561
01:06:05,440 --> 01:06:06,580
Vi ska bara gå igenom det.

1562
01:06:06,580 --> 01:06:10,500
Så insättnings slag är snäll
av liknande val Sortera

1563
01:06:10,500 --> 01:06:14,460
i att vi har både en osorterad
och sorteras del av matrisen.

1564
01:06:14,460 --> 01:06:20,260
>> Men vad är annorlunda är att
när vi går igenom en efter en,

1565
01:06:20,260 --> 01:06:24,210
vi bara ta de nummer
är nästa i vår osorterade,

1566
01:06:24,210 --> 01:06:28,507
och korrekt sortera
in i vår sorterade arrayen.

1567
01:06:28,507 --> 01:06:30,090
Det kommer att vara bättre med ett exempel.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Så allt börjar som osorterat,
precis som med val slag.

1570
01:06:35,430 --> 01:06:38,740
Och vi kommer att lösa detta på
stigande ordning som vi har varit.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Så på vår första passet
Vi tar det första värdet

1573
01:06:43,340 --> 01:06:46,700
och vi säger, OK, du är
nu i en lista själv.

1574
01:06:46,700 --> 01:06:49,150
>> Eftersom du är i en lista
själv, du är sorterade.

1575
01:06:49,150 --> 01:06:52,460
Grattis för att vara
första elementet i arrayen.

1576
01:06:52,460 --> 01:06:54,800
Du är redan sorterade allt på egen hand.

1577
01:06:54,800 --> 01:06:58,900
Så nu har vi en sortering
och en osorterad array.

1578
01:06:58,900 --> 01:07:01,760
Så nu tar vi det första.

1579
01:07:01,760 --> 01:07:05,600
Vad händer mellan här
och här är det vi säger,

1580
01:07:05,600 --> 01:07:08,890
OK, vi kommer att titta på
första värdet av vår osorterade array

1581
01:07:08,890 --> 01:07:13,270
och vi kommer att mata in den i dess
rätt ställe i den sorterade arrayen.

1582
01:07:13,270 --> 01:07:21,460
>> Så vad vi gör är tar vi 5 och
vi säger, OK, 5 är större än 3,

1583
01:07:21,460 --> 01:07:24,630
så vi bara sätta in den rätt
till höger om denna.

1584
01:07:24,630 --> 01:07:25,130
Vi är bra.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Så då går vi vidare till vår nästa.

1587
01:07:28,420 --> 01:07:29,720
Och vi tar 2.

1588
01:07:29,720 --> 01:07:34,330
Vi säger, OK, 2 är mindre
än 3, så vi vet att det

1589
01:07:34,330 --> 01:07:36,220
behöver vara vid
framför vår lista nu.

1590
01:07:36,220 --> 01:07:41,800
Så vad vi gör är att vi trycker 3 och 5 ner
och vi går 2 i det första facket.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Så vi bara sätter in det i
rätt plats det ska vara.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Då vi tittar på vår
nästa en, och vi säger 6.

1595
01:07:49,470 --> 01:07:53,620
OK, är 6 större än
allt i vårt sorterade arrayen,

1596
01:07:53,620 --> 01:07:56,000
så vi bara tagga det till slutet.

1597
01:07:56,000 --> 01:07:56,960
Och så tittar vi på 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 är mindre än 6, är det mindre
än 5 men det är större än 3.

1600
01:08:03,020 --> 01:08:06,270
Så vi bara sätta in den rätt in
mitten mellan 3 och 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Så för att göra det lite
lite mer konkret,

1603
01:08:10,530 --> 01:08:12,280
här är typ av
uppfattning om vad som hände.

1604
01:08:12,280 --> 01:08:16,430
Så för varje osorterade element, vi
bestämma var i den sorterade delen

1605
01:08:16,430 --> 01:08:17,090
det är.

1606
01:08:17,090 --> 01:08:20,680
>> Så med tanke på
sorterade och osorterade,

1607
01:08:20,680 --> 01:08:26,080
vi har att passera genom och figur
på var den passar i den sorterade arrayen.

1608
01:08:26,080 --> 01:08:31,460
Och vi för in den genom att flytta
element till höger om den.

1609
01:08:31,460 --> 01:08:34,910
Och då är vi bara hålla
iterera igenom tills vi

1610
01:08:34,910 --> 01:08:39,270
ha en helt sorterade listan
där osorterade nu är noll

1611
01:08:39,270 --> 01:08:41,720
och sorterade tar upp
helhet på vår lista.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Så, återigen, att göra saker ännu
mer konkret, vi har pseudokod.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Så i princip för i är
lika med 0 till n minus 1,

1616
01:08:52,410 --> 01:08:54,790
det är bara längden på vår array.

1617
01:08:54,790 --> 01:09:00,979
Vi har en del inslag som är lika med
den första uppsättningen eller de första indexen.

1618
01:09:00,979 --> 01:09:03,200
Vi sätter j lika med den.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Så medan j är större än
noll och matrisen, j minus ett

1621
01:09:09,210 --> 01:09:11,660
är större än den
element, så allt som gör

1622
01:09:11,660 --> 01:09:17,479
är att se till att
din j verkligen representerar

1623
01:09:17,479 --> 01:09:20,010
den osorterade delen av matrisen.

1624
01:09:20,010 --> 01:09:30,745
>> Så medan det finns fortfarande saker
att sortera och j minus ett är-- vad

1625
01:09:30,745 --> 01:09:31,840
är elementet henne?

1626
01:09:31,840 --> 01:09:34,760
J var aldrig definieras här.

1627
01:09:34,760 --> 01:09:35,677
Det är typ av irriterande.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Anyways.

1630
01:09:36,689 --> 01:09:39,899
Så j minus 1, du kontrollerar
elementet innan det.

1631
01:09:39,899 --> 01:09:46,460
Du säger, OK, är elementet
innan vart jag am-- låt oss

1632
01:09:46,460 --> 01:09:47,540
faktiskt dra ut denna.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Så låt oss säga att detta är
som på våra andra passet.

1635
01:09:56,830 --> 01:09:59,525
Så jag kommer att vara lika
till 1, vilket är här.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Så jag kommer att vara lika med 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
Detta skulle vara 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Okej.

1642
01:10:16,750 --> 01:10:20,945
Så vår del i detta ärende
kommer att vara lika med 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
Och vi har några j som är
kommer att vara lika med ett.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Åh, är j nedräkning.

1647
01:10:30,971 --> 01:10:31,720
Det är vad det är.

1648
01:10:31,720 --> 01:10:35,680
Så j är lika med i, så vad det här är
säger är att när vi går framåt,

1649
01:10:35,680 --> 01:10:37,530
vi bara att se
att vi inte är över

1650
01:10:37,530 --> 01:10:43,520
indexera det här sättet när vi försöker
att sätta saker i vår sorterade listan.

1651
01:10:43,520 --> 01:10:49,850
>> Så när j är lika med 1 i detta fall och
array j minus en-- så array j minus 1

1652
01:10:49,850 --> 01:10:54,610
är 2 i denna case-- om det är
som är större än elementets,

1653
01:10:54,610 --> 01:10:57,700
då allt detta gör
skiftar ner saker.

1654
01:10:57,700 --> 01:11:04,790
Så i detta fall, array j minus ett
vore array noll, vilket är 2.

1655
01:11:04,790 --> 01:11:08,430
2 inte är större än 4,
så detta inte köra.

1656
01:11:08,430 --> 01:11:11,460
Så övergången inte rör sig nedåt.

1657
01:11:11,460 --> 01:11:18,790
Vad detta innebär här är bara
flytta din sorterade arrayen ner.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
I det här fallet, faktiskt, vi
kunde do-- låt oss göra detta 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Så om vi ska gå igenom med
Detta exempel är vi nu här.

1662
01:11:31,970 --> 01:11:32,740
Detta är sorterad.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Detta är osorterade.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Cool?

1667
01:11:39,860 --> 01:11:46,620
Så i är lika med 2, så
vår del är lika med 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
Och vår j är lika med 2.

1670
01:11:52,270 --> 01:12:00,620
Så vi tittar igenom och vi
säger, OK, är array j minus en

1671
01:12:00,620 --> 01:12:03,470
större än elementet
att vi tittar på?

1672
01:12:03,470 --> 01:12:05,540
Och svaret är ja, hur?

1673
01:12:05,540 --> 01:12:11,275
4 är större än 3 och j
är 2, så den här koden körs.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Så nu vad vi gör en matris på
2, så just här, vi byta dem.

1676
01:12:18,550 --> 01:12:25,620
Så vi bara säga, OK, array
vid 2 kommer nu att bli 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
Och j kommer att vara lika
j minus 1, vilket är ett.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
Det är hemskt, men
ni får idén.

1681
01:12:37,200 --> 01:12:38,360
J är nu lika med 1.

1682
01:12:38,360 --> 01:12:44,360
Och array j bara kommer att bli
lika med vår del, vilket var 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
Jag raderade något jag inte borde
har eller miswrote något,

1685
01:12:48,570 --> 01:12:49,910
men ni förstår tanken.

1686
01:12:49,910 --> 01:12:50,640
>> Det rör sig med n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
Och sedan om det fanns, skulle det loop
igen och det skulle säga, OK, är j 1 nu.

1689
01:12:57,960 --> 01:13:00,665
Och array j minus 1 är nu 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Är 2 mindre än vår del?

1692
01:13:03,760 --> 01:13:04,540
Nej?

1693
01:13:04,540 --> 01:13:07,970
Det innebär att vi har
insatt detta element

1694
01:13:07,970 --> 01:13:10,110
på rätt plats i vårt sorterade arrayen.

1695
01:13:10,110 --> 01:13:14,400
Då kan vi ta detta och vi säger,
OK, är vår sorterade arrayen här.

1696
01:13:14,400 --> 01:13:19,940
Och det skulle ta detta nummer 6 och vara
liknande, OK, är 6 färre än detta antal?

1697
01:13:19,940 --> 01:13:20,480
Nej?

1698
01:13:20,480 --> 01:13:21,080
Cool.

1699
01:13:21,080 --> 01:13:22,680
Vi är bra.

1700
01:13:22,680 --> 01:13:23,530
>> Gör det igen.

1701
01:13:23,530 --> 01:13:24,740
Vi säger 7.

1702
01:13:24,740 --> 01:13:29,010
Är 7 färre än i slutet
av våra sorterade arrayen?

1703
01:13:29,010 --> 01:13:29,520
Nej.

1704
01:13:29,520 --> 01:13:30,430
Så vi är bra.

1705
01:13:30,430 --> 01:13:32,760
Så detta skulle sorteras.

1706
01:13:32,760 --> 01:13:38,610
I princip allt detta gör
det säger take

1707
01:13:38,610 --> 01:13:42,060
den första delen av
din osorterat array,

1708
01:13:42,060 --> 01:13:46,010
räkna ut var det går
i ditt sorterade arrayen.

1709
01:13:46,010 --> 01:13:48,780
Och detta bara tar hand
av swappar för att göra det.

1710
01:13:48,780 --> 01:13:51,300
Du är i princip bara byta
tills det är på rätt plats.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Den visuella bilden är att du är
flytta ned allt genom att göra det.

1713
01:13:56,990 --> 01:13:59,420
>> Så det är som en halv bubbla sort-esque.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Kolla undersökning 50.

1716
01:14:03,420 --> 01:14:06,000
Jag rekommenderar starkt försöker
att koda detta på egen hand.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Om du har några frågor eller om du vill
se exempelkod för en insättnings sortera,

1719
01:14:12,450 --> 01:14:13,750
låt mig veta.

1720
01:14:13,750 --> 01:14:14,500
Jag är alltid runt.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Så värsta fall runtime
och bästa fall runtime.

1723
01:14:20,200 --> 01:14:30,700
Som ni killen såg från bordet jag redan
visade dig, det är både n kvadrat och n.

1724
01:14:30,700 --> 01:14:35,590
>> Så snäll att gå ut med vad vi pratade
om med våra tidigare slag, värst

1725
01:14:35,590 --> 01:14:38,760
fall runtime är att om
det är helt osorterade,

1726
01:14:38,760 --> 01:14:42,530
vi har att jämföra alla dessa n gånger.

1727
01:14:42,530 --> 01:14:47,020
Vi gör en hel del jämförelser
eftersom om det är i omvänd ordning,

1728
01:14:47,020 --> 01:14:50,360
vi ska säga, OK, detta
är densamma, är det bra,

1729
01:14:50,360 --> 01:14:54,650
och här måste jämföras
mot den första en att flyttas tillbaka.

1730
01:14:54,650 --> 01:14:56,710
Och när vi får in mot
svansen slutet, vi har

1731
01:14:56,710 --> 01:14:59,440
att jämföra, jämföra och
jämföra mot allt.

1732
01:14:59,440 --> 01:15:03,030
>> Så det slutar som
ungefär n kvadrat.

1733
01:15:03,030 --> 01:15:09,510
Om det stämmer så har du
säger, OK, 2, du är bra.

1734
01:15:09,510 --> 01:15:11,330
3, du är jämfört med 2.

1735
01:15:11,330 --> 01:15:12,310
Du är bra.

1736
01:15:12,310 --> 01:15:14,150
4, du bara jämför med svansen.

1737
01:15:14,150 --> 01:15:14,990
Du är bra.

1738
01:15:14,990 --> 01:15:17,140
6, jämför med svansen, du är bra.

1739
01:15:17,140 --> 01:15:20,870
Så för varje plats om det redan
sorterade, du gjorde en jämförelse.

1740
01:15:20,870 --> 01:15:22,320
Så det är bara n.

1741
01:15:22,320 --> 01:15:26,840
Och eftersom vi har en bästa fall runtime
n och ett värsta runtime n

1742
01:15:26,840 --> 01:15:28,680
kvadrat, har vi ingen förväntad körtid.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Det beror bara på
kaos på vår lista där.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
Och återigen, en annan
graf och en annan tabell.

1747
01:15:39,530 --> 01:15:41,170
Så skillnader mellan sorter.

1748
01:15:41,170 --> 01:15:44,180
Jag kommer bara att knäppa genom, jag
känns som vi har pratat utför

1749
01:15:44,180 --> 01:15:46,570
om hur de alla typer
av att variera och länka samman.

1750
01:15:46,570 --> 01:15:50,564
Så Merge sort är den sista
Jag ska tråka ut er med.

1751
01:15:50,564 --> 01:15:52,105
Vi har en ganska färgstark bild.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Så samman slag är en rekursiv algoritm.

1754
01:15:56,040 --> 01:15:59,910
Så gör ni vet vad
en rekursiv funktion är?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Någon vill säga?

1757
01:16:03,320 --> 01:16:04,739
Vill du prova?

1758
01:16:04,739 --> 01:16:07,280
Så en rekursiv funktion är bara
en funktion som kallar sig.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Så om ni känner
med Fibonacci-sekvensen,

1761
01:16:11,590 --> 01:16:15,670
som har bedömts rekursiv eftersom
du tar de två föregående

1762
01:16:15,670 --> 01:16:17,530
och lägga ihop dem
att få din nästa.

1763
01:16:17,530 --> 01:16:21,440
Så rekursiv, tror jag alltid
av rekursion som likt en spiral

1764
01:16:21,440 --> 01:16:24,430
så du är som spiral ner i den.

1765
01:16:24,430 --> 01:16:27,150
Men det är bara en funktion
som kallar sig.

1766
01:16:27,150 --> 01:16:32,660
>> Och, faktiskt, riktigt snabbt jag
kan visa dig vad som ser ut som.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Så rekursiv här, om vi ser, är detta
den rekursiva sättet att summera över en array.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Så allt vi gör är
Vi har sum funktion

1771
01:16:47,880 --> 01:16:52,210
summa som tar en storlek och en array.

1772
01:16:52,210 --> 01:16:55,210
Och om du märker, storlek
minskningar av en varje gång.

1773
01:16:55,210 --> 01:17:00,365
Och allt det gör är om x är lika med
zero-- så om storleken på matrisen

1774
01:17:00,365 --> 01:17:02,710
är lika med zero-- den returnerar noll.

1775
01:17:02,710 --> 01:17:10,440
>> Annars summerar detta
sista elementet i arrayen,

1776
01:17:10,440 --> 01:17:14,790
och sedan tar en summa
resten av matrisen.

1777
01:17:14,790 --> 01:17:17,555
Så det är bara att bryta ner
i mindre och mindre problem.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Lång historia kort, rekursion,
funktion som kallar sig.

1780
01:17:21,890 --> 01:17:25,740
Om det är allt du fick ut av detta,
det är vad en rekursiv funktion är.

1781
01:17:25,740 --> 01:17:29,870
Om du tar 51, du kommer att få mycket,
mycket bekväma med rekursion.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Det är verkligen häftigt.

1784
01:17:32,370 --> 01:17:34,660
Det var meningsfullt på liknande
03:00 en natt.

1785
01:17:34,660 --> 01:17:37,900
Och jag var som, varför
har jag aldrig detta?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Så för merge sort, i princip
Vad det kommer att göra är att det är

1788
01:17:42,430 --> 01:17:45,620
kommer att bryta ner det och bryta
ner tills det är bara enskilda element.

1789
01:17:45,620 --> 01:17:47,570
De enskilda delarna är lätta att sortera.

1790
01:17:47,570 --> 01:17:48,070
Vi ser att.

1791
01:17:48,070 --> 01:17:50,760
Om du har en del, det är
redan som sorteras.

1792
01:17:50,760 --> 01:17:53,800
Så på en ingång av n element,
om n är mindre än 2,

1793
01:17:53,800 --> 01:17:58,120
bara tillbaka eftersom det betyder
det är antingen 0 eller 1 som vi har sett.

1794
01:17:58,120 --> 01:18:00,050
De som anses sorterade element.

1795
01:18:00,050 --> 01:18:02,170
>> Annars bryter den på mitten.

1796
01:18:02,170 --> 01:18:06,336
Sortera första halvlek, sortera den andra
hälften, och sedan sammanfoga dem tillsammans.

1797
01:18:06,336 --> 01:18:07,460
Varför det kallas merge sort.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Så vi har här vi ska sortera dessa.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Så vi fortsätter att ha dem
tills matrisstorlek är 1.

1802
01:18:17,210 --> 01:18:20,790
Så när det är 1, vi bara tillbaka
eftersom detta är en sorterad array,

1803
01:18:20,790 --> 01:18:23,940
och detta är en sorterad array, och det är
en sorterad array, vi alla sorterade.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Så vad vi gör är att vi
börja slå samman dem tillsammans.

1806
01:18:29,420 --> 01:18:31,820
>> Så hur kan du
tycker om sammanslagning är

1807
01:18:31,820 --> 01:18:36,240
du bara ta bort den mindre
antal av vardera av underuppsättningar

1808
01:18:36,240 --> 01:18:38,330
och bara lägga den till framkommit arrayen.

1809
01:18:38,330 --> 01:18:44,290
Så om du tittar här, när vi har
dessa uppsättningar vi har 4, 6 och 1.

1810
01:18:44,290 --> 01:18:47,280
När vi vill sammanfoga dessa,
vi tittar på dessa två första

1811
01:18:47,280 --> 01:18:50,730
och vi säger, OK, 1 är mindre,
Det går till fronten.

1812
01:18:50,730 --> 01:18:54,330
4 och 6, det finns inget att jämföra
det, bara tagga den på till slutet.

1813
01:18:54,330 --> 01:18:58,020
>> När vi kombinerar dessa två, vi bara
ta den mindre en av dessa två,

1814
01:18:58,020 --> 01:18:59,310
så det är 1.

1815
01:18:59,310 --> 01:19:01,690
Och nu tar vi
mindre av dessa två, så 2.

1816
01:19:01,690 --> 01:19:03,330
Mindre av dessa två, 3.

1817
01:19:03,330 --> 01:19:06,260
Mindre av dessa två, fyra, fem, sex.

1818
01:19:06,260 --> 01:19:08,630
Så du bara dra av dessa.

1819
01:19:08,630 --> 01:19:11,210
Och eftersom de har
sorterats tidigare,

1820
01:19:11,210 --> 01:19:14,300
Du har bara en
Jämförelsen varje gång.

1821
01:19:14,300 --> 01:19:19,610
Så mer kod här, bara representation.

1822
01:19:19,610 --> 01:19:24,410
Så du börjar på mitten och
du sorterar vänster och höger

1823
01:19:24,410 --> 01:19:26,180
och då du bara slå ihop dem.

1824
01:19:26,180 --> 01:19:30,080
>> Och vi har inte kod
för samman just här.

1825
01:19:30,080 --> 01:19:34,110
Men, återigen, om du går på
studera 50, det ska vara där.

1826
01:19:34,110 --> 01:19:36,860
Annars kommer prata med mig
om du fortfarande förvirrad.

1827
01:19:36,860 --> 01:19:42,340
Så cool sak här är att i bästa fall,
värsta fall, och förväntade runtime

1828
01:19:42,340 --> 01:19:46,250
är alla i log n, vilken
är mycket bättre än vi har

1829
01:19:46,250 --> 01:19:48,000
sett för resten av våra slag.

1830
01:19:48,000 --> 01:19:51,840
Vi har sett n kvadrat
och vad vi faktiskt

1831
01:19:51,840 --> 01:19:54,380
ta sig hit är n log n, vilket är bra.

1832
01:19:54,380 --> 01:19:55,830
>> Titta på hur mycket bättre det är.

1833
01:19:55,830 --> 01:19:56,780
En sådan fin kurva.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Så mycket mer effektivt.

1836
01:20:00,120 --> 01:20:03,510
Om du någonsin kan, användning samman slag.

1837
01:20:03,510 --> 01:20:04,810
Det kommer att spara tid.

1838
01:20:04,810 --> 01:20:07,670
Då igen, som sagt, om
du är i detta nedre regionen,

1839
01:20:07,670 --> 01:20:09,480
Det gör inte det
mycket av en skillnad.

1840
01:20:09,480 --> 01:20:11,360
Du får upp till tusentals
och tusentals insatsvaror,

1841
01:20:11,360 --> 01:20:13,318
du absolut vill ha en
mer effektiv algoritm.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
Och, återigen, vår fina tabell över alla
sorterar att ni lärt idag.

1844
01:20:19,400 --> 01:20:21,157
>> Så jag vet att det har varit en tät dag.

1845
01:20:21,157 --> 01:20:23,490
Detta är inte nödvändigtvis kommer
för att hjälpa dig med din pset.

1846
01:20:23,490 --> 01:20:28,250
Men jag vill bara göra en ansvarsfriskrivning
det avsnittet handlar inte bara om psets.

1847
01:20:28,250 --> 01:20:31,240
Allt detta material är rättvist
spel för dina midterms.

1848
01:20:31,240 --> 01:20:35,430
Och även om du fortsätter med CS,
dessa är verkligen viktiga fundamenta

1849
01:20:35,430 --> 01:20:37,870
att du skulle behöva veta.

1850
01:20:37,870 --> 01:20:41,700
Så vissa dagar kommer att vara en
lite mer pset hjälp,

1851
01:20:41,700 --> 01:20:44,600
men några veckor kommer att vara
mycket mer faktiska innehållet

1852
01:20:44,600 --> 01:20:46,600
som kanske inte verkar super
användbart för dig just nu,

1853
01:20:46,600 --> 01:20:51,215
men jag lovar om du fortsätter
på kommer att bli mycket, mycket användbart.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Så det är det för avsnitt.

1856
01:20:54,250 --> 01:20:55,250
Ner till viran.

1857
01:20:55,250 --> 01:20:56,570
Jag gjorde det inom en minut.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Men där du går.

1860
01:20:58,970 --> 01:21:01,240
Och jag kommer att ha munkar eller godis.

1861
01:21:01,240 --> 01:21:03,464
Är någon allergisk mot
något, förresten?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Ägg och mjölk.

1864
01:21:05,890 --> 01:21:08,120
Så munkar är ett nej?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
OK.

1867
01:21:10,160 --> 01:21:10,770
Okej.

1868
01:21:10,770 --> 01:21:12,120
Choklad nej?

1869
01:21:12,120 --> 01:21:12,620
Starburst.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts är bra.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Vi kommer att ha
Starburst nästa vecka då.

1874
01:21:17,045 --> 01:21:18,240
Det är vad jag får.

1875
01:21:18,240 --> 01:21:19,690
Ni har en bra vecka.

1876
01:21:19,690 --> 01:21:20,460
Läs din spec.

1877
01:21:20,460 --> 01:21:22,130
>> Låt mig veta om du har några frågor.

1878
01:21:22,130 --> 01:21:25,300
Pset två kvaliteter bör vara
ut till dig av torsdagen.

1879
01:21:25,300 --> 01:21:28,320
Om du har några frågor
om hur jag graderade något

1880
01:21:28,320 --> 01:21:32,250
eller varför jag graderade något som jag
gjorde, vänligen maila mig, kom prata med mig.

1881
01:21:32,250 --> 01:21:34,210
Jag är lite galen ut
vecka, men jag lovar

1882
01:21:34,210 --> 01:21:36,340
Jag kommer fortfarande att svara inom 24 timmar.

1883
01:21:36,340 --> 01:21:38,240
Så ha en bra vecka, alla.

1884
01:21:38,240 --> 01:21:40,090
Lycka till på din pset.

1885
01:21:40,090 --> 01:21:41,248