การเรียงลำดับเป็นหนึ่งในประเภทพื้นฐานของกิจกรรมหรือการดำเนินการที่ทำกับออบเจ็กต์ แม้แต่ในวัยเด็ก เด็ก ๆ ก็ยังได้รับการสอนให้แยกแยะและพัฒนาความคิดของตนเอง คอมพิวเตอร์และโปรแกรมก็ไม่มีข้อยกเว้น มีอัลกอริธึมที่หลากหลายมาก ฉันขอแนะนำให้คุณดูว่ามันคืออะไรและทำงานอย่างไร นอกจากนี้ จะเกิดอะไรขึ้นหากวันหนึ่งคุณถูกถามเกี่ยวกับสิ่งเหล่านี้ในการสัมภาษณ์?
วัสดุ:
L совпадёт с
การแนะนำ
องค์ประกอบการเรียงลำดับเป็นหนึ่งในหมวดหมู่ของอัลกอริธึมที่นักพัฒนาซอฟต์แวร์ต้องคุ้นเคย หากกาลครั้งหนึ่งตอนที่ฉันเรียนอยู่ วิทยาการคอมพิวเตอร์ไม่ได้ถูกจริงจังนัก แต่ตอนนี้ในโรงเรียน พวกเขาควรจะสามารถใช้อัลกอริธึมการเรียงลำดับและทำความเข้าใจมันได้ อัลกอริธึมพื้นฐานซึ่งเป็นวิธีที่ง่ายที่สุดถูกนำไปใช้โดยใช้ลูfor
ป โดยปกติแล้ว ในการจัดเรียงคอลเลกชันขององค์ประกอบ เช่น อาร์เรย์ คุณจะต้องสำรวจคอลเลกชันนี้ด้วยวิธีใดวิธีหนึ่ง ตัวอย่างเช่น:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
คุณจะพูดอะไรเกี่ยวกับโค้ดชิ้นนี้ได้บ้าง? เรามีลูปที่เราเปลี่ยนค่าดัชนี ( int i
) จาก 0 เป็นองค์ประกอบสุดท้ายในอาร์เรย์ ที่จริงแล้ว เราเพียงแค่นำแต่ละองค์ประกอบในอาร์เรย์และพิมพ์เนื้อหาออกมา ยิ่งมีองค์ประกอบในอาร์เรย์มากเท่าไร โค้ดก็จะยิ่งใช้เวลานานในการดำเนินการมากขึ้นเท่านั้น นั่นคือ ถ้า n คือจำนวนองค์ประกอบ โดยที่ n=10 โปรแกรมจะใช้เวลาดำเนินการนานกว่า n=5 ถึง 2 เท่า เมื่อโปรแกรมของเรามีหนึ่งลูป เวลาดำเนินการจะเพิ่มขึ้นเป็นเส้นตรง ยิ่งมีองค์ประกอบมากเท่าใด การดำเนินการก็จะนานขึ้นเท่านั้น ปรากฎว่าอัลกอริทึมของโค้ดด้านบนทำงานในเวลาเชิงเส้น (n) ในกรณีเช่นนี้ “ความซับซ้อนของอัลกอริทึม” เรียกว่า O(n) สัญกรณ์นี้เรียกอีกอย่างว่า "big O" หรือ "พฤติกรรมเชิงเส้นกำกับ" แต่คุณสามารถจำ "ความซับซ้อนของอัลกอริทึม" ได้
การเรียงลำดับที่ง่ายที่สุด (Bubble Sort)
ดังนั้นเราจึงมีอาร์เรย์และสามารถวนซ้ำได้ ยอดเยี่ยม. ทีนี้ลองเรียงลำดับจากน้อยไปมาก สิ่งนี้มีความหมายสำหรับเราอย่างไร? ซึ่งหมายความว่าเมื่อมีสมาชิกสองตัว (เช่น a=6, b=5) เราต้องสลับ a และ b ถ้า a มากกว่า b (ถ้า a > b) สิ่งนี้มีความหมายอย่างไรสำหรับเราเมื่อทำงานกับคอลเลกชันตามดัชนี (เช่นเดียวกับกรณีของอาร์เรย์) ซึ่งหมายความว่าหากองค์ประกอบที่มีดัชนี a มากกว่าองค์ประกอบที่มีดัชนี b (array[a] > array[b]) องค์ประกอบดังกล่าวจะต้องถูกสลับ การเปลี่ยนสถานที่มักเรียกว่าการแลกเปลี่ยน มีหลายวิธีในการเปลี่ยนสถานที่ แต่เราใช้โค้ดที่เรียบง่าย ชัดเจน และจดจำง่าย:private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
ตอนนี้เราสามารถเขียนสิ่งต่อไปนี้:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
ดังที่เราเห็นองค์ประกอบต่างๆ ได้เปลี่ยนแปลงสถานที่ไปแล้ว เราเริ่มต้นด้วยองค์ประกอบเดียว เพราะว่า... ถ้าอาร์เรย์ประกอบด้วยองค์ประกอบเดียวเท่านั้น นิพจน์ 1 < 1 จะไม่คืนค่าเป็นจริง ดังนั้นเราจะป้องกันตัวเองจากกรณีของอาร์เรย์ที่มีองค์ประกอบเดียวหรือไม่มีองค์ประกอบเลย และโค้ดจะดูดีขึ้น แต่อาร์เรย์สุดท้ายของเราไม่ได้เรียงลำดับอยู่แล้ว เพราะ... ไม่สามารถจัดเรียงทุกคนในรอบเดียวได้ เราจะต้องเพิ่มอีกวงหนึ่งโดยเราจะทำการส่งทีละวงจนกว่าเราจะได้อาร์เรย์ที่เรียงลำดับ:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
ดังนั้นการเรียงลำดับครั้งแรกของเราจึงได้ผล เราวนซ้ำในวงรอบนอก ( while
) จนกว่าเราจะตัดสินใจว่าไม่จำเป็นต้องวนซ้ำอีกต่อไป ตามค่าเริ่มต้น ก่อนการวนซ้ำแต่ละครั้ง เราจะถือว่าอาร์เรย์ของเราได้รับการจัดเรียงแล้ว และเราไม่ต้องการวนซ้ำอีกต่อไป ดังนั้นเราจึงผ่านองค์ประกอบต่างๆ ตามลำดับและตรวจสอบสมมติฐานนี้ แต่หากองค์ประกอบไม่เป็นระเบียบ เราจะสลับองค์ประกอบและตระหนักว่าเราไม่แน่ใจว่าองค์ประกอบต่างๆ อยู่ในลำดับที่ถูกต้องแล้ว ดังนั้นเราจึงต้องการทำซ้ำอีกครั้งหนึ่ง ตัวอย่างเช่น [3, 5, 2] 5 มากกว่าสาม ทุกอย่างเรียบร้อยดี แต่ 2 น้อยกว่า 5 อย่างไรก็ตาม [3, 2, 5] ต้องผ่านอีกครั้งหนึ่ง เพราะ 3 > 2 และจำเป็นต้องเปลี่ยน เนื่องจากเราใช้การวนซ้ำภายในการวนซ้ำ ปรากฎว่าความซับซ้อนของอัลกอริทึมของเราเพิ่มขึ้น เมื่อมีสมาชิก n ตัว จะกลายเป็น n * n นั่นคือ O(n^2) ความซับซ้อนนี้เรียกว่ากำลังสอง ตามที่เราเข้าใจ เราไม่สามารถรู้ได้อย่างแน่ชัดว่าจะต้องทำซ้ำกี่ครั้ง ตัวบ่งชี้ความซับซ้อนของอัลกอริทึมมีจุดประสงค์ในการแสดงแนวโน้มของความซับซ้อนที่เพิ่มขึ้น ซึ่งเป็นกรณีที่เลวร้ายที่สุด เวลาทำงานจะเพิ่มขึ้นเท่าใดเมื่อจำนวนองค์ประกอบและการเปลี่ยนแปลง การเรียงลำดับแบบบับเบิ้ลเป็นหนึ่งในการเรียงลำดับที่ง่ายและไม่มีประสิทธิภาพมากที่สุด บางครั้งเรียกว่า "การเรียงลำดับที่โง่" วัสดุที่เกี่ยวข้อง:
เรียงลำดับการเลือก
อีกประเภทหนึ่งคือการเรียงลำดับการเลือก นอกจากนี้ยังมีความซับซ้อนแบบกำลังสอง แต่จะเพิ่มเติมในภายหลัง ดังนั้นความคิดจึงเป็นเรื่องง่าย แต่ละรอบจะเลือกองค์ประกอบที่เล็กที่สุดและย้ายไปยังจุดเริ่มต้น ในกรณีนี้ ให้เริ่มแต่ละรอบใหม่โดยเลื่อนไปทางขวา นั่นคือ รอบแรก - จากองค์ประกอบแรก รอบที่สอง - จากวินาที มันจะมีลักษณะเช่นนี้:int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
การเรียงลำดับนี้ไม่เสถียรเพราะว่า องค์ประกอบที่เหมือนกัน (จากมุมมองของคุณลักษณะที่เราจัดเรียงองค์ประกอบ) สามารถเปลี่ยนตำแหน่งได้ ตัวอย่างที่ดีมีให้ในบทความ Wikipedia: Sorting_by -selection วัสดุที่เกี่ยวข้อง:
การเรียงลำดับการแทรก
การเรียงลำดับการแทรกยังมีความซับซ้อนแบบกำลังสอง เนื่องจากเรามีการวนซ้ำภายในลูปอีกครั้ง มันแตกต่างจากการเรียงลำดับแบบเลือกอย่างไร? การเรียงลำดับนี้ "เสถียร" ซึ่งหมายความว่าองค์ประกอบที่เหมือนกันจะไม่เปลี่ยนลำดับ เหมือนกันในแง่ของลักษณะที่เราเรียงลำดับint[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Retrieve the value of the element
int value = array[left];
// Move through the elements that are before the pulled element
int i = left - 1;
for (; i >= 0; i--) {
// If a smaller value is pulled out, move the larger element further
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the pulled element is larger, stop
break;
}
}
// Insert the extracted value into the freed space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
วัสดุที่เกี่ยวข้อง:
การเรียงลำดับรถรับส่ง
ในบรรดาการเรียงลำดับแบบง่าย ๆ มีอีกอย่างหนึ่งคือการเรียงลำดับกระสวย แต่ฉันชอบความหลากหลายของรถรับส่งมากกว่า สำหรับฉันดูเหมือนว่าเราไม่ค่อยพูดถึงกระสวยอวกาศและกระสวยอวกาศก็วิ่งมากกว่า ดังนั้นจึงง่ายกว่าที่จะจินตนาการว่ากระสวยอวกาศถูกปล่อยสู่อวกาศอย่างไร นี่คือความเกี่ยวข้องกับอัลกอริทึมนี้ สาระสำคัญของอัลกอริทึมคืออะไร? สาระสำคัญของอัลกอริทึมคือเราวนซ้ำจากซ้ายไปขวา และเมื่อสลับองค์ประกอบ เราจะตรวจสอบองค์ประกอบอื่นๆ ทั้งหมดที่เหลืออยู่เพื่อดูว่าจำเป็นต้องสลับซ้ำหรือไม่int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
วัสดุที่เกี่ยวข้อง:
การเรียงลำดับเปลือก
การเรียงลำดับง่ายๆ อีกประการหนึ่งคือการเรียงลำดับแบบเชลล์ สาระสำคัญของมันคล้ายกับการเรียงลำดับแบบฟอง แต่การวนซ้ำแต่ละครั้งเรามีช่องว่างที่แตกต่างกันระหว่างองค์ประกอบที่จะเปรียบเทียบ การวนซ้ำแต่ละครั้งจะลดลงครึ่งหนึ่ง นี่คือตัวอย่างการใช้งาน:int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a difference between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right pointer until we can find one that
// there won't be enough space between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
วัสดุที่เกี่ยวข้อง:
ผสานการเรียงลำดับ
นอกเหนือจากการเรียงลำดับแบบง่ายที่ระบุไว้แล้ว ยังมีการเรียงลำดับที่ซับซ้อนอีกด้วย ตัวอย่างเช่น การเรียงลำดับแบบผสาน ประการแรก การเรียกซ้ำจะมาช่วยเรา ประการที่สอง ความซับซ้อนของเราจะไม่เป็นแบบกำลังสองอีกต่อไปอย่างที่เราคุ้นเคย ความซับซ้อนของอัลกอริทึมนี้คือลอการิทึม เขียนเป็น O(n log n) ลองทำสิ่งนี้กัน ขั้นแรก เรามาเขียนการเรียกแบบเรียกซ้ำไปยังวิธีการเรียงลำดับ:public static void mergeSort(int[] source, int left, int right) {
// Choose a separator, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Execute this function recursively for the two halves (if we can split(
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
ตอนนี้ เรามาเพิ่มการดำเนินการหลักลงไป นี่คือตัวอย่างวิธีการพิเศษของเราที่มีการนำไปปฏิบัติ:
public static void mergeSort(int[] source, int left, int right) {
// Choose a separator, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Execute this function recursively for the two halves (if we can split(
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the desired size
int[] buffer = new int[right - left + 1];
// Starting from the specified left border, go through each element
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use the delimeter to point to the element from the right side
// If delimeter > right, then there are no unadded elements left on the right side
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
เรามารันตัวอย่างโดยการเรียกmergeSort(array, 0, array.length-1)
. อย่างที่คุณเห็น สิ่งสำคัญอยู่ที่การที่เรารับอาร์เรย์ที่ระบุจุดเริ่มต้นและจุดสิ้นสุดของส่วนที่จะจัดเรียงเป็นอินพุต เมื่อการเรียงลำดับเริ่มต้น นี่คือจุดเริ่มต้นและจุดสิ้นสุดของอาร์เรย์ ต่อไปเราจะคำนวณตัวคั่น - ตำแหน่งของตัวแบ่ง หากตัวแบ่งสามารถแบ่งออกเป็น 2 ส่วน เราจะเรียกการเรียงลำดับแบบเรียกซ้ำสำหรับส่วนที่ตัวแบ่งแบ่งอาร์เรย์ เราเตรียมอาร์เรย์บัฟเฟอร์เพิ่มเติมซึ่งเราเลือกส่วนที่เรียงลำดับ ต่อไป เราวางเคอร์เซอร์ไว้ที่จุดเริ่มต้นของพื้นที่ที่จะเรียงลำดับ และเริ่มผ่านแต่ละองค์ประกอบของอาร์เรย์ว่างที่เราได้เตรียมไว้และเติมด้วยองค์ประกอบที่เล็กที่สุด หากองค์ประกอบที่เคอร์เซอร์ชี้ไปนั้นเล็กกว่าองค์ประกอบที่ตัวหารชี้ไป เราจะวางองค์ประกอบนี้ไว้ในอาร์เรย์บัฟเฟอร์แล้วเลื่อนเคอร์เซอร์ มิฉะนั้น เราจะวางองค์ประกอบที่ตัวคั่นชี้ไปลงในอาร์เรย์บัฟเฟอร์แล้วย้ายตัวคั่น ทันทีที่ตัวคั่นเกินขอบเขตของพื้นที่ที่เรียงลำดับหรือเราเติมอาร์เรย์ทั้งหมด ช่วงที่ระบุจะถือว่าเรียงลำดับแล้ว วัสดุที่เกี่ยวข้อง:
การนับการเรียงลำดับและการเรียงลำดับ Radix
อัลกอริธึมการเรียงลำดับที่น่าสนใจอีกอย่างหนึ่งคือการนับการเรียงลำดับ ความซับซ้อนของอัลกอริทึมในกรณีนี้คือ O(n+k) โดยที่ n คือจำนวนองค์ประกอบ และ k คือค่าสูงสุดขององค์ประกอบ มีปัญหาประการหนึ่งกับอัลกอริทึม: เราจำเป็นต้องทราบค่าต่ำสุดและค่าสูงสุดในอาร์เรย์ นี่คือตัวอย่างการใช้งานการเรียงลำดับการนับ:public static int[] countingSort(int[] theArray, int maxValue) {
// Array with "counters" ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// In the corresponding cell (index = value) we increase the counter
for (int num : theArray) {
numCounts[num]++;
}
// Prepare array for sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// go through the array with "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// go by the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
อย่างที่เราเข้าใจมันไม่สะดวกมากเมื่อเราต้องรู้ค่าต่ำสุดและสูงสุดล่วงหน้า แล้วก็มีอัลกอริธึมอื่น - Radix Sort ฉันจะนำเสนออัลกอริทึมที่นี่ด้วยสายตาเท่านั้น สำหรับการนำไปใช้ โปรดดูเอกสารประกอบ:
Java การเรียงลำดับด่วน
สำหรับของหวาน - หนึ่งในอัลกอริธึมที่มีชื่อเสียงที่สุด: การเรียงลำดับอย่างรวดเร็ว มันมีความซับซ้อนของอัลกอริธึม นั่นคือ เรามี O(n log n) การเรียงลำดับนี้เรียกอีกอย่างว่าการเรียงลำดับแบบ Hoare สิ่งที่น่าสนใจคือ Hoare เป็นผู้คิดค้นอัลกอริทึมนี้ระหว่างที่เขาอยู่ในสหภาพโซเวียต โดยเขาได้ศึกษาการแปลด้วยคอมพิวเตอร์ที่มหาวิทยาลัยมอสโก และกำลังพัฒนาหนังสือวลีภาษารัสเซีย-อังกฤษ อัลกอริธึมนี้ยังใช้ในการใช้งานที่ซับซ้อนมากขึ้นใน Arrays.sort ใน Java แล้ว Collections.sort ล่ะ? ฉันขอแนะนำให้คุณดูด้วยตัวคุณเองว่าพวกมันถูกจัดเรียงอย่างไร "ภายใต้ประทุน" ดังนั้นรหัส:public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right while element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker until element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check if you don't need to swap elements pointed to by markers
if (leftMarker <= rightMarker) {
// The left marker will only be less than the right marker if we have to swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Move markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively for parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
ทุกสิ่งที่นี่น่ากลัวมาก ดังนั้นเราจะเข้าใจมันเอง สำหรับแหล่งอาร์เรย์อินพุตint[]
เราตั้งค่าเครื่องหมายสองตัว ซ้าย (L) และขวา (R) เมื่อถูกเรียกเป็นครั้งแรก ค่าเหล่านี้จะจับคู่จุดเริ่มต้นและจุดสิ้นสุดของอาร์เรย์ ถัดไป กำหนดองค์ประกอบสนับสนุน หรือที่รู้จักในชื่อpivot
. หลังจากนี้ งานของเราคือย้ายค่าที่น้อยกว่า ไปpivot
ทางซ้ายpivot
และค่าที่ใหญ่กว่าไปทางขวา เมื่อต้องการทำเช่นนี้ ขั้นแรกให้เลื่อนตัวชี้L
จนกว่าเราจะพบค่าที่pivot
มากกว่า หากไม่พบค่าที่น้อยกว่าแสดงว่าpivot
. Потом двигаем указатель
R
пока не найдём меньшее, чем
pivot
meaning. Если меньшее meaning не нашли, то
R
совпадёт с
pivot
. Далее, если указатель
L
находится до указателя
R
or совпадает с ним, то пытаемся выполнить обмен элементов, если элемент
L
меньше, чем
R
. Далее
L
сдвигаем вправо на 1 позицию,
R
сдвигаем влево на одну позицию. Когда левый маркер
L
окажется за правым маркером
R
это будет означать, что обмен закончен, слева от
pivot
меньшие значения, справа от
pivot
— большие значения. После этого рекурсивно вызываем такую же сортировку для участков массива от начала сортируемого участка до правого маркера и от левого маркера до конца сортируемого участка. Почему от начала до правого? Потому что в конце итерации так и получится, что правый маркер сдвинется настолько, что станет границей части слева. Этот алгоритм более сложный, чем простая sorting, поэтому его лучше зарисовать. Возьмём белый лист бумаги, запишем: 4 2 6 7 3 , а
Pivot
по центру, т.е. число 6. Обведём его в круг. Под 4 напишем
L
, под 3 напишем
R
. 4 меньше чем 6, 2 меньше чем 6. Total,
L
переместился на положение
pivot
, т.к. по условию
L
не может уйти дальше, чем
pivot
. Напишем снова 4 2 6 7 3 , обведём 6 вкруг (
pivot
) и поставим под ним
L
. Теперь двигаем указатель
R
. 3 меньше чем 6, поэтому ставим маркер
R
на цифру 3. Так How 3 меньше, чем
pivot 6
выполняем
swap
, т.е. обмен. Запишем результат: 4 2 3 7 6 , обводим 6 вкруг, т.к. он по прежнему
pivot
. Указатель
L
на цифре 3, указатель
R
на цифре 6. Мы помним, что двигаем указатели до тех пор, пока
L
не зайдём за
R
.
L
двигаем на следующую цифру. Тут хочется разобрать два варианта: если бы предпоследняя цифра была 7 и если бы она была не 7, а 1.
Предпоследня цифра 1: Сдвинули указатель
L
на цифру 1, т.к. мы можем двигать
L
до тех пор, пока указатель
L
указывает на цифру, меньшую чем
pivot
. А вот
R
мы не можем сдвинуть с 6, т.к. R не мы можем двигать только если указатель
R
указывает на цифру, которая больше чем
pivot
.
swap
не делаем, т.к. 1 меньше 6. Записываем положение: 4 2 3 1 6, обводим
pivot 6
.
L
сдвигается на
pivot
и больше не двигается.
R
тоже не двигается. Обмен не производим. Сдвигаем
L
и
R
на одну позицию и подписываем цифру 1 маркером
R
, а
L
получается вне числа. Т.к.
L
вне числа — ничего не делаем, а вот часть 4 2 3 1 выписываем снова, т.к. это наша левая часть, меньшая, чем
pivot 6
. Выделяем новый
pivot
и начинаем всё снова )
Предпоследняя цифра 7: Сдвинули указать
L
на цифру 7, правый указатель не можем двигать, т.к. он уже указывает на pivot. т.к. 7 больше, чем
pivot
, то делаем
swap
. Запишем результат: 4 2 3 6 7, обводим 6 кружком, т.к. он
pivot
. Указатель
L
теперь сдвигается на цифру 7, а указатель
R
сдвигается на цифру 3. Часть от
L
до конца нет смысла сортировать, т.к. там всего 1 элемент, а вот часть от 4 до указателя
R
отправляем на сортировку. Выбираем
pivot
и начинаем всё снова ) Может на первый взгляд показаться, что если расставить много одинаковых с
pivot
значений, это сломает алгоритм, но это не так. Можно напридумывать каверзных вариантов и на бумажке убедиться, что всё правильно и подивиться, How такие простые действия предоставляют такой надёжный механизм. Единственный минус — такая sorting не является стабильной. Т.к. при выполнении обмена одинаковые элементы могут поменять свой порядок, если один из них встретился до
pivot
до того, How другой элемент попал в часть до
pivot
при помощи обмена. Материал:
GO TO FULL VERSION