DOUG LLOYD: áá¡á CS50 ááááááá á¡á®ááááá¡á®áá ááá®áá áá¡á®ááá áá á«ááááá¡ ááááá áááááá. áá áááá¯áá  áá¡ á¨ááá«áááá áá§áá¡ áªáá¢á á¡áá®áá¤ááá á¨áááá á©á£áááá á¡ááá¦áá á á á ááááá áááá ááááááá¡ á á. á©ááá ááááááááá áá®áááá ááá¬ááááá áá á¨áááá®áá á«ááááá, áá á¡ááááá¡ áá ááááá á¡á®áá á¡ááá«ááá á áá ááá®áá áá¡á®ááá ááááá áááááá. áá¡á á áá, áá ááááá ááááá áá®áááá á áááááááá á¬á£áá áªááááááá áá áááááá®áááá¡ áááááá£á ááááá áááá á¥ááááá ááá¡á á«áá ááááá ááááááá¢ááá áá¡á á áá áá¥ááá á¨áááá«áááá áááá®á¡ááááá¡, á áá á§áááááá áááá¨ááááááááá ááá¤áá áááªáá ááá á¨áá¡áá®áá áá á¨áá«áááá¡ ááááá¢áááá áááá¡á®áááááááá, á¡áá­áá ááááá¡ á¨áááá®ááááá¨á. 

ááá áááá áá áá¡ áá¡, á¨áá á©ááá áá ááááá á. á«áá ááááá áááá á£ááá á¨áá á©áááá¡ ááááááááá¡ áááá«ááááá á§áááááá ááá¢áá á áá áá¡áá á¢áá ááá£áá ááááááá¢á¡ ááá¡ááá áá á¡ááá ááá ááá áááá áá áá¡áá á¢áá ááá£áá ááááááá¢á¡ á áá ááá¡ááá. á©ááá ááá¥ááá, á áá á§áááááá á£áá áá¡ áá¬áá ááááá¡ áá á, á áá n ááááá áá¢á¨á. áá áá£ áááááá ááááá®á¡áááá, á áá¢áá, áááá¦áá¡ á¨ááá®áááá á¨áá á©áááá¡ ááááááááá¡ ááááá. á¡áá£ááááá¡á á¨áááá®ááááá¨á ááá á¡ááá¥á¢áááá¨á áá á áá¡ááá n ááááá áá¢á¨á. 

Bubble ááááááááá¡, áááá, á áá áá áá á¡ááá áááááááá á á¬á§áááá. áá¡á á áá, áá¡ áá áá¡ ááá¡áá¦ááá, á ááááááª ááááá®ááá áááá ááá®á¡ááá¡ áááá¡á®áááááá áá¥. á¨áá á©ááá ááááááááá¡ áá áá¡, á¯áá á¯áá áááá, áááá«ááááá smallest-- bubble ááááááááá¡ áá áá¡ á¡ááá áááááááá á á¬á§áááá. á©ááá á¡ááá áááááááá á á¬á§áááá ááááááá¢áááá¡, áá£ áá¡ááá áá¬á§ááá áááá ááááá¡á£ááá, á ááááááª áá¤áá¥á¢á£á áá áá£á¨á¢ááá áááá ááááááá¢ááá á£á¤áááá, áá, ááááá áá áá¡, áá¡ áá¡ááá áá¬á§ááá áááááááááááá ááá¢áá á ááááááá¢ááá ááá áªá®ááá. á£áá áá¡á á¨áááá®ááááá¨á ááá á¡ááá¥á¢áááá¨á áá á of bubble sort áá áá¡ n ááááá áá¢á¨á. á¡áá£ááááá¡á á¨áááá®ááááá¨á ááá á¡ááá¥á¢áááá¨á áá á of bubble sort áá áá¡ n. áááá¡ áááá, á áá á¡áá¢á£ááªáá á©ááá áá  á áááá£á áá á©ááá á¨ááá«áááá áá  á£ááá áááá¦áá¡ ááááá¡áááá á á¡ááááááá¡ á§áááá. á©ááá áá®áááá á£ááá áááá¦áá¡ áá áá ááááááá¡ ááááá n ááááááá¢ááá¡. 

In á©áá¡áá á¡áá®áá¡, á«áá ááááá áááá áá¥ áááááááá. á¡á¬áá áá á¡áá¢á§ááá Insertion ááááááááá¡. á©ááá ááááá ááá, á áá áááááááá¡ áá áá®áá ááá¨áááááá ááá¡ááá ááá áªá®ááááá ááá á¯áááá. áá á áááá áª á©ááá áááááááá, á©ááá áááá ááá¡ ááááá¡áááá¡ ááááááá¢ááá á©ááá á£ááá ááááááá®áá, á ááá áááá®á ááªáá á ááá ááá, á áá á£ááá áááá ááá¡ á¡ááá¦ááª á£ááá á áá ááá®áá áá¡á®ááá£áá ááá¬ááá. áá¡á á áá, á©ááá áááá¨áááá ááá®áá áá¡á®ááá£áá ááá¡ááá áá áá ááááááá¢á¡ áá áá¡, ááá áªá®ááááá ááá á¯áááá, áá á©ááá áááááá¢ááá á áá, á ááá áááá®á¨á. á£áá áá¡á ááá á¡ááá¥á¢áááá¨á áá á Insertion ááááááááá¡ áá áá¡ n ááááá áá¢á¨á. á¡áá£ááááá¡á á¨áááá®ááááá¨á áá¬áá ááááá¡ áá á n. 

á¨áá á¬á§áá ááááááááá¡ á¡áá¢á§ááá áá¥ áá áá¡ ááá§áá¤ááá áá á¨áá á¬á§áá. á©ááá ááá§áá¤ááá á¡á á£áá ááá¡ááá, áá£ áá á áá¡ áá¥áá¡á ááááááá¢ááá, á áá ááááááá¢ááá¡, 10,000 ááááááá¢ááá¡ á©ááá ááá§áá¤ááá ááá á¥ááááá ááá®áááá á, ááá®áááá á, ááá®áááá á, á¡áááá á©ááá áááá¥áá¡ á¥ááá¨ ááá¡ááá á-áá áá ááááááá¢áá ááá¡ááááá. ááááááá¥á¢á n áá á ááááááá¢á¡ ááá¡ááááá. áá¡á á áá, á©ááá ááááá¬á§áá áá áá 1000-ááááááá¢á¡ ááá¡ááá, áá ááááá¦ááá áá á¬áá á¢ááá¨á, á¡ááááª á©ááá 1,000 áá áá ááááááá¢á ááá¡ááááá. ááá¨áá á©ááá ááá¬á§ááá á¨áá á¬á§áá áá á¥áá ááááá¥á¢áá ááá á£ááá áá ááá á¡á¬áá á áááááá. áá¡á á áá, á©ááá ááá¦ááá áá á áá áá ááááááá¢á ááááá¥á¢áá ááá áá á¨áá¥ááá áá á ááááááá¢á¡ ááá¡ááá. á©ááá ááá¦ááá áá á áá  ááááááá¢á¡ ááááá¥á¢áá ááá áá á¨áá¥áááá¡ ááá®á ááááááá¢á¡ ááá¡ááá áá áá¡á á¨ááááá áá áá¡á á¨ááááá, á¡áááá á©ááá áá áá®áá áááááááááá£áá áá á n ááááááá¢á¡ ááá¡ááá. 

á£áá áá¡á ááá á¡ááá¥á¢áááá¨á áá á á¨áá á¬á§áá ááááááááá¡ áá áá¡ N á¯áá  á¨áá¡ááá n. á©ááá ááá§ááá¡ n ááááááá¢ááá, áááá áá áá recombining áá ááªáá¡á áá¦ááá¡ á¨áá¡ááá N ááááá¯ááá ááá¡áá¦áááá á£ááá á¡á á£áá ááá¡ááá. á¡áá£ááááá¡á á¨áááá®ááááá¨á áá¬áá ááááá¡ áá áá¡ áá¡ááá n á¨áá¡ááá n á ááááá áá¡ áá ááªáá¡á ááááááááá áá  ááááá¢áá áá¡ááá¡ áá£ áá á ááá¡ááá ááá®áá áá¡á®ááá£áá áá áá  á£ááá áááá¬á§áá¡. áá ááªáá¡á ááááá, áá á¡ááááá¡ áá áááááá  á¨áááá®ááááá¨á áá  á£ááá ááááá á©áá ááá á áá. áá¡á á áá, N á¨áá¡ááá N á£áá áá¡ á¨áááá®ááááá¨á, N á¨áá¡ááá N á¡áá£ááááá¡á á¨áááá®ááááá¨á. 

á©ááá ááá¡áá£áá áá áá á á«ááááá¡ ááááá áááááá. áá¡á á áá á¬á á¤ááá á«áááá áááá®áááááá iterating. á©ááá áááá á«ááááá ááá¡á¨á¢áááá ááá¡ááá áá áá®áá, ááá áªá®ááááá ááá á¯áááá, áªáááááá¡ áááááá¡ ááááá á á©ááá ááá«ááá. á£áá áá¡á áá¬áá ááááá¡ áá á áá áá¡ áááá á á. áá¡ á¨ááá«áááá áááá¦áá¡ á©ááááááá¡ iterating ááá¡á¨á¢áááá áááááá£áá ááááááá¢áá¡ áááááá ááááááá¢á¡ á©ááá ááá«ááá áááá¡áááá¡, áá áª áááá ááááááááááá, áá á¡ááá ááá áá . áááá áá á©ááá ááá  áááá¡á¢á£á áááá, á áá á¡áááá á©ááá á¨ááá®ááá á§ááááá¤áá á. ááá  á¡áá£ááááá¡á á¨áááá®ááááá¨á, á©ááá ááá£á§áááááááá. á¡áá£ááááá¡á á¨áááá®ááááá¨á ááá á¡ááá¥á¢áááá¨á áá á á®ááááááá á«áááá omega 1. 

áá ááááá¡, áá ááááá á«áááá, á ááááááª ááááá®ááá¡ áá¡áá á¢á ááá¡ááá. ááá®á¡ááááá, á áá áá¡ áá áá¡ á«ááááá áááá¨ááááááááá áááá®ááááá¡ á áááá¡ááª áá£á¨áááá áá ááááá á«áááá. áá¡ áá áá¡ á¬áááááá ááá ááááá§áááááá it-- ááá¡ááá, á áá áá¥ááá ááááá®áááá á£ááá áá§áá¡ ááá®áá áá¡á®ááá£áá. á¬ááááá¦áááá á¨áááá®ááááá¨á, á¡áá¢á§ááá áá áá¡ ááááá¨á áá ááááá§á áá. ááá§áá¤ááá ááá¡ááá ááá®áááá á áá áá¦ááá¤á®áá áá¡ ááá®áááá á¨á ááááááá¢ááá á§áááá á¯áá áá, á áááá áª áá¥ááá áááá¦áá¡ ááá¨áááááá. áááá¡ áááá, á áá áá ááááá¨á áá ááááá§á áá áá ááá§áá¤á á áá ááá®áááá á ááááááá, á£áá áá¡á ááá á¡ááá¥á¢áááá¨á áá á áá ááááá á«áááá áá áá¡ á¨áá¡ááá N, á ááááááª áá á¡áááááá á£ááááá¡áá á®ááááááá á«áááá á¡ á. á¡áá£ááááá¡á ááá á¡ááá¥á¢áááá¨á áá á áá áá¡ ááááá áá áá. 

á©ááá, á¨ááá«áááá, ááá¨áááá ááá ááááá á©ááá áááááá, áááá áá, áá áá®áá, ááá®á¡ááá¡, á áá ááá£á®áááááá áááá¡á, á áá áá ááááá á«áááá áá áá¡ áááªáááááá á£ááááá¡áá, áááá á á®ááááááá á«áááá á«áááá áá§áá¤á log n á¬ááááá¦áááá n, áá¥ááá á£ááá ááááá áá¡ áá£á¨áááá ááá®áá áá¡á®ááá áá¥áááá ááá¡ááá ááá áááá, á ááááááª á¨áá¡áá«ááá áá¡ áááááááá áá¤áá¥á¢á£á á áááááááááá£ááá on áááá iterating ááááááá¬ááááá£áá. 

áá Doug Lloyd, áá¡ áá áá¡ CS50.