[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.