อัลกอริทึม QuickSort ใน Javaต้นฉบับ
Quick Sort คืออะไร?
จัดเรียงด่วน อัลกอริทึมใช้แนวทาง Divide and Conquer โดยแบ่งองค์ประกอบออกเป็นส่วนย่อยๆ ตามเงื่อนไขบางประการ และดำเนินการเรียงลำดับส่วนย่อยๆ ที่แบ่งออกไป
อัลกอริทึม Quick Sort เป็นหนึ่งในอัลกอริทึมที่ใช้และได้รับความนิยมมากที่สุดในภาษาการเขียนโปรแกรมใดๆ แต่ถ้าคุณเป็น Javaนักพัฒนาสคริปต์ คุณอาจเคยได้ยินเกี่ยวกับ เรียงลำดับ () ซึ่งมีอยู่แล้วใน Javaสคริปต์ จากนั้นคุณอาจคิดว่าอัลกอริทึมการเรียงลำดับด่วนนี้มีความจำเป็นอย่างไร เพื่อทำความเข้าใจเรื่องนี้ ก่อนอื่นเราต้องรู้ว่าการเรียงลำดับคืออะไร และการเรียงลำดับเริ่มต้นคืออะไร Javaต้นฉบับ
การเรียงลำดับคืออะไร?
การจัดเรียงไม่ใช่สิ่งอื่นใดนอกจากการจัดเรียงองค์ประกอบต่างๆ ในลำดับที่เราต้องการ คุณอาจเคยพบสิ่งนี้ในสมัยเรียนหรือมหาวิทยาลัย เช่นเดียวกับการจัดเรียงตัวเลขจากน้อยไปมาก (จากน้อยไปมาก) หรือจากมากไปน้อย (จากมากไปน้อย) นี่คือสิ่งที่เราเคยเห็นมาจนถึงทุกวันนี้ และเรียกว่าการจัดเรียง
การเรียงลำดับเริ่มต้น Javaต้นฉบับ
ดังกล่าวก่อนหน้านี้, Javaสคริปต์มี เรียงลำดับ ()- ให้เรายกตัวอย่างที่มีองค์ประกอบอาร์เรย์ไม่กี่รายการ เช่น [5,3,7,6,2,9] และต้องการเรียงลำดับองค์ประกอบอาร์เรย์นี้จากน้อยไปหามาก เพียงแค่โทร เรียงลำดับ () ในอาร์เรย์รายการและจะเรียงลำดับองค์ประกอบอาร์เรย์จากน้อยไปหามาก
รหัส:
var items = [5,3,7,6,2,9]; console.log(items.sort()); //prints [2, 3, 5, 6, 7, 9]
เหตุผลที่เลือก Quick sort แทน default sort() in คืออะไร Javaต้นฉบับ
แม้ว่า sort() จะให้ผลลัพธ์ที่เราต้องการ แต่ปัญหาอยู่ที่วิธีการเรียงลำดับองค์ประกอบอาร์เรย์ การเรียงลำดับเริ่มต้น () ใน Javaการใช้สคริปต์ การเรียงลำดับการแทรก by เครื่องยนต์ V8 ของ Chrome และ ผสานการจัดเรียง by Mozilla Firefox และ Safari.
แต่อย่างอื่นไม่เหมาะหากคุณต้องการจัดเรียงองค์ประกอบจำนวนมาก วิธีแก้ไขคือใช้ Quick sort สำหรับชุดข้อมูลขนาดใหญ่
ดังนั้น เพื่อให้เข้าใจอย่างถ่องแท้ คุณจำเป็นต้องทราบวิธีการทำงานของการเรียงลำดับด่วน และให้เราดูรายละเอียดในขั้นตอนนี้
การเรียงลำดับด่วนคืออะไร?
เรียงลำดับอย่างรวดเร็วดังต่อไปนี้ หารและพิชิต อัลกอริทึม คือการแบ่งองค์ประกอบออกเป็นส่วนย่อยๆ ตามเงื่อนไขบางประการ และดำเนินการเรียงลำดับส่วนย่อยๆ ที่แบ่งออกไปนั้น ดังนั้นจึงใช้ได้ดีกับชุดข้อมูลขนาดใหญ่ ดังนั้น ต่อไปนี้คือขั้นตอนการทำงานของการเรียงลำดับด่วนแบบง่ายๆ
- ขั้นแรกเลือกองค์ประกอบที่จะเรียกว่าเป็น เดือย ธาตุ.
- ถัดไป เปรียบเทียบองค์ประกอบอาร์เรย์ทั้งหมดกับองค์ประกอบเดือยที่เลือก และจัดเรียงในลักษณะที่องค์ประกอบที่น้อยกว่าองค์ประกอบเดือยอยู่ทางซ้าย และมากกว่าองค์ประกอบเดือยอยู่ทางขวา
- สุดท้าย ให้ดำเนินการแบบเดียวกันกับองค์ประกอบด้านซ้ายและด้านขวาขององค์ประกอบจุดหมุน
นั่นคือโครงร่างพื้นฐานของการเรียงลำดับด่วน ต่อไปนี้เป็นขั้นตอนที่ต้องปฏิบัติตามทีละขั้นตอนเพื่อดำเนินการเรียงลำดับด่วน
QuickSort ทำงานอย่างไร
- ขั้นแรกให้หา "หมุน" องค์ประกอบในอาร์เรย์
- เริ่มตัวชี้ซ้ายที่องค์ประกอบแรกของอาร์เรย์
- เริ่มตัวชี้ขวาที่องค์ประกอบสุดท้ายของอาร์เรย์
- เปรียบเทียบองค์ประกอบที่ชี้กับตัวชี้ด้านซ้าย และหากน้อยกว่าองค์ประกอบสาระสำคัญ ให้เลื่อนตัวชี้ซ้ายไปทางขวา (เพิ่ม 1 ไปที่ดัชนีด้านซ้าย) ทำต่อไปจนกว่าองค์ประกอบด้านซ้ายจะมากกว่าหรือเท่ากับองค์ประกอบเดือย
- เปรียบเทียบองค์ประกอบที่ชี้กับตัวชี้ทางขวา และหากมีค่ามากกว่าองค์ประกอบสาระสำคัญ ให้เลื่อนตัวชี้ทางขวาไปทางซ้าย (ลบ 1 ไปยังดัชนีทางขวา) ทำต่อไปจนกว่าองค์ประกอบทางด้านขวาจะน้อยกว่าหรือเท่ากับองค์ประกอบเดือย
- ตรวจสอบว่าตัวชี้ด้านซ้ายน้อยกว่าหรือเท่ากับตัวชี้ด้านขวา จากนั้นสลับองค์ประกอบในตำแหน่งของตัวชี้เหล่านี้
- เพิ่มตัวชี้ทางซ้ายและลดตัวชี้ทางขวา
- หากดัชนีของตัวชี้ด้านซ้ายยังน้อยกว่าดัชนีของตัวชี้ด้านขวา ให้ทำซ้ำขั้นตอนนี้ มิฉะนั้นจะส่งคืนดัชนีของตัวชี้ด้านซ้าย
ให้เราดูขั้นตอนเหล่านี้พร้อมตัวอย่าง ให้เราพิจารณาอาร์เรย์ขององค์ประกอบที่เราต้องเรียงลำดับคือ [5,3,7,6,2,9]
กำหนดองค์ประกอบ Pivot
แต่ก่อนที่จะดำเนินการเรียงลำดับด่วน การเลือกองค์ประกอบสาระสำคัญจะมีบทบาทสำคัญ หากคุณเลือกองค์ประกอบแรกเป็นองค์ประกอบ Pivot องค์ประกอบดังกล่าวจะให้ประสิทธิภาพที่แย่ที่สุดในอาร์เรย์ที่เรียงลำดับ ดังนั้นจึงแนะนำให้เลือกองค์ประกอบตรงกลาง (ความยาวของอาร์เรย์หารด้วย 2) เป็นองค์ประกอบเดือยเสมอ และเราก็ทำเช่นเดียวกัน
ต่อไปนี้เป็นขั้นตอนในการดำเนินการเรียงลำดับด่วนที่แสดงพร้อมกับตัวอย่าง [5,3,7,6,2,9]
ขั้นตอนที่ 1: กำหนดเดือยเป็นองค์ประกอบตรงกลาง ดังนั้น, 7 เป็นองค์ประกอบหลัก
ขั้นตอนที่ 2: เริ่มตัวชี้ซ้ายและขวาเป็นองค์ประกอบแรกและสุดท้ายของอาร์เรย์ตามลำดับ ดังนั้นตัวชี้ซ้ายจึงชี้ไปที่ 5 ที่ดัชนี 0 และตัวชี้ทางขวาชี้ไปที่ 9 ที่ดัชนี 5
ขั้นตอนที่ 3: เปรียบเทียบองค์ประกอบที่ตัวชี้ซ้ายกับองค์ประกอบจุดหมุน เนื่องจาก 5 < 6 ให้เลื่อนตัวชี้ซ้ายไปทางขวาเพื่อระบุดัชนี 1
ขั้นตอนที่ 4: ตอนนี้ 3 < 6 ยังคงอยู่ ดังนั้นให้เลื่อนตัวชี้ซ้ายไปที่ดัชนีอีกตัวหนึ่งทางขวา ตอนนี้ 7 > 6 หยุดเพิ่มตัวชี้ซ้าย และตอนนี้ตัวชี้ซ้ายจะอยู่ที่ดัชนี 2
ขั้นตอนที่ 5: ตอนนี้ ให้เปรียบเทียบค่าที่ตัวชี้ด้านขวากับองค์ประกอบเดือย ตั้งแต่ 9 > 6 ให้เลื่อนตัวชี้ขวาไปทางซ้าย ขณะนี้ 2 < 6 หยุดเลื่อนตัวชี้ด้านขวา
ขั้นตอนที่ 6: สลับค่าทั้งสองค่าที่อยู่ทางซ้ายและขวาของพอยน์เตอร์ระหว่างกัน
ขั้นตอนที่ 7: ย้ายพอยน์เตอร์ทั้งสองตัวอีกหนึ่งขั้น
ขั้นตอนที่ 8: เนื่องจาก 6 = 6 ให้เลื่อนพอยน์เตอร์ไปอีกขั้นหนึ่งแล้วหยุดเมื่อพอยน์เตอร์ซ้ายข้ามพอยน์เตอร์ทางขวาและส่งกลับดัชนีของพอยน์เตอร์ทางซ้าย
ดังนั้น ตามแนวทางข้างต้น เราจำเป็นต้องเขียนโค้ดสำหรับการสลับองค์ประกอบและการแบ่งพาร์ติชันอาร์เรย์ตามที่กล่าวไว้ในขั้นตอนข้างต้น
โค้ดสำหรับสลับเลขสองตัว Javaต้นฉบับ
function swap(items, leftIndex, rightIndex){ var temp = items[leftIndex]; items[leftIndex] = items[rightIndex]; items[rightIndex] = temp; }
รหัสสำหรับดำเนินการพาร์ติชันตามที่กล่าวไว้ในขั้นตอนข้างต้น
function partition(items, left, right) { var pivot = items[Math.floor((right + left) / 2)], //middle element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] < pivot) { i++; } while (items[j] > pivot) { j--; } if (i <= j) { swap(items, i, j); //swap two elements i++; j--; } } return i; }
ดำเนินการแบบเรียกซ้ำ
เมื่อคุณทำตามขั้นตอนข้างต้นแล้ว ดัชนีของตัวชี้ด้านซ้ายจะถูกส่งกลับ และเราจำเป็นต้องใช้สิ่งนั้นเพื่อแบ่งอาร์เรย์และดำเนินการเรียงลำดับด่วนในส่วนนั้น ดังนั้นจึงเรียกว่าอัลกอริทึมแบ่งและพิชิต
ดังนั้น การเรียงลำดับด่วนจะดำเนินการจนกว่าองค์ประกอบทั้งหมดในอาร์เรย์ด้านซ้ายและอาร์เรย์ด้านขวาจะถูกจัดเรียง
หมายเหตุ การเรียงลำดับอย่างรวดเร็วจะดำเนินการในอาร์เรย์เดียวกัน และไม่มีการสร้างอาร์เรย์ใหม่ในกระบวนการนี้
เราจึงต้องเรียกสิ่งนี้ว่า พาร์ติชัน () อธิบายไว้ข้างต้นและตามที่เราแบ่ง แถว ในส่วนต่างๆ นี่คือโค้ดที่คุณใช้
function quickSort(items, left, right) { var index; if (items.length > 1) { index = partition(items, left, right); //index returned from partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(items, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(items, index, right); } } return items; } // first call to quick sort var result = quickSort(items, 0, items.length - 1);
กรอกโค้ดการเรียงลำดับด่วนให้สมบูรณ์
var items = [5,3,7,6,2,9]; function swap(items, leftIndex, rightIndex){ var temp = items[leftIndex]; items[leftIndex] = items[rightIndex]; items[rightIndex] = temp; } function partition(items, left, right) { var pivot = items[Math.floor((right + left) / 2)], //middle element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] < pivot) { i++; } while (items[j] > pivot) { j--; } if (i <= j) { swap(items, i, j); //sawpping two elements i++; j--; } } return i; } function quickSort(items, left, right) { var index; if (items.length > 1) { index = partition(items, left, right); //index returned from partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(items, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(items, index, right); } } return items; } // first call to quick sort var sortedArray = quickSort(items, 0, items.length - 1); console.log(sortedArray); //prints [2,3,5,6,7,9]
หมายเหตุ: การเรียงลำดับอย่างรวดเร็วทำงานตามความซับซ้อนของเวลาของ O(nlogn)