[Powered by Google Translate] TOMMY: Mari kita lihat semacam seleksi, algoritma untuk mengambil daftar nomor dan menyortir mereka. Sebuah algoritma, ingat, hanya langkah-demi-langkah prosedur untuk menyelesaikan tugas. Ide dasar dibalik semacam seleksi untuk membagi daftar kami menjadi dua bagian - sebagian diurutkan dan bagian unsorted. Pada setiap langkah algoritma, nomor dipindahkan dari unsorted bagian ke bagian diurutkan sampai akhirnya Daftar seluruh diurutkan. Jadi di sini adalah daftar dari enam nomor - 23, 42, 4, 16, 8, dan 15. Saat ini seluruh daftar dianggap unsorted. Meskipun nomor seperti 16 mungkin sudah berada dalam yang benar lokasi, algoritma kami tidak memiliki cara untuk mengetahui bahwa sampai Daftar seluruh diurutkan. Jadi kami akan mempertimbangkan setiap nomor yang akan unsorted sampai kita mengurutkan diri kita sendiri. Kita tahu bahwa kita ingin daftar untuk berada di urutan. Jadi kita akan ingin membangun bagian diurutkan dari daftar kami dari kiri ke kanan, terkecil hingga terbesar. Untuk melakukan itu, kita harus menemukan elemen minimum unsorted dan letakkan di bagian akhir bagian diurutkan. Karena daftar ini tidak diurutkan, satu-satunya cara untuk melakukannya adalah untuk melihat setiap elemen di bagian unsorted, mengingat elemen yang terendah dan membandingkan setiap elemen itu. Jadi pertama-tama kita akan melihat 23. Ini adalah elemen pertama telah kita lihat, jadi kita akan ingat sebagai minimum. Selanjutnya kita akan melihat 42. 42 lebih besar dari 23, sehingga 23 masih minimum. Berikutnya adalah 4 yang kurang dari 23, jadi kita akan ingat 4 sebagai baru minimum. Berikutnya adalah 16 yang lebih besar dari 4, sehingga 4 masih minimum. 8 lebih besar dari 4, dan 15 lebih besar dari 4, sehingga 4 harus elemen unsorted terkecil. Jadi meskipun sebagai manusia kita bisa langsung melihat bahwa 4 adalah elemen minimum, algoritma kami perlu melihat setiap elemen unsorted, bahkan setelah kami telah menemukan 4 - minimum elemen. Jadi sekarang kita telah menemukan elemen minimum, 4, kita akan ingin untuk memindahkannya ke bagian diurutkan dari daftar. Karena ini adalah langkah pertama, ini berarti kita ingin menempatkan 4 di awal daftar. Saat ini 23 adalah pada awal daftar, sehingga mari kita swap 4 dan 23. Jadi sekarang daftar kami terlihat seperti ini. Kita tahu bahwa 4 harus di lokasi akhirnya, karena baik elemen terkecil dan elemen pada awal dari daftar. Jadi ini berarti bahwa kita tidak merasa perlu untuk memindahkannya lagi. Jadi mari kita ulangi proses ini untuk menambahkan elemen lain ke diurutkan bagian dari daftar. Kita tahu bahwa kita tidak perlu melihat 4, karena sudah diurutkan. Jadi kita bisa mulai di 42, yang kita akan ingat sebagai minimum elemen. Jadi selanjutnya kita akan melihat 23 yang kurang dari 42, jadi kami ingat 23 adalah baru minimum. Selanjutnya kita melihat 16 yang kurang dari 23, sehingga 16 adalah baru minimum. Sekarang kita melihat 8 yang kurang dari 16, sehingga 8 adalah minimum baru. Dan akhirnya 8 kurang dari 15, sehingga kita tahu bahwa 8 adalah minimum unsorted elemen. Jadi itu berarti kita harus menambahkan 8 untuk diurutkan bagian dari daftar. Sekarang 4 adalah satu-satunya elemen diurutkan, jadi kami ingin menempatkan 8 sebelah 4 tersebut. Sejak 42 adalah elemen pertama di bagian unsorted dari daftar, kita akan ingin menukar 42 dan 8. Jadi sekarang daftar kami terlihat seperti ini. 4 dan 8 merupakan bagian diurutkan dari daftar, dan nomor yang tersisa mewakili unsorted bagian dari daftar. Jadi mari kita lanjutkan dengan iterasi yang lain. Kita mulai dengan 23 kali ini, karena kita tidak perlu melihat 4 dan 8 lagi karena mereka sudah sudah diurutkan. 16 kurang dari 23, jadi kita akan ingat 16 sebagai minimum baru. 16 kurang dari 42, tapi 15 adalah kurang dari 16, jadi 15 harus elemen unsorted minimum. Jadi sekarang kita ingin menukar 15 dan 23 untuk memberi kita daftar ini. Bagian diurutkan daftar terdiri dari 4, 8 dan 15, dan unsur tersebut masih unsorted. Tapi kebetulan bahwa unsur unsorted berikutnya, 16, sudah diurutkan. Namun, ada cara untuk algoritma kami untuk mengetahui bahwa 16 sudah di lokasi yang benar, sehingga kita masih perlu ulangi proses yang sama persis. Jadi kita melihat bahwa 16 kurang dari 42, dan 16 adalah kurang dari 23, sehingga 16 harus menjadi unsur minimal. Tidak mungkin untuk menukar elemen ini dengan dirinya sendiri, sehingga kami dapat hanya meninggalkannya di lokasi ini. Jadi kita perlu satu lagi lulus dari algoritma kami. 42 lebih besar dari 23, maka 23 harus minimum unsorted elemen. Setelah kita swap 23 dan 42, kita berakhir dengan akhir kami diurutkan daftar - 4, 8, 15, 16, 23, 42. Kita tahu 42 harus berada di tempat yang benar karena itu adalah Unsur-satunya yang tersisa, dan itu semacam seleksi. Mari kita sekarang meresmikan algoritma kami dengan beberapa pseudocode. On line satu, kita dapat melihat bahwa kita perlu mengintegrasikan lebih setiap elemen dari daftar. Kecuali elemen terakhir, sejak elemen 1 Daftar sudah diurutkan. On line dua, kita mempertimbangkan elemen pertama dari unsorted bagian dari daftar yang akan minimum, seperti yang kita lakukan dengan kami Misalnya, jadi kami memiliki sesuatu untuk membandingkan. Baris ketiga dimulai loop kedua di mana kita iterate atas setiap elemen unsorted. Kita tahu bahwa setelah i iterasi, bagian diurutkan dari daftar kami harus i elemen di dalamnya karena setiap langkah macam satu elemen. Jadi elemen unsorted pertama harus dalam posisi i ditambah 1. On line empat, kita membandingkan elemen saat ini ke minimum elemen yang telah kita lihat sejauh ini. Jika elemen saat ini lebih kecil dari jumlah minimum elemen, maka kita ingat elemen saat ini sebagai baru minimum pada baris kelima. Akhirnya, pada baris enam dan tujuh, kami bertukar minimum elemen dengan elemen unsorted pertama, sehingga menambahkannya ke bagian diurutkan dari daftar. Setelah kita memiliki sebuah algoritma, pertanyaan penting untuk bertanya diri sebagai programmer adalah berapa lama yang mengambil? Kami pertama-tama akan bertanya berapa lama waktu yang diperlukan untuk ini algoritma untuk menjalankan dalam kasus terburuk? Ingat kami mewakili berjalan ini waktu dengan notasi O besar. Dalam rangka untuk menentukan unsur unsorted minimum, kita dasarnya harus membandingkan setiap elemen dalam daftar untuk setiap elemen lain dalam daftar. Secara intuitif, ini terdengar seperti O operasi n kuadrat. Melihat pseudocode kami, kami juga memiliki loop bersarang di dalam loop lain, yang memang terdengar seperti O operasi n kuadrat. Namun, ingat bahwa kita tidak perlu melihat lebih Seluruh daftar ketika menentukan elemen unsorted minimum? Setelah kita tahu bahwa 4 itu diurutkan, misalnya, kita tidak perlu melihat lagi. Jadi, apakah ini lebih rendah waktu berjalan? Untuk daftar panjang 6, kita perlu membuat lima perbandingan untuk elemen pertama, empat untuk perbandingan elemen kedua, dan seterusnya. Itu berarti bahwa jumlah langkah adalah jumlah dari bilangan bulat dari 1 sampai panjang daftar dikurangi 1. Kita bisa mewakili ini dengan penjumlahan. Kami tidak akan masuk ke sini penjumlahan. Tapi ternyata bahwa penjumlahan ini sama dengan n kali n minus 1 lebih dari 2. Atau ekuivalen, n kuadrat lebih dari 2 dikurangi n lebih dari 2. Ketika berbicara tentang runtime asimtotik, istilah kuadrat n akan mendominasi istilah n. Jadi semacam seleksi O n kuadrat. Ingatlah bahwa dalam contoh kita, semacam seleksi masih diperlukan untuk memeriksa apakah nomor yang sudah diurutkan perlu dipindahkan. Jadi itu berarti bahwa jika kita berlari semacam seleksi atas yang sudah diurutkan daftar, itu akan membutuhkan jumlah yang sama dari langkah-langkah seperti akan ketika berjalan di atas daftar sepenuhnya unsorted. Jadi semacam seleksi memiliki kinerja kasus terbaik n kuadrat, yang kami mewakili dengan omega n kuadrat. Dan itu untuk semacam seleksi. Hanya salah satu dari banyak algoritma kita bisa digunakan untuk mengurutkan daftar. Nama saya Tommy, dan ini adalah cs50.