Urut Pantas di Java Dijelaskan

Konvensyen Halving

Apabila bilangan elemen dalam senarai sama, separuh senarai bermaksud separuh pertama literal senarai adalah separuh pertama, dan separuh kedua literal senarai adalah separuh kedua. Elemen pertengahan (tengah) keseluruhan senarai, adalah elemen terakhir dari senarai pertama. Ini bermaksud indeks tengah adalah panjang / 2 - 1, kerana pengiraan indeks bermula dari sifar. Panjang adalah bilangan elemen dalam senarai. Sebagai contoh, jika bilangan elemen adalah 8, maka separuh pertama senarai mempunyai 4 elemen dan separuh kedua senarai juga mempunyai 4 elemen. Itu tidak mengapa. Oleh kerana pengiraan indeks bermula dari 0, indeks tengah adalah 3 = 8/2 - 1.

Bagaimana dengan kes itu, apabila bilangan elemen dalam senarai atau sub-senarai itu ganjil? Pada permulaan, panjangnya masih dibahagi dengan 2. Secara konvensional, bilangan elemen pada separuh pertama pembahagian ini adalah panjang / 2 + 1/2. Pengiraan indeks bermula dari sifar. Indeks tengah diberi panjang / 2 - 1/2. Ini dianggap sebagai istilah pertengahan, oleh konvensyen. Sebagai contoh, jika bilangan elemen dalam senarai adalah 5, maka indeks tengah adalah 2 = 5/2 - 1/2. Terdapat tiga elemen pada separuh pertama senarai dan dua elemen pada separuh masa kedua. Elemen tengah keseluruhan senarai adalah elemen ketiga pada indeks, 2, yang merupakan indeks tengah kerana pengiraan indeks bermula dari 0.

Pembahagian dengan cara ini adalah contoh aritmetik integer.

Median Tiga Nilai

Soalan: Berapakah median turutan:

C B A

Penyelesaian:
Susun senarai mengikut urutan menaik:

A B C

Istilah pertengahan, B, adalah median. Besarnya terletak di antara dua magnitud yang lain.

Mencari median dalam senarai tidaklah sebegitu. Sebagai contoh, dalam senarai 19 elemen yang tidak disusun, median untuk elemen pertama, elemen tengah, dan elemen terakhir mungkin diperlukan. Ketiga-tiga nilai ini mungkin tidak mengikut urutan menaik; dan begitu, indeksnya mesti diambil kira.

Dengan Quick Sort, median diperlukan untuk keseluruhan senarai dan sub-senarai. Pseudocode untuk mencari median tiga nilai yang dijelaskan dalam senarai (array) adalah:

Istilah arr bermaksud tatasusunan. Segmen kod ini mencari median dan juga melakukan penyortiran. Segmen kod ini kelihatan sederhana, tetapi boleh membingungkan. Oleh itu, perhatikan penjelasan berikut:

Penyortiran dalam tutorial ini akan menghasilkan senarai di mana nilai pertama adalah nilai terkecil, dan nilai terakhir adalah nilai terbesar. Dengan abjad, A kurang daripada Z.

Di sini, pangsi adalah median yang dihasilkan. Rendah adalah indeks terendah senarai atau sub-senarai (tidak semestinya untuk nilai terendah); tinggi adalah indeks tertinggi senarai atau sub-senarai (tidak semestinya untuk nilai tertinggi), dan tengah adalah indeks tengah konvensional (tidak semestinya untuk nilai tengah keseluruhan senarai).

Jadi, median yang akan diperoleh adalah antara nilai indeks terendah, nilai indeks tengah, dan nilai indeks tertinggi.

Dalam kod, indeks tengah konvensional diperoleh terlebih dahulu. Pada permulaan ini, senarai tidak disusun. Perbandingan dan beberapa penyusunan semula mengikut urutan menaik dari ketiga nilai tersebut akan berlaku pada masa yang sama. Pernyataan if pertama membandingkan nilai untuk indeks terendah dan indeks tengah. Sekiranya indeks tengah kurang daripada indeks terendah, maka kedua-dua nilai bertukar posisi. Ini mula menyusun dan mengubah susunan nilai dalam senarai atau sub-senarai. Pernyataan if kedua membandingkan nilai untuk indeks tertinggi dan indeks terendah. Sekiranya indeks tertinggi kurang daripada indeks terendah, kedua-dua nilai bertukar posisi. Ini menjalankan beberapa penyusunan dan perubahan susunan nilai dalam senarai atau sub-senarai. Pernyataan if ketiga membandingkan nilai untuk indeks tengah dan indeks tertinggi. Sekiranya indeks tertinggi kurang daripada indeks tengah, kedua-dua nilai bertukar posisi. Beberapa penyortiran atau penyusunan semula juga mungkin berlaku di sini. Keadaan jika ketiga ini tidak seperti dua sebelumnya.

Pada akhir ketiga pertukaran ini, nilai tengah dari ketiga nilai tersebut adalah A [tinggi], yang kandungan asalnya mungkin telah diubah dalam segmen kod. Contohnya, pertimbangkan urutan yang tidak disusun:

C B A

Kita sudah tahu bahawa mediannya adalah B. Namun, ini harus dibuktikan. Tujuannya di sini adalah untuk memperoleh median ketiga nilai ini menggunakan segmen kod di atas. Pernyataan if pertama membandingkan B dan C. Sekiranya B kurang dari C, maka kedudukan B dan C mesti ditukar. B kurang dari C, jadi susunan baru menjadi:

B C A

Perhatikan, nilai untuk indeks terendah dan indeks tengah telah berubah. Pernyataan if kedua membandingkan A dan B. Sekiranya A kurang dari B, maka kedudukan A dan B harus ditukar. A kurang dari B, jadi susunan baru menjadi:

A C B

Perhatikan, nilai untuk indeks tertinggi dan indeks terendah telah berubah. Pernyataan if ketiga membandingkan C dan B. Sekiranya C kurang dari B, maka kedudukan C dan B harus ditukar. C tidak kurang dari B, jadi tidak berlaku pertukaran. Susunan baru tetap seperti sebelumnya, iaitu:

A C B

B adalah median, iaitu, [tinggi], dan ia adalah pangsi. Oleh itu, pangsi lahir pada hujung senarai atau sub-senarai yang paling hujung.

Fungsi Pertukaran

Ciri lain yang diperlukan oleh Quick Sort adalah fungsi menukar. Fungsi menukar, menukar nilai dua pemboleh ubah. Pseudocode untuk fungsi pertukaran adalah:

Di sini, x dan y merujuk kepada nilai sebenar dan bukan salinannya.

Penyusunan dalam artikel ini akan menghasilkan senarai di mana nilai pertama adalah nilai terkecil, dan nilai terakhir adalah nilai terbesar.

Kandungan Artikel

• Algoritma Susun Pantas
• Pseudocode Partition
• Ilustrasi Urutan Pantas
• Pengekodan Java
• Kesimpulannya

Algoritma Susun Pantas

Cara biasa untuk menyusun senarai yang tidak disusun adalah dengan mempertimbangkan dua nilai pertama. Sekiranya tidak teratur, susunlah. Seterusnya, pertimbangkan tiga nilai pertama. Imbas dua yang pertama untuk melihat di mana nilai ketiga sesuai dan pas dengan tepat. Kemudian, pertimbangkan empat nilai pertama. Imbas tiga nilai pertama untuk melihat di mana nilai keempat sesuai dan sesuai dengan tepat. Teruskan dengan prosedur ini sehingga keseluruhan senarai disusun.

Prosedur ini, juga dikenali sebagai brute-force semacam, dalam bahasa pengaturcaraan komputer, terlalu lambat. Algoritma Quick Sort dilengkapi dengan prosedur yang lebih pantas.

Langkah-langkah untuk algoritma quicksort adalah seperti berikut:

1. Pastikan terdapat sekurang-kurangnya 2 nombor untuk disusun dalam senarai yang tidak disusun.
2. Dapatkan anggaran nilai pusat untuk senarai, yang dipanggil pangsi. Median, seperti yang dijelaskan di atas, adalah salah satu cara untuk mendapatkan pangsi. Berbagai cara datang dengan kelebihan dan kekurangan mereka. - Jumpa lagi.
3. Bahagikan senarai. Ini bermaksud, letakkan pivot dalam senarai. Dengan cara sedemikian, semua elemen di sebelah kiri lebih kecil daripada nilai pangsi, dan semua elemen di sebelah kanan lebih besar daripada atau sama dengan nilai pangsi. Terdapat cara pemisahan yang berbeza. Setiap kaedah partition dilengkapi dengan kelebihan dan kekurangannya. Pemisahan terbahagi dalam paradigma pembahagi dan penaklukan.
4. Ulangi langkah 1, 2, dan 3 secara berulang untuk pasangan sub-senarai baru yang muncul sehingga keseluruhan senarai disusun. Ini adalah penaklukan dalam paradigma perpecahan dan penaklukan.

Pseudocode Quick Sort adalah:

Pseudocode Partition

Partition pseudocode yang digunakan dalam tutorial ini adalah:

Dalam ilustrasi Urutan Pantas di bawah, kod ini digunakan:

Ilustrasi Urutan Pantas

Pertimbangkan senarai (susunan) huruf abjad yang tidak disusun berikut:

Q W E R T Y U I O P

Melalui pemeriksaan, senarai yang disusun adalah:

E I O P Q R T U W Y

Senarai yang disusun sekarang akan dibuktikan, menggunakan segmen algoritma dan pseudocode di atas, dari senarai yang tidak disusun:

Q W E R T Y U I O P

Pivot pertama ditentukan dari arr [0] = Q, arr [4] = T, dan arr [9] = P, dan dikenal pasti sebagai Q dan diletakkan di paling kanan senarai. Jadi, senarai dengan penyusun fungsi pangsi menjadi:

P W E R T Y U I O Q

Pivot semasa adalah Q. Prosedur pivot melakukan beberapa penyortiran kecil dan meletakkan P pada kedudukan pertama. Senarai yang dihasilkan harus disusun semula (dipartisi), sehingga, semua elemen di sebelah kiri bernilai lebih kecil, maka pangsi dan semua elemen di sebelah kanan pangsi, sama atau lebih besar daripada pangsi. Komputer tidak dapat melakukan partition dengan pemeriksaan. Jadi, ia berlaku dengan menggunakan indeks dan algoritma partition di atas.

Indeks rendah dan tinggi sekarang adalah 0 dan 9. Oleh itu, komputer akan bermula dengan mengimbas dari indeks 0 sehingga mencapai indeks, yang nilainya sama dengan atau lebih besar daripada pangsi dan berhenti di sana buat sementara waktu. Ia juga akan mengimbas dari hujung (kanan) tinggi, indeks 9, turun, sehingga mencapai indeks yang nilainya kurang dari atau sama dengan pangsi dan berhenti di sana buat sementara waktu. Ini bermaksud dua kedudukan berhenti. Sekiranya i, pemboleh ubah indeks kenaikan, dari rendah belum sama dengan atau lebih besar daripada pemboleh ubah indeks penurunan, j dari tinggi, maka kedua nilai ini ditukar. Dalam keadaan sekarang, pengimbasan dari kedua-dua hujung berhenti di W dan O. Jadi senarai menjadi:

P O E R T Y U I W Q

Pivot masih Q. Pengimbasan ke arah yang berlawanan berterusan dan berhenti dengan sewajarnya. Sekiranya i belum sama atau lebih besar daripada j, maka dua nilai di mana pengimbasan dari kedua hujung berhenti ditukar. Kali ini, pengimbasan dari kedua hujung berhenti di R dan I. Oleh itu, susunan senarai menjadi:

P O E I T Y U R W Q

Pivot masih Q. Pengimbasan ke arah yang berlawanan berterusan dan berhenti dengan sewajarnya. Sekiranya i belum sama atau lebih besar daripada j, maka dua nilai di mana pengimbasan berhenti, ditukar. Kali ini, pengimbasan dari kedua hujung berhenti di T untuk i dan I untuk j. saya dan j telah bertemu atau menyeberang. Jadi, tidak ada pertukaran. Senarai tetap sama seperti:

P O E I T Y U R W Q

Pada titik ini, pangsi, Q, mesti diletakkan pada kedudukan terakhir dalam penyortiran. Ini dilakukan dengan menukar arr [i] dengan arr [tinggi], menukar T dan Q. Senarai menjadi:

P O E I Q Y U R W T

Pada ketika ini, partition untuk keseluruhan senarai telah berakhir. Pivot = Q telah memainkan peranannya. Kini terdapat tiga sub-senarai, iaitu:

P O E I Q Y U R W T

Partisi adalah pembahagian dan penaklukan (penyortiran) dalam paradigma. Q berada pada kedudukan pengisihan yang betul. Setiap elemen di sebelah kiri Q lebih kecil daripada Q, dan setiap elemen di sebelah kanan Q lebih besar daripada Q. Walau bagaimanapun, senarai kiri masih tidak disusun; dan senarai yang betul masih belum disusun. Keseluruhan fungsi Quick Sort harus dipanggil secara berulang untuk menyusun sub-senarai kiri dan sub-senarai kanan. Pengingat Semula Pantas ini harus diteruskan; sub-senarai baru akan dikembangkan sehingga keseluruhan senarai asal disusun sepenuhnya. Untuk setiap mengingat fungsi Quick Sort, sub-senarai kiri dihadiri terlebih dahulu sebelum sub-senarai kanan yang sesuai dihadiri. Pivot baru mesti diperoleh untuk setiap sub-senarai.

Untuk sub-senarai:

P O E I

Pivot (median) untuk P, O, dan I ditentukan. Pivot adalah O. Untuk sub-senarai ini, dan berkaitan dengan senarai lengkap, arr baru [rendah] adalah arr [0], dan arr baru [tinggi] adalah arr terakhir [i-1] = arr [ 4-1] = arr [3], di mana saya adalah indeks pangsi terakhir dari partisi sebelumnya. Setelah fungsi pangsi () dipanggil, nilai pangsi baru, pivot = O. Jangan mengelirukan antara fungsi pangsi dan nilai pangsi. Fungsi pangsi mungkin melakukan beberapa penyortiran kecil dan meletakkan pangsi di paling kanan sub-senarai. Sub-senarai ini menjadi,

Saya P E O

Dengan skema ini, pivot selalu berakhir di hujung kanan sub-senarai atau senarai setelah panggilan fungsinya. Pengimbasan dari kedua hujung bermula dari arr [0] dan arr [3] sehingga i dan j bertemu atau menyeberang. Perbandingan dilakukan dengan pivot = O. Perhentian pertama adalah di P dan E. Mereka ditukar, dan sub-senarai baru menjadi:

I E P O

Pengimbasan dari kedua hujung berterusan, dan perhentian baru berada di P untuk i dan di E untuk j. Sekarang saya dan j telah bertemu atau menyeberang. Jadi sub-senarai tetap sama seperti:

I E P O

Pembahagian sub-senarai atau senarai berakhir apabila pivot telah diletakkan pada kedudukan terakhirnya. Jadi, nilai baru untuk arr [i] dan arr [tinggi] ditukar. Iaitu, P dan O ditukar. Sub-senarai baru menjadi:

I E O P

O kini berada di kedudukan terakhir untuk keseluruhan senarai. Peranannya sebagai pangsi telah berakhir. Sub-senarai kini dibahagikan kepada tiga senarai lagi, iaitu:

I E O P

Pada ketika ini, Segera Pantas dari sub-senarai kanan pertama mesti dipanggil. Walau bagaimanapun, ia tidak akan dipanggil. Sebaliknya, ia akan diperhatikan dan dicadangkan, untuk dipanggil kemudian. Ketika pernyataan fungsi partisi sedang dijalankan, dari bahagian atas fungsi, itu adalah Urutan Pantas untuk sub-daftar kiri yang mesti dipanggil sekarang (setelah pivot () dipanggil). Ia akan dipanggil untuk senarai:

Saya E

Ia akan dimulakan dengan mencari median I dan E. Di sini, arr [rendah] = I, arr [pertengahan] = I dan arr [tinggi] = E. Jadi median, pangsi, harus ditentukan oleh algoritma pangsi sebagai , I. Namun, pseot pseot di atas akan menentukan pivot sebagai E. Kesalahan ini berlaku di sini kerana pseudocode di atas dimaksudkan untuk tiga elemen dan bukan dua. Dalam pelaksanaan di bawah, terdapat beberapa penyesuaian kod. Sub-senarai menjadi,

E Saya

Pivot selalu berakhir di hujung kanan sub-senarai atau senarai selepas panggilan fungsinya. Pengimbasan dari kedua hujung bermula dari arr [0] dan arr [1] eksklusif sehingga i dan j bertemu atau menyeberang. Perbandingan dilakukan dengan pivot = I. Perhentian pertama dan satu-satunya adalah di I dan E: di I untuk i dan di E untuk j. Sekarang saya dan j telah bertemu atau menyeberang. Oleh itu, sub-senarai tetap sama seperti:

E Saya

Pembahagian sub-senarai atau senarai berakhir apabila pivot telah diletakkan pada kedudukan terakhirnya. Jadi, nilai baru untuk arr [i] dan arr [tinggi] ditukar. Ia berlaku di sini bahawa arr [i] = I dan arr [tinggi] = I. Oleh itu, nilai yang sama ditukar dengan dirinya sendiri. Sub-senarai baru menjadi:

E Saya

Saya kini berada di kedudukan terakhir untuk keseluruhan senarai. Peranannya sebagai pangsi telah berakhir. Sub-senarai kini dibahagikan kepada dua senarai lagi, iaitu,

E Saya

Sekarang, pivot sejauh ini adalah Q, O, dan I. Pivots berakhir pada kedudukan terakhir mereka. Sub-senarai satu elemen, seperti P di atas, juga berakhir pada kedudukan terakhirnya.

Pada ketika ini, sub-senarai kiri pertama telah disusun sepenuhnya. Dan prosedur menyusun sekarang adalah:

E I O P Q Y U R W T

Sub-senarai kanan pertama:

Y U R W T

masih perlu disusun.

Menaklukkan Sub-Senarai Kanan Pertama
Ingat bahawa panggilan Quick Sort untuk sub-senarai kanan pertama dicatat dan disimpan dan bukan dilaksanakan. Pada ketika ini, ia akan dilaksanakan. Oleh itu, arr baru [rendah] = arr [5] = arr [QPivotIndex + 1], dan arr baru [tinggi] tetap arr [9]. Kumpulan aktiviti serupa yang berlaku untuk sub-senarai kiri pertama akan berlaku di sini. Sub-senarai kanan pertama ini disusun mengikut:

R T U W Y

Dan senarai asal yang tidak disusun telah disusun ke:

E I O P Q R T U W Y

Pengekodan Java

Meletakkan algoritma di Java hanya dengan memasukkan semua segmen pseudocode di atas ke dalam kaedah Java dalam satu kelas. Jangan lupa bahawa perlu ada kaedah utama () di kelas yang akan memanggil fungsi quicksort () dengan array yang tidak disusun.

Kaedah pangsi ()

Kaedah Java pivot () yang mengembalikan nilai, pivot, harus:

Kaedah pertukaran ()

Kaedah pertukaran () hendaklah:

Kaedah quicksort ()

Kaedah quicksort () mestilah:

Kaedah partition ()

Kaedah partition () mestilah:

Kaedah utama ()

Kaedah utama () boleh menjadi:

Semua kaedah di atas boleh dimasukkan ke dalam satu kelas.

Kesimpulannya

Quick Sort adalah algoritma penyortiran yang menggunakan paradigma pembahagi dan penaklukan. Ia bermula dengan membahagikan senarai yang tidak disusun menjadi dua atau tiga sub-senarai. Dalam tutorial ini, Quick Sort telah membahagikan senarai menjadi tiga sub-senarai: sub-senarai kiri, senarai tengah satu elemen, dan sub-senarai kanan. Menakluki dalam Quick Sort adalah membahagikan senarai atau sub-senarai sambil menyusunnya, menggunakan nilai pangsi. Tutorial ini telah menjelaskan satu pelaksanaan Quick Sort dalam bahasa komputer Java.

Mengenai Pengarang

Chrysanthus Forcha

Penemu Integrasi Matematik dari Prinsip Pertama dan siri yang berkaitan. Ijazah Sarjana dalam Pendidikan Teknikal, yang mengkhususkan diri dalam Elektronik dan Perisian Komputer. Elektronik BSc. Saya juga mempunyai pengetahuan dan pengalaman di peringkat Master dalam Pengkomputeran dan Telekomunikasi. Daripada 20,000 penulis, saya adalah penulis ke-37 terbaik di devarticles.com. Saya telah bekerja di bidang ini selama lebih dari 10 tahun.

POS HINT LINUX BERKAITAN

• Membandingkan Rentetan di Jawa
• Cara menggunakan HashMap di Java
• Urut Pantas di Java Dijelaskan
• Perjalanan Preorder Pokok Binari di Jawa
• Gabungan Susun di Java Dijelaskan
• Cara menggunakan Scanner di Java
• Java menulis ke fail