การเรียงลำดับเป็นหนึ่งในการดำเนินการที่พบบ่อยและจำเป็นที่สุดในการเขียนโปรแกรม มันแสดงถึงการเรียงลำดับขององค์ประกอบบางชุดในลำดับเฉพาะ บทความนี้เกี่ยวกับวิธีการมาตรฐานสำหรับการเรียงลำดับอาร์เรย์ใน Java
สั้น ๆ เกี่ยวกับการเรียงลำดับ
ดังนั้นการเรียงลำดับคือการเรียงลำดับชุดข้อมูล ในกรณีของเราคืออาร์เรย์ วัตถุประสงค์ของการเรียงลำดับอาร์เรย์หรือโครงสร้างข้อมูลอื่นๆ คือเพื่อให้ง่ายต่อการค้นหา จัดการ หรือแยกวิเคราะห์ข้อมูลในคอลเลกชัน โปรแกรมเมอร์จำเป็นต้องเรียงลำดับบ่อยครั้งจนภาษาการเขียนโปรแกรมใดๆ มีวิธีการในตัวสำหรับการเรียงลำดับอาร์เรย์ รายการ และโครงสร้างข้อมูลที่เรียงลำดับอื่นๆ หากต้องการใช้วิธีการดังกล่าวให้โทรหาพวกเขา การดำเนินการนั้นง่ายขึ้นมากที่สุด โดยปกติแล้ว วิธีการในตัวจะได้รับการปรับให้เหมาะสมที่สุด ในกรณีส่วนใหญ่ การใช้สิ่งเหล่านี้สำหรับงานหรือโครงการของคุณเป็นความคิดที่ดี อย่างไรก็ตาม ในระหว่างการศึกษา โปรแกรมเมอร์เกือบทุกคนจำเป็นต้องใช้อัลกอริธึมการเรียงลำดับด้วยตนเอง ดังนั้นแบบฝึกหัดที่สมบูรณ์แบบเหล่านี้จะสอนให้คุณเข้าใจแก่นแท้ของการเขียนโปรแกรม นอกจากนี้ บางครั้งคุณจำเป็นต้องใช้วิธีการจัดเรียงที่ไม่ได้มาตรฐานในการทำงาน มีอัลกอริธึมการเรียงลำดับมากมาย มีจุดแข็งและจุดอ่อนขึ้นอยู่กับประเภทหรือขนาดของชุดข้อมูล อัลกอริธึมการเรียงลำดับมาตรฐาน ได้แก่ การเรียงลำดับแบบฟอง การเรียงลำดับการเลือก การเรียงลำดับการแทรก การเรียงลำดับแบบผสาน และการเรียงลำดับแบบด่วนวิธีการเรียงลำดับอาร์เรย์ใน Java: Arrays.sort
เริ่มจากสิ่งที่ง่ายที่สุดกันก่อน มีคนเขียนวิธีการเรียงลำดับอาร์เรย์ใน Java ให้เราแล้ว เมธอด นี้อยู่ใน คลาส Arraysโดยเฉพาะjava.util.Arrays คลาสนี้มีวิธีการต่างๆ สำหรับการทำงานกับอาร์เรย์ เช่น การเรียงลำดับและการค้นหา เมธอดArrays.sortมอบวิธีที่สะดวกในการจัดเรียงอาร์เรย์ใน Java ไม่ว่าจะประกอบด้วยสตริง จำนวนเต็ม หรือองค์ประกอบอื่นๆ ก็ตาม วิธีการ Arrays.sortใน Java มีหลายรูปแบบ ต่อไปนี้เป็นวิธีการเรียงลำดับที่ใช้โดยทั่วไปจาก คลาส Arrays :- Arrays.sort(Array) : ใช้เพื่อเรียงลำดับอาร์เรย์ของประเภทดั้งเดิมหรือวัตถุจากน้อยไปหามาก ใช้การเรียงลำดับองค์ประกอบตามธรรมชาติ
- Arrays.sort(Array, fromIndex, toIndex) : วิธีการจัดเรียงที่โอเวอร์โหลดนี้ช่วยให้คุณสามารถจัดเรียงเฉพาะส่วนของอาร์เรย์ที่ระบุโดยพารามิเตอร์ fromIndex และ toIndex
- Arrays.sort(Array, comparator) : อันนี้ใช้สำหรับการเรียงลำดับอาร์เรย์ของวัตถุโดยใช้ตัวเปรียบเทียบที่กำหนดเอง ตัวเปรียบเทียบจะกำหนดการเรียงลำดับขององค์ประกอบ
- Arrays.parallelSort(Array) : เวอร์ชันของเมธอดนี้จะเรียงลำดับArrayแบบขนาน โดยใช้หลายเธรดเพื่อประสิทธิภาพที่ดีขึ้น มีประโยชน์สำหรับการเรียงลำดับอาร์เรย์ขนาดใหญ่
- Arrays.parallelSort(Array, fromIndex, toIndex) : วิธีการ ParallelSort เวอร์ชันที่มีการโอเวอร์โหลดนี้ทำให้สามารถจัดเรียงช่วงขององค์ประกอบเฉพาะในArrayได้
ตัวอย่างที่ 1: การเรียงลำดับสตริง
สมมติว่าเรามีเครื่องดนตรีเครื่องสายหลายประเภท: "ไวโอลิน", "วิโอลา", "เชลโล" และ "ดับเบิลเบส" เราสามารถใช้ วิธี Array.sortเพื่อจัดเรียงตามตัวอักษร
import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
public static void main(String[] args) {
String[] instruments = {"violin", "viola", "cello", "double bass"};
Arrays.sort(instruments);
System.out.println("Sorted Instruments:");
for (String instrument : instruments) {
System.out.println(instrument);
}
}
}
ผลลัพธ์อยู่ที่นี่:
เครื่องดนตรีประเภท: เชลโล ดับเบิลเบส วิโอลา ไวโอลิน
ในโปรแกรมนี้ ก่อนอื่น เราจะนำเข้า คลาส java.util.Arraysเพื่อเข้าถึงเมธอดArray.sort จากนั้นเราสร้างอาร์เรย์สตริงที่เรียกว่าเครื่องดนตรีที่มีชื่อเครื่องดนตรี หลังจากนั้นเราจะเรียกArrays.sort(instruments ) ดังนั้นวิธีนี้จะได้รับอาร์เรย์ เรียงลำดับองค์ประกอบจากน้อยไปมากตามลำดับตามธรรมชาติ (ตัวอักษร) สุดท้าย เราก็วนซ้ำArray ที่เรียงลำดับ แล้วพิมพ์เครื่องดนตรีแต่ละชิ้นออกมา
ตัวอย่างที่ 2: การเรียงลำดับจำนวนเต็ม
ลองพิจารณาอีกตัวอย่างหนึ่งที่เราจัดเรียงอาร์เรย์ของจำนวนเต็มจากน้อยไปหามาก
import java.util.Arrays;
public class IntegerSortExample {
public static void main(String[] args) {
int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort
Arrays.sort(numbers);
System.out.println("Sorted Numbers:");
for (int number : numbers) {
System.out.println(number);
}
}
}
เอาท์พุท:
เรียงลำดับหมายเลข: 1 2 3 5 7 8
ที่นี่เราสร้างอาร์เรย์จำนวนเต็มที่เรียกว่าตัวเลขซึ่งมีองค์ประกอบที่ไม่ได้เรียงลำดับหลายรายการ ต่อไป เราเรียกArrays.sort(numbers)เพื่อเรียงลำดับอาร์เรย์จากน้อยไปหามาก โปรดทราบว่า เมธอด Array.sortจะปรับเปลี่ยนอาร์เรย์ดั้งเดิมแบบแทนที่ ดังนั้นหากต้องการเก็บArray ดั้งเดิม ไว้ ให้ทำสำเนาก่อนทำการเรียงลำดับ
ตัวอย่างที่ 3: ลำดับจากมากไปน้อย
แล้วการเรียงลำดับจากมากไปน้อยล่ะ? Arrays.sortยังเป็นเรื่องง่ายด้วย เพียงใช้ตัวเปรียบเทียบที่กำหนดเอง นี่คือตัวอย่าง:
import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
public static void main(String[] args) {
Integer[] numbers = {8, 2, 7, 3, 1, 5};
//sort an Array using Arrays.sort
Arrays.sort(numbers, Comparator.reverseOrder());
System.out.println("Sorted Numbers (Descending):");
for (int number : numbers) {
System.out.println(number);
}
}
}
ผลลัพธ์คือถัดไป:
เรียงลำดับตัวเลข (มากไปหาน้อย): 8 7 5 3 2 1
ตรงนี้ เรามีอาร์เรย์ของจำนวนเต็มชื่อตัวเลข การส่งComparator.reverseOrder()เป็นอาร์กิวเมนต์ที่สองไปยัง เมธอด Arrays.sortเราจะระบุตัวเปรียบเทียบแบบกำหนดเองที่เรียงลำดับองค์ประกอบจากมากไปน้อย Comparator.reverseOrder ()วิธีการส่งคืนตัวเปรียบเทียบที่จะกลับลำดับตามธรรมชาติขององค์ประกอบ โปรดทราบว่าที่นี่ เราใช้คลาส wrapper Integer แทนประเภท int ดั้งเดิม เนื่องจาก เมธอด Comparator.reverseOrder()ต้องใช้อ็อบเจ็กต์ หากคุณมีอาร์เรย์ของค่า int ดั้งเดิม คุณจะต้องแปลงค่าเหล่านั้นเป็นวัตถุจำนวนเต็ม ก่อนที่จะใช้วิธีนี้ การใช้ตัวเปรียบเทียบแบบกำหนดเองทำให้คุณสามารถจัดเรียงอาร์เรย์จากมากไปน้อยได้อย่างง่ายดายโดยใช้ วิธี Arrays.sortใน Java
อัลกอริธึมการเรียงลำดับแบบคลาสสิกที่เขียนเองใน Java
คุณเคยเห็น งานการเรียง ลำดับอาร์เรย์แล้วหากคุณกำลังศึกษาวิทยาการคอมพิวเตอร์อิสระหรือที่มหาวิทยาลัย มีอัลกอริธึมการเรียงลำดับที่แตกต่างกันมากมาย และเราจะนำอัลกอริธึมบางส่วนไปใช้ในบทความนี้ โดยทั่วไป ยิ่งนำอัลกอริธึมไปใช้ได้ง่ายขึ้นเท่าใด ประสิทธิภาพก็ยิ่งน้อยลงเท่านั้น โปรแกรมเมอร์วัดประสิทธิภาพของอัลกอริธึมโดยวัดตามเวลาการทำงานและหน่วยความจำที่ใช้ไปกับทรัพยากร นั่นไม่ใช่หัวข้อของบทความของเรา แต่เราพูดถึงว่าArrays.sortใน Java เป็นอัลกอริทึมที่มีประสิทธิภาพการเรียงลำดับฟอง
เริ่มจากอัลกอริทึมยอดนิยมในหมู่นักเรียนกันก่อน: Bubble sort ตรงไปตรงมา: อัลกอริธึมจะเปรียบเทียบสององค์ประกอบ แล้วสลับองค์ประกอบเหล่านั้นหากอยู่ในลำดับที่ไม่ถูกต้อง และทำต่อไปจนถึงจุดสิ้นสุดของอาร์เรย์ ปรากฎว่าองค์ประกอบที่มีขนาดเล็กกว่าจะ "ลอย" ไปที่ส่วนท้ายของArrayเช่น ฟองสบู่ที่ลอยขึ้นมาด้านบน
public class BubbleSort {
public static void bubbleSort(int[] myArray) {
int n = myArray.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (myArray[j] > myArray[j + 1]) {
// Swap myArray[j] and myArray[j+1]
int temp = myArray[j];
myArray[j] = myArray[j + 1];
myArray[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {18, 28, 2, 7, 90, 45};
System.out.println("Array before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
bubbleSort(arr);
System.out.println("\nArray after sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
ที่นี่วิธีการรับอาร์เรย์ของจำนวนเต็มเป็นอินพุต วงรอบนอกเปลี่ยนจาก 0 ถึง n-1 โดยที่ n คือขนาดของอาร์เรย์ วงในเปรียบเทียบองค์ประกอบที่อยู่ติดกัน หากคำสั่งซื้อไม่ถูกต้อง วิธีการจะสลับคำสั่งซื้อเหล่านั้น ขั้นตอนนี้จะถูกทำซ้ำจนกว่าอาร์เรย์ทั้งหมดจะถูกจัดเรียง นี่คือผลลัพธ์ของโปรแกรมของเรา:
อาร์เรย์ก่อนเรียงลำดับ: 18 28 2 7 90 45 อาร์เรย์หลังเรียงลำดับ: 2 7 18 28 45 90
เรียงลำดับการเลือก
อัลกอริธึมการเลือกจะเรียงลำดับอาร์เรย์โดยการค้นหาองค์ประกอบที่เล็กที่สุดจากส่วนที่ไม่ได้เรียงลำดับซ้ำแล้วซ้ำอีกและวางไว้ที่จุดเริ่มต้น มาเขียนเป็นภาษา Java:
public class SelectionSort {
public static void selectionSort(int[] myArray) {
int n = myArray.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// Find the index of the minimum element in the unsorted part of the array
for (int j = i + 1; j < n; j++) {
if (myArray[j] < myArray[minIndex]) {
minIndex = j;
}
}
// Swap the minimum element with the first element of the unsorted part
int temp = myArray[minIndex];
myArray[minIndex] = myArray[i];
myArray[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {18, 28, 45, 2, 90, 7};
System.out.println("Array before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
selectionSort(arr);
System.out.println("\nArray after sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
นี่คือผลลัพธ์ของโปรแกรม:
อาร์เรย์ก่อนการเรียงลำดับ: 18 28 45 2 90 7 อาร์เรย์หลังการเรียงลำดับ: 2 7 18 28 45 90
มาอธิบายทีละขั้นตอนกัน การวนซ้ำด้านนอกจะวนซ้ำจากจุดเริ่มต้นของArrayไปยังองค์ประกอบที่สองไปสุดท้าย (มากถึง n-1) ลูปนี้จะเลือกแต่ละองค์ประกอบทีละรายการเป็นจุดเริ่มต้นของส่วนที่ไม่ได้เรียงลำดับของArray ภายในลูปด้านนอก เราเริ่มต้นminIndexเป็นดัชนีปัจจุบันiโดยสมมติว่าเป็นดัชนีของรายการที่เล็กที่สุดในส่วนที่ไม่ได้เรียงลำดับของArray วงในเริ่มต้นจากi+1และไปจนถึงองค์ประกอบสุดท้ายของArray ค้นหาดัชนีของรายการที่เล็กที่สุดในส่วนที่ไม่ได้เรียงลำดับของ Array โดยการเปรียบเทียบแต่ละองค์ประกอบกับองค์ประกอบขั้นต่ำปัจจุบัน ( arr[minIndex] ) หากเราพบองค์ประกอบที่เล็กกว่าองค์ประกอบขั้นต่ำปัจจุบัน เราจะอัปเดตminIndexเป็นดัชนีขององค์ประกอบขั้นต่ำใหม่ หลังจากที่วงในเสร็จ สิ้นเราก็พบดัชนีขององค์ประกอบขั้นต่ำในส่วนที่ไม่มีการเรียงลำดับของArray จากนั้นเราจะสลับองค์ประกอบขั้นต่ำกับองค์ประกอบแรกของส่วนที่ไม่ได้เรียงลำดับโดยใช้อุณหภูมิตัวแปรชั่วคราว วงรอบนอกจะดำเนินต่อไปจนกว่าองค์ประกอบทั้งหมดจะถูกจัด เรียงโดยค่อยๆ ขยายส่วนที่เรียงลำดับของArray ในที่สุดอาร์เรย์ ที่เรียงลำดับ จะถูกพิมพ์ในวิธีการหลักก่อนและหลังการเรียกวิธีการ SelectSort
ผสานการเรียงลำดับ
Merge Sort เป็นอัลกอริธึมการแบ่งและพิชิตที่แบ่งอาร์เรย์ ย่อย ออกเป็นอาร์เรย์ย่อยที่มีขนาดเล็กลงซ้ำๆ แล้วเรียงลำดับ จากนั้นจึงรวมเข้าด้วยกันเพื่อให้ได้อาร์เรย์ที่เรียงลำดับ Merge Sort มีความเสถียรและใช้กันอย่างแพร่หลาย โดยเฉพาะอย่างยิ่งเมื่อจำเป็นต้องมีความเสถียรและรับประกันความซับซ้อนของเวลาที่แย่ที่สุด
public class MergeSort {
//Merge Sort array
public static void mergeSort(int[] myArray) {
if (myArray.length <= 1) {
return;
}
int mid = myArray.length / 2;
int[] left = new int[mid];
int[] right = new int[myArray.length - mid];
System.arraycopy(myArray, 0, left, 0, mid);
System.arraycopy(myArray, mid, right, 0, myArray.length - mid);
mergeSort(left);
mergeSort(right);
merge(myArray, left, right);
}
public static void merge(int[] arr, int[] left, int[] right) {
int i = 0; // index for left subarray
int j = 0; // index for right subarray
int k = 0; // index for merged array
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
public static void main(String[] args) {
int[] arr = {18, 2, 28, 7, 90, 45};
System.out.println("Array before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
mergeSort(arr);
System.out.println("\nArray after sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
ผลลัพธ์ที่นี่คือ:
อาร์เรย์ก่อนการเรียงลำดับ: 18 2 28 7 90 45 อาร์เรย์หลังการเรียงลำดับ: 2 7 18 28 45 90
มาอธิบายวิธีการทำงานให้ชัดเจนยิ่งขึ้น อัลกอริธึมจะแบ่งอาร์เรย์ออกเป็นสองส่วนแบบวนซ้ำจนกว่าจะถึงกรณีฐาน (เมื่ออาร์เรย์มีองค์ประกอบหนึ่งหรือศูนย์) จากนั้นจะรวมส่วนที่เรียงลำดับกลับเข้าด้วยกันโดยใช้วิธีการผสาน วิธีการผสานจะใช้อาร์เรย์สามชุดเป็นอินพุต: อาร์เรย์ ดั้งเดิม และอาร์เรย์ย่อยด้านซ้ายและขวา (ซ้ายและขวา) โดยจะเปรียบเทียบองค์ประกอบจากอาร์เรย์ย่อยด้านซ้ายและขวา และรวมองค์ประกอบเหล่านั้นเข้ากับอาร์เรย์ ดั้งเดิม ตามลำดับที่จัดเรียง
การเรียงลำดับการแทรก
การเรียงลำดับการแทรกทำงานโดยการแทรกองค์ประกอบจากส่วนที่ไม่ได้เรียงลำดับซ้ำๆ ลงในตำแหน่งที่ถูกต้องในส่วนที่เรียงลำดับ ทำงานได้ดีกับชุดข้อมูลขนาดเล็กหรือข้อมูลที่เกือบจะเรียงลำดับแล้ว
public class InsertionSort {
public static void insertionSort(int[] myArray) {
int n = myArray.length;
for (int i = 1; i < n; i++) {
int key = myArray[i];
int j = i - 1;
while (j >= 0 && myArray[j] > key) {
myArray[j + 1] = myArray[j];
j--;
}
myArray[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {18, 90, 7, 28, 45, 2};
System.out.println("Array before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
insertionSort(arr);
System.out.println("\nArray after sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
ผลลัพธ์ของโปรแกรมก็เหมือนกับปกติ:
อาร์เรย์ก่อนการเรียงลำดับ: 18 90 7 28 45 2 อาร์เรย์หลังการเรียงลำดับ: 2 7 18 28 45 90
ที่นี่ วิธีการ insertionSortใช้อัลกอริทึมการเรียงลำดับการแทรก มันวนซ้ำผ่านArrayและถือว่าแต่ละองค์ประกอบเป็นคีย์ โดยจะเปรียบเทียบคีย์กับองค์ประกอบที่อยู่ข้างหน้า และจะเลื่อนคีย์ไปข้างหน้าหนึ่งตำแหน่งหากคีย์นั้นใหญ่กว่า ซึ่งจะเป็นการเลื่อนองค์ประกอบต่างๆ อย่างมีประสิทธิภาพเพื่อให้มีที่ว่างสำหรับคีย์ในตำแหน่งที่ถูกต้อง
วงรอบนอกวนซ้ำจากองค์ประกอบที่สอง ( i = 1 ) ไปยังองค์ประกอบสุดท้ายของอาร์เรย์ วงในเริ่มต้นจากองค์ประกอบปัจจุบัน ( arr[i] ) และย้อนกลับ ( j = i - 1 ) จนกว่าจะพบตำแหน่งที่ถูกต้องสำหรับคีย์หรือไปถึงจุดเริ่มต้นของArray ภายในลูปด้านใน หากองค์ประกอบ ( arr[j] ) มากกว่าคีย์ องค์ประกอบนั้นจะถูกเลื่อนไปข้างหน้าหนึ่งตำแหน่ง ( arr[j + 1] = arr[j] ) เพื่อให้มีที่ว่างสำหรับคีย์ กระบวนการนี้จะดำเนินต่อไปจนกว่าจะพบตำแหน่งที่ถูกต้องของกุญแจ หลังจากที่วงในเสร็จสิ้น คีย์จะถูกวางในตำแหน่งที่ถูกต้อง ( arr[j + 1] = key ) ในวิธีการหลัก จะมีการสร้างและพิมพ์อาร์เรย์ตัวอย่างก่อนและหลังการเรียงลำดับโดยใช้วิธี insertionSort
จัดเรียงอย่างรวดเร็ว
Quick Sort เป็นอัลกอริธึมการแบ่งและพิชิตที่เลือกองค์ประกอบเดือยและแบ่งอาร์เรย์รอบเดือย ตามกฎแล้ว Quick Sort จะเร็วกว่า Merge Sort สำหรับชุดข้อมูลขนาดเล็กและขนาดกลาง เนื่องจากมีปัจจัยคงที่ต่ำ
public class QuickSort {
public static void quickSort(int[] myArray, int low, int high) {
if (low < high) {
int pivotIndex = partition(myArray, low, high);
quickSort(myArray, low, pivotIndex - 1);
quickSort(myArray, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {18, 28, 2, 90, 7, 45};
System.out.println("Array before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
quickSort(arr, 0, arr.length - 1);
System.out.println("\nArray after sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
ผลลัพธ์อยู่ที่นี่:
อาร์เรย์ก่อนการเรียงลำดับ: 18 28 2 90 7 45 อาร์เรย์หลังการเรียงลำดับ: 2 7 18 28 45 90
เรามีสามวิธีในการใช้การเรียงลำดับอย่างรวดเร็ว วิธี การQuickSortใช้พารามิเตอร์สามตัว ได้แก่อาร์เรย์ที่จะจัดเรียง ดัชนีต่ำของอาร์เรย์ย่อย และดัชนีสูงของอาร์เรย์ย่อย เริ่มแรกจะตรวจสอบว่าอาร์เรย์ย่อยมีมากกว่าหนึ่งองค์ประกอบหรือไม่ หากเป็นเช่นนั้น ระบบจะเลือกจุดหมุนโดยใช้วิธีการแบ่งพาร์ติชัน เรียงลำดับอาร์เรย์ย่อยก่อนจุดหมุนแบบวนซ้ำ และเรียงลำดับอาร์เรย์ย่อยหลังจุดหมุนแบบวนซ้ำ วิธีการแบ่งพาร์ติชั่นจะเลือกเดือยเป็นองค์ประกอบสุดท้ายของอาร์เรย์ย่อย ( arr[high] ) โดยจะตั้งค่าดัชนีพาร์ติชัน (i) เป็นดัชนีต่ำลบ 1 จากนั้นจะวนซ้ำจากดัชนีต่ำไปเป็นดัชนีสูง - 1 และตรวจสอบว่าแต่ละองค์ประกอบน้อยกว่าหรือเท่ากับเดือยหรือไม่ หากเป็นเช่นนั้น ระบบจะสลับองค์ประกอบกับองค์ประกอบที่ดัชนีพาร์ติชัน (i) และเพิ่มดัชนีพาร์ติชัน สุดท้ายจะสลับองค์ประกอบเดือยกับองค์ประกอบที่ดัชนีพาร์ติชัน + 1 และส่งคืนดัชนีพาร์ติชัน วิธีการแบ่งพาร์ติชั่นจะเลือกเดือยเป็นองค์ประกอบสุดท้ายของอาร์เรย์ย่อย ( arr[high] ) โดยจะตั้งค่าดัชนีพาร์ติชัน (i) เป็นดัชนีต่ำลบ 1 จากนั้นวนซ้ำจากดัชนีต่ำไปเป็นดัชนีสูง - 1 และตรวจสอบว่าแต่ละรายการมีขนาดเล็กกว่าหรือเท่ากับเดือยหรือไม่ หากเป็นเช่นนั้น ระบบจะสลับองค์ประกอบกับองค์ประกอบที่ดัชนีพาร์ติชัน (i) และเพิ่มดัชนีพาร์ติชัน สุดท้ายจะสลับองค์ประกอบเดือยกับองค์ประกอบที่ดัชนีพาร์ติชัน + 1 และส่งคืนดัชนีพาร์ติชัน วิธีการสลับเป็นวิธีการอรรถประโยชน์ที่ใช้ในการสลับสององค์ประกอบในArray ใน วิธีการ หลักจะมีการสร้างและพิมพ์อาร์เรย์ตัวอย่างก่อนและหลังการเรียงลำดับโดยใช้วิธี QuickSort
GO TO FULL VERSION