QuickSort คืออัลกอริทึมการแบ่งและพิชิต ในกระบวนทัศน์การออกแบบอัลกอริทึมของ Divide & Conquer เราแบ่งปัญหาในปัญหาย่อยซ้ำ ๆ จากนั้นแก้ปัญหาย่อยและในที่สุดก็รวมวิธีแก้ปัญหาเพื่อค้นหาผลลัพธ์สุดท้าย ในบทความนี้เราจะเน้นไปที่ QuickSort In
คำแนะนำต่อไปนี้จะกล่าวถึงในบทความนี้
เอาล่ะ!
สิ่งหนึ่งที่ควรคำนึงถึงในขณะที่แบ่งปัญหาออกเป็นปัญหาย่อยก็คือโครงสร้างของปัญหาย่อยจะไม่เปลี่ยนแปลงเหมือนปัญหาเดิม
อัลกอริทึม Divide & Conquer มี 3 ขั้นตอน:
- แบ่ง: แบ่งปัญหาออกเป็นปัญหาย่อย
- Conquer: แก้ปัญหาย่อยซ้ำ ๆ
- รวม: การรวมโซลูชันเพื่อให้ได้ผลลัพธ์สุดท้าย
การจัดการข้อยกเว้นในขั้นตอนการจัดเก็บ oracle
มีอัลกอริทึมที่หลากหลายตามกระบวนทัศน์แบ่งและพิชิต การเรียงลำดับอย่างรวดเร็วและการรวมอยู่ในหมู่พวกเขา
แม้ว่าความซับซ้อนของเวลาที่เลวร้ายที่สุดของ QuickSort คือ O (n2) ซึ่งมากกว่าอัลกอริธึมการเรียงลำดับอื่น ๆ เช่น Merge Sort และ Heap Sort แต่ QuickSort นั้นเร็วกว่าในทางปฏิบัติเนื่องจากวงในสามารถนำไปใช้งานได้อย่างมีประสิทธิภาพในสถาปัตยกรรมส่วนใหญ่ ข้อมูลจริง
มาพูดถึงการใช้อัลกอริทึมการจัดเรียงด่วน Quicksort อัลกอริทึมใช้องค์ประกอบ pivot และแบ่งพาร์ติชันอาร์เรย์รอบ ๆ pivot elememt Quicksot มีหลายรูปแบบซึ่งขึ้นอยู่กับว่าคุณเลือกองค์ประกอบ Pivot อย่างไร มีหลายวิธีในการเลือกองค์ประกอบ Pivot:
ความแตกต่างระหว่างปริญญาโทและปริญญาโท
- เลือกองค์ประกอบแรก
- เลือกองค์ประกอบสุดท้าย
- เลือกองค์ประกอบแบบสุ่ม
- การเลือกองค์ประกอบมัธยฐาน
สิ่งสำคัญต่อไปที่ต้องทำความเข้าใจคือฟังก์ชันพาร์ติชัน () ในอัลกอริทึมการเรียงลำดับด่วน ฟังก์ชันพาร์ติชั่นเพื่อรับองค์ประกอบเดือยวางไว้ในตำแหน่งที่เหมาะสมย้ายองค์ประกอบทั้งหมดที่มีขนาดเล็กกว่าองค์ประกอบเดือยไปทางซ้ายและองค์ประกอบทั้งหมดอยู่ทางขวามากขึ้น Quicksort ใช้เวลาเชิงเส้นในการทำเช่นนั้น
จากนั้นอาร์เรย์จะแบ่งออกเป็นสองส่วนจากองค์ประกอบ Pivot (เช่นองค์ประกอบที่น้อยกว่า pivot & องค์ประกอบที่มากกว่า pivot) และอาร์เรย์ทั้งสองจะเรียงลำดับซ้ำโดยใช้อัลกอริทึม Quicksort
ตอนนี้เราเข้าใจการทำงานของอัลกอริทึม QuickSort แล้ว มาทำความเข้าใจวิธีใช้อัลกอริทึม Quicksort ใน Java กัน
QuickSort ฟังก์ชัน:
/ * ฟังก์ชัน Quicksort ต้องการให้อาร์เรย์เรียงลำดับด้วยดัชนีต่ำสุดและสูงสุด * /
การจัดเรียงเป็นโมฆะ (int arr [], int lowIndex, int highIndex) {// จนกว่า lowIndex = highIndex ถ้า (lowIndexตอนนี้ให้เราดูรหัสการแบ่งพาร์ติชันเพื่อทำความเข้าใจว่ามันทำงานอย่างไร
พาร์ทิชัน รหัส
ในรหัสการแบ่งพาร์ติชันเราจะเลือกองค์ประกอบสุดท้ายเป็นองค์ประกอบเดือย เราสำรวจอาร์เรย์ทั้งหมด (เช่นใช้ตัวแปร j ในกรณีของเรา) เราติดตามองค์ประกอบที่เล็กที่สุดสุดท้ายในอาร์เรย์ (เช่นการใช้ตัวแปร i ในกรณีของเรา) หากเราพบองค์ประกอบใด ๆ ที่เล็กกว่าเดือยเราจะย้ายองค์ประกอบปัจจุบัน a [j] กับ arr [i] มิฉะนั้นเราจะเคลื่อนที่ต่อไป
พาร์ติชัน int (int arr [], int lowIndex, int highIndex) {// ทำให้องค์ประกอบสุดท้ายเป็น pivot int pivot = arr [highIndex] // ใช้ i เพื่อติดตามองค์ประกอบที่เล็กกว่าจาก pivot int i = (lowIndex-1) สำหรับ (int j = lowIndex jเมื่อคุณเข้าใจฟังก์ชัน Quicksort & partition แล้วให้เราดูโค้ดทั้งหมดอย่างรวดเร็ว
QuickSort รหัส Java
class QuickSort {// Partition Method int partition (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) สำหรับ (int j = lowIndex j// วิธีการเรียงลำดับ
การจัดเรียงเป็นโมฆะ (int arr [], int lowIndex, int highIndex) {if (lowIndex// วิธีการพิมพ์อาร์เรย์
โมฆะคง printArray (int arr []) {int n = arr.length สำหรับ (int i = 0 i// วิธีหลัก
วิธีใช้บริการตอนนี้
โมฆะคงที่สาธารณะ main (สตริง args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('sorted array') printArray (arr)}} เอาท์พุต:
หลังจากเรียกใช้โปรแกรม Java ข้างต้นแล้วคุณจะเข้าใจว่า QuickSort ทำงานอย่างไรและวิธีการใช้งานใน Javaดังนั้นเราจึงมาถึงตอนท้ายของบทความ 'Quicksort in Java' นี้ หากคุณต้องการเรียนรู้เพิ่มเติมตรวจสอบไฟล์ โดย Edureka บริษัท การเรียนรู้ออนไลน์ที่เชื่อถือได้ หลักสูตรการฝึกอบรมและการรับรอง Java J2EE และ SOA ของ Edureka ได้รับการออกแบบมาเพื่อฝึกอบรมคุณสำหรับแนวคิด Java ทั้งหลักและขั้นสูงพร้อมกับกรอบงาน Java ต่างๆเช่น Hibernate & Spring
มีคำถามสำหรับเรา? โปรดระบุไว้ในส่วนความคิดเห็นของบล็อกนี้และเราจะติดต่อกลับโดยเร็วที่สุด