Quicksort Algorithm Implementation ใน Java

1. ภาพรวม

ในบทช่วยสอนนี้เราจะสำรวจอัลกอริทึม QuickSort โดยละเอียดโดยเน้นที่การใช้งาน Java

นอกจากนี้เราจะพูดถึงข้อดีและข้อเสียจากนั้นวิเคราะห์ความซับซ้อนของเวลา

2. QuickSort Algorithm

Quicksort เป็นอัลกอริธึมการเรียงลำดับซึ่งใช้ประโยชน์จากหลักการแบ่งและพิชิต มีความซับซ้อนO (n log n)โดยเฉลี่ยและเป็นหนึ่งในอัลกอริทึมการจัดเรียงที่ใช้กันมากที่สุดโดยเฉพาะสำหรับปริมาณข้อมูลขนาดใหญ่

สิ่งสำคัญคือต้องจำไว้ว่า Quicksort ไม่ใช่อัลกอริทึมที่เสถียร อัลกอริทึมการเรียงลำดับที่มีเสถียรภาพคืออัลกอริทึมที่องค์ประกอบที่มีค่าเดียวกันปรากฏในลำดับเดียวกันในเอาต์พุตที่เรียงลำดับตามที่ปรากฏในรายการอินพุต

รายการอินพุตถูกแบ่งออกเป็นสองรายการย่อยโดยองค์ประกอบที่เรียกว่าเดือย; รายการย่อยหนึ่งรายการที่มีองค์ประกอบน้อยกว่าเดือยและอีกรายการหนึ่งที่มีองค์ประกอบมากกว่าเดือย กระบวนการนี้ซ้ำสำหรับแต่ละรายการย่อย

สุดท้ายรายการย่อยที่เรียงลำดับทั้งหมดจะรวมเข้าด้วยกันเพื่อสร้างผลลัพธ์สุดท้าย

2.1. ขั้นตอนอัลกอริทึม

เราเลือกองค์ประกอบจากรายการที่เรียกว่า pivot เราจะใช้มันเพื่อแบ่งรายการออกเป็นสองรายการย่อย
เราเรียงลำดับองค์ประกอบทั้งหมดรอบ ๆ เดือยใหม่ - องค์ประกอบที่มีค่าน้อยกว่าจะถูกวางไว้ข้างหน้าและองค์ประกอบทั้งหมดที่มากกว่าเดือยตามหลัง หลังจากขั้นตอนนี้เดือยจะอยู่ในตำแหน่งสุดท้าย นี่คือขั้นตอนการแบ่งพาร์ติชันที่สำคัญ
เราใช้ขั้นตอนข้างต้นซ้ำ ๆ กับรายการย่อยทั้งทางซ้ายและขวาของเดือย

อย่างที่เราเห็นQuicksort เป็นอัลกอริธึมแบบวนซ้ำตามธรรมชาติเช่นเดียวกับวิธีการหารและพิชิตทุกประการ

มาดูตัวอย่างง่ายๆเพื่อทำความเข้าใจอัลกอริทึมนี้ให้ดียิ่งขึ้น

Arr[] = {5, 9, 4, 6, 5, 3}

สมมติว่าเราเลือก 5 เป็นเดือยสำหรับความเรียบง่าย
อันดับแรกเราจะใส่องค์ประกอบทั้งหมดที่น้อยกว่า 5 ในตำแหน่งแรกของอาร์เรย์: {3, 4, 5, 6, 5, 9}
จากนั้นเราจะทำซ้ำสำหรับอาร์เรย์ย่อยด้านซ้าย {3,4} โดยใช้ 3 เป็นเดือย
มีองค์ประกอบไม่น้อยกว่า 3
เราใช้ Quicksort กับอาร์เรย์ย่อยทางด้านขวาของเดือยเช่น {4}
อาร์เรย์ย่อยนี้ประกอบด้วยองค์ประกอบที่เรียงลำดับเพียงองค์ประกอบเดียว
เราดำเนินการต่อด้วยส่วนทางขวาของอาร์เรย์เดิม {6, 5, 9} จนกว่าเราจะได้อาร์เรย์ลำดับสุดท้าย

2.2. การเลือก Pivot ที่เหมาะสมที่สุด

จุดสำคัญใน QuickSort คือการเลือก Pivot ที่ดีที่สุด องค์ประกอบตรงกลางเป็นสิ่งที่ดีที่สุดเนื่องจากจะแบ่งรายการออกเป็นสองรายการย่อยเท่า ๆ กัน

แต่การค้นหาองค์ประกอบตรงกลางจากรายการที่ไม่เรียงลำดับเป็นเรื่องยากและใช้เวลานานนั่นคือเหตุผลที่เราใช้เป็นจุดหมุนองค์ประกอบแรกองค์ประกอบสุดท้ายค่ามัธยฐานหรือองค์ประกอบสุ่มอื่น ๆ

3. การใช้งานใน Java

วิธีแรกคือquickSort ()ซึ่งใช้เป็นพารามิเตอร์ที่จะเรียงลำดับอาร์เรย์ดัชนีแรกและดัชนีสุดท้าย ขั้นแรกให้ตรวจสอบดัชนีและดำเนินการต่อหากยังมีองค์ประกอบที่ต้องจัดเรียง

เราได้รับดัชนีของเดือยที่เรียงลำดับและใช้เพื่อเรียกเมธอดพาร์ติชัน ()แบบวนซ้ำด้วยพารามิเตอร์เดียวกันกับเมธอด quickSort ()แต่มีดัชนีต่างกัน:

public void quickSort(int arr[], int begin, int end) { if (begin < end) { int partitionIndex = partition(arr, begin, end); quickSort(arr, begin, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } }

ลองดำเนินการกับพาร์ทิชัน ()วิธีการ เพื่อความเรียบง่ายฟังก์ชันนี้จะใช้องค์ประกอบสุดท้ายเป็นเดือย จากนั้นตรวจสอบแต่ละองค์ประกอบและสลับก่อนเดือยว่าค่าน้อยกว่าหรือไม่

ในตอนท้ายของการแบ่งพาร์ติชันองค์ประกอบทั้งหมดจะน้อยลงจากนั้นเดือยจะอยู่ทางด้านซ้ายของมันและองค์ประกอบทั้งหมดที่มากกว่าเดือยจะอยู่ทางด้านขวาของมัน เดือยอยู่ที่ตำแหน่งที่จัดเรียงสุดท้ายและฟังก์ชันจะส่งกลับตำแหน่งนี้:

private int partition(int arr[], int begin, int end) { int pivot = arr[end]; int i = (begin-1); for (int j = begin; j < end; j++) { if (arr[j] <= pivot) { i++; int swapTemp = arr[i]; arr[i] = arr[j]; arr[j] = swapTemp; } } int swapTemp = arr[i+1]; arr[i+1] = arr[end]; arr[end] = swapTemp; return i+1; }

4. การวิเคราะห์อัลกอริทึม

4.1. ความซับซ้อนของเวลา

In the best case, the algorithm will divide the list into two equal size sub-lists. So, the first iteration of the full n-sized list needs O(n). Sorting the remaining two sub-lists with n/2 elements takes 2*O(n/2) each. As a result, the QuickSort algorithm has the complexity of O(n log n).

In the worst case, the algorithm will select only one element in each iteration, so O(n) + O(n-1) + … + O(1), which is equal to O(n2).

On the average QuickSort has O(n log n) complexity, making it suitable for big data volumes.

4.2. QuickSort vs MergeSort

Let's discuss in which cases we should choose QuickSort over MergeSort.

Although both Quicksort and Mergesort have an average time complexity of O(n log n), Quicksort is the preferred algorithm, as it has an O(log(n)) space complexity. Mergesort, on the other hand, requires O(n) extra storage, which makes it quite expensive for arrays.

Quicksort requires to access different indices for its operations, but this access is not directly possible in linked lists, as there are no continuous blocks; therefore to access an element we have to iterate through each node from the beginning of the linked list. Also, Mergesort is implemented without extra space for LinkedLists.

In such case, overhead increases for Quicksort and Mergesort is generally preferred.

5. Conclusion

Quicksort เป็นอัลกอริธึมการเรียงลำดับที่สวยงามซึ่งมีประโยชน์มากในกรณีส่วนใหญ่

โดยทั่วไปแล้วจะเป็นอัลกอริทึม "ในสถานที่" โดยมีความซับซ้อนของเวลาเฉลี่ยO (n log n)

ประเด็นที่น่าสนใจอีกประการหนึ่งที่ต้องกล่าวถึงคือวิธีArrays.sort ()ของ Java ใช้ Quicksort สำหรับการเรียงลำดับอาร์เรย์ของ primitives การใช้งานใช้สอง pivots และทำงานได้ดีกว่าโซลูชันง่ายๆของเรามากนั่นคือเหตุผลว่าทำไมสำหรับรหัสการผลิตจึงมักใช้วิธีไลบรารี

เช่นเคยรหัสสำหรับการใช้อัลกอริทึมนี้สามารถพบได้ในที่เก็บ GitHub ของเรา