ผสานการเรียงลำดับ: อัลกอริธึม ข้อดี และคุณสมบัติ

2024 ผู้เขียน: Angel Austin | [email protected]. แก้ไขล่าสุด: 2024-02-02 14:52

การจัดเรียงแบบผสานเป็นหนึ่งในอัลกอริธึมวิทยาการคอมพิวเตอร์ขั้นพื้นฐาน ซึ่งคิดค้นขึ้นในปี 1945 โดยนักคณิตศาสตร์ผู้ยิ่งใหญ่ จอห์น ฟอน นอยมันน์ ขณะเข้าร่วมโครงการแมนฮัตตัน นอยมันน์ต้องเผชิญกับความจำเป็นในการประมวลผลข้อมูลจำนวนมหาศาลอย่างมีประสิทธิภาพ วิธีที่เขาพัฒนาขึ้นนั้นใช้หลักการ "แบ่งแยกแล้วพิชิต" ซึ่งช่วยลดเวลาในการทำงานลงได้อย่างมาก

หลักการและการใช้อัลกอริทึม

วิธีการจัดเรียงแบบผสานจะใช้ในปัญหาของโครงสร้างการเรียงลำดับที่สั่งการเข้าถึงองค์ประกอบ เช่น อาร์เรย์ รายการ สตรีม

ระหว่างการประมวลผล บล็อกข้อมูลเริ่มต้นจะถูกแบ่งออกเป็นส่วนประกอบขนาดเล็ก มากถึงหนึ่งองค์ประกอบ ซึ่งอันที่จริงแล้วเป็นรายการที่จัดเรียงแล้ว จากนั้นจึงประกอบกลับในลำดับที่ถูกต้อง

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

วิธีการนี้สามารถใช้เพื่อจัดลำดับประเภทข้อมูลที่เปรียบเทียบได้ เช่น ตัวเลขหรือสตริง

รวมเรียงแปลง

เพื่อทำความเข้าใจอัลกอริธึม เรามาเริ่มการวิเคราะห์กันตั้งแต่ปลาย - จากกลไกของการรวมบล็อกที่จัดเรียง

ลองนึกภาพว่าเรามีตัวเลขสองแถวเรียงกันแบบใดแบบหนึ่งที่ต้องรวมเข้าด้วยกันเพื่อไม่ให้การเรียงลำดับเสียหาย เพื่อความง่าย เราจะเรียงลำดับตัวเลขจากน้อยไปมาก

ตัวอย่างเบื้องต้น: อาร์เรย์ทั้งสองประกอบด้วยองค์ประกอบละหนึ่งรายการ

int arr1={31}; int arr2={18};


ในการรวม คุณต้องนำองค์ประกอบศูนย์ของอาร์เรย์แรก (อย่าลืมว่าการนับเริ่มต้นจากศูนย์) และองค์ประกอบศูนย์ของอาร์เรย์ที่สอง เหล่านี้คือ 31 และ 18 ตามลำดับ ตามเงื่อนไขการเรียงลำดับ ตัวเลข 18 ควรมาก่อนเนื่องจากน้อยกว่า เพียงแค่ใส่ตัวเลขในลำดับที่ถูกต้อง:


int ผลลัพธ์={18, 31};

มาดูตัวอย่างที่ซับซ้อนกว่านี้กัน โดยที่แต่ละอาร์เรย์ประกอบด้วยหลายองค์ประกอบ:

int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};


อัลกอริธึมการผสานจะประกอบด้วยการเปรียบเทียบองค์ประกอบที่เล็กกว่าและจัดวางองค์ประกอบเหล่านั้นในอาร์เรย์ที่เป็นผลลัพธ์ในลำดับที่ถูกต้อง ในการติดตามดัชนีปัจจุบัน เรามาแนะนำสองตัวแปร - index1 และ index2 เริ่มแรก เราตั้งค่าให้เป็นศูนย์ เนื่องจากอาร์เรย์ถูกจัดเรียง และองค์ประกอบที่เล็กที่สุดอยู่ที่จุดเริ่มต้น

int index1=0; int ดัชนี2=0;


มาเขียนขั้นตอนการรวมทั้งหมดทีละขั้นตอน:








นำองค์ประกอบที่มี index1 จากอาร์เรย์ arr1 และองค์ประกอบที่มี index2 จากอาร์เรย์ arr2.
เปรียบเทียบ เลือกตัวที่เล็กที่สุดแล้วใส่ลงไปอาร์เรย์ผลลัพธ์
เพิ่มดัชนีปัจจุบันขององค์ประกอบที่มีขนาดเล็กลง 1.
ต่อจากก้าวแรก






โคจรรอบแรก จะเป็นแบบนี้

index1=0; ดัชนี2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; ดัชนี1++; ผลลัพธ์[0]=arr1[0]; // ผลลัพธ์=[2]


รอบที่สอง:

ดัชนี1=1; ดัชนี2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; ดัชนี2++; ผลลัพธ์[1]=arr2[0]; // ผลลัพธ์=[2, 5]


ที่สาม:

ดัชนี1=1; ดัชนี2=1; arr1[1]=17; arr2 [1]=6; arr1[1] > arr2[1]; ดัชนี2++; ผลลัพธ์[2]=arr2[1]; // ผลลัพธ์=[2, 5, 6]









และอื่นๆ จนกว่าผลลัพธ์จะเป็นอาร์เรย์ที่จัดเรียงอย่างสมบูรณ์: {2, 5, 6, 17, 21, 19, 30, 45}.
ปัญหาบางอย่างอาจเกิดขึ้นได้หากรวมอาร์เรย์ที่มีความยาวต่างกันเข้าด้วยกัน จะเกิดอะไรขึ้นถ้าหนึ่งในดัชนีปัจจุบันถึงองค์ประกอบสุดท้าย และยังมีสมาชิกเหลืออยู่ในอาร์เรย์ที่สอง?

int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 ขั้นตอน index1=0, index2=0; 1 2 ผลลัพธ์={1, 2}; // 3 ขั้นตอน index1=1, index2=1; 4 < 5 ผลลัพธ์={1, 2, 4}; ///4 ขั้นตอน index1=2, index2=1 ??


ตัวแปร index1 ถึงค่า 2 แล้ว แต่อาร์เรย์ arr1 ไม่มีองค์ประกอบที่มีดัชนีนั้น ทุกอย่างง่ายที่นี่: เพียงโอนองค์ประกอบที่เหลือของอาร์เรย์ที่สองไปยังอาร์เรย์ที่เป็นผลลัพธ์ รักษาลำดับไว้


ผลลัพธ์={1, 2, 4, 5, 6, 7, 9};

สถานการณ์นี้บ่งบอกความต้องการของเราจับคู่ดัชนีตรวจสอบปัจจุบันกับความยาวของอาร์เรย์ที่จะถูกรวม
รวมโครงร่างสำหรับลำดับที่สั่ง (A และ B) ที่มีความยาวต่างกัน:

หากความยาวของทั้งสองลำดับมากกว่า 0 ให้เปรียบเทียบ A[0] กับ B[0] และย้ายลำดับที่เล็กกว่าไปยังบัฟเฟอร์
หากความยาวของหนึ่งในลำดับเป็น 0 ให้นำองค์ประกอบที่เหลือของลำดับที่สองและย้ายไปที่ส่วนท้ายของบัฟเฟอร์โดยไม่เปลี่ยนลำดับ


การดำเนินการของด่านที่สอง
ตัวอย่างการรวมอาร์เรย์ที่เรียงลำดับสองอันใน Java แสดงไว้ด้านล่าง








int a1=int ใหม่ {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=ใหม่ int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=ใหม่ int[a1.length + a2.length]; int i=0, j=0; สำหรับ (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=ก; เจ++; } else if (j > a2.length-1) { int a=a1; a3[k]=ก; ผม++; } อื่น ๆ ถ้า (a1 < a2[j]) { int a=a1; a3[k]=ก; ผม++; } อื่น ๆ { int b=a2[j]; a3[k]=ข; เจ++; } }


ที่นี่:

a1 และ a2 เป็นอาร์เรย์ที่จัดเรียงดั้งเดิมที่จะรวม
a3 – อาร์เรย์สุดท้าย;
i และ j เป็นดัชนีขององค์ประกอบปัจจุบันสำหรับอาร์เรย์ a1 และ a2.

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






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


// อาร์เรย์ดั้งเดิม {34, 95, 10, 2, 102, 70}; // แยกครั้งแรก {34, 95, 10} และ {2, 102, 70}; // แยกที่สอง {34} และ {95, 10} และ {2} และ {102, 70}

ผลลัพท์ที่ประกอบด้วย 1-2 องค์ประกอบนั้นง่ายต่อการจัดเรียง
หลังจากนั้น คุณต้องรวมอาร์เรย์ขนาดเล็กที่จัดเรียงไว้แล้วเป็นคู่ รักษาลำดับของสมาชิกที่เราได้เรียนรู้ไปแล้ว






การดำเนินการของด่านแรก
การแบ่งพาร์ติชั่นแบบเรียกซ้ำของอาร์เรย์แสดงอยู่ด้านล่าง

โมฆะ mergeSort(T a, เริ่มต้นแบบยาว, จบแบบยาว) { แยกแบบยาว; ถ้า(เริ่ม < จบ) { split=(เริ่ม + สิ้นสุด)/2; mergeSort(a, เริ่ม, แยก); mergeSort(a, split+1, เสร็จสิ้น); ผสาน (a, เริ่ม, แยก, เสร็จสิ้น); } }


เกิดอะไรขึ้นในรหัสนี้:



ฟังก์ชัน mergeSort ได้รับอาร์เรย์เริ่มต้น

a

และเส้นขอบด้านซ้ายและขวาของภูมิภาคที่จะจัดเรียง (ดัชนีเริ่มต้นและ

finish).



หากความยาวของส่วนนี้มากกว่าหนึ่ง (

start < จบ

) จะถูกแบ่งออกเป็นสองส่วน (โดยดัชนี

split) และแต่ละรายการจะถูกจัดเรียงแบบเรียกซ้ำ



ในการเรียกฟังก์ชันแบบเรียกซ้ำทางด้านซ้าย ดัชนีเริ่มต้นของพล็อตและดัชนี

split

จะถูกส่งต่อ สำหรับอันที่ถูกต้อง ตามลำดับ จุดเริ่มต้นจะเป็น

(split + 1) และจุดสิ้นสุดจะเป็นดัชนีสุดท้ายของส่วนดั้งเดิม



Function

merge

ได้รับคำสั่งสองลำดับ (

a[start]…a[split]

and

a[split +1]…a[finish]) และรวมเข้าด้วยกันในลำดับการจัดเรียง


กลไกของฟังก์ชันการรวมถูกกล่าวถึงข้างต้น

รูปแบบทั่วไปของอัลกอริทึม
วิธีการจัดเรียงแบบผสานประกอบด้วยสองขั้นตอนใหญ่:

แยกอาร์เรย์ดั้งเดิมที่ไม่ได้จัดเรียงออกเป็นชิ้นเล็กๆ
เก็บเป็นคู่ตามกฎการเรียงลำดับ

งานใหญ่และซับซ้อนถูกแบ่งออกเป็นงานง่าย ๆ มากมาย ซึ่งจะแก้ไขตามลำดับซึ่งนำไปสู่ผลลัพธ์ที่ต้องการ






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

การนำอัลกอริทึมไปใช้
การเรียงลำดับการผสาน Pascal แสดงอยู่ด้านล่าง


ขั้นตอน MergeSort(ชื่อ: string; var f: text); Var a1, a2, s, i, j, kol, tmp: จำนวนเต็ม; f1, f2: ข้อความ; b: บูลีน Begincol:=0; กำหนด(f, ชื่อ); รีเซ็ต(f); แม้ว่าจะไม่ใช่ EOF(f) ก็จะเริ่มอ่าน (f, a1); inc(col); จบ; ปิด (f); กำหนด (f1, '{ชื่อของไฟล์เสริมที่ 1}'); กำหนด (f2, '{ชื่อของไฟล์เสริมที่ 2}'); s:=1; ในขณะที่ (s<kol) เริ่มรีเซ็ต (f); เขียนใหม่(f1); เขียนใหม่(f2); สำหรับ i:=1 ถึง kol div 2 เริ่มอ่าน (f, a1); เขียน(f1, a1, ' '); จบ; ถ้า (kol div 2) mod s0 ให้เริ่ม tmp:=kol div 2; ในขณะที่ tmp mod s0 เริ่มอ่าน (f, a1); เขียน(f1, a1, ' '); อิงค์ (tmp); จบ; จบ; ในขณะที่ไม่ใช่ EOF(f) ให้เริ่มอ่าน (f, a2); เขียน(f2, a2, ' '); จบ; ปิด (f); ปิด(f1); ปิด(f2); เขียนใหม่ (f); รีเซ็ต(f1); รีเซ็ต(f2); อ่าน(f1, a1); อ่าน (f2, a2); ในขณะที่ (ไม่ใช่ EOF(f1)) และ (ไม่ใช่ EOF(f2)) เริ่มต้น i:=0; เจ:=0; b:=จริง; ในขณะที่ (b) และ (ไม่ใช่ EOF(f1)) และ (ไม่ใช่ EOF(f2)) เริ่มต้นขึ้น หาก (a1<a2) เริ่มต้นขึ้นเขียน(f, a1, ' '); อ่าน(f1, a1); อิงค์ (i); สิ้นสุด อื่น เริ่ม เขียน (f, a2, ' '); อ่าน (f2, a2); อิงค์(j); จบ; ถ้า (i=s) หรือ (j=s) แล้ว b:=false; จบ; ถ้าไม่ใช่ b ให้เริ่มในขณะที่ (i<s) และ (ไม่ใช่ EOF(f1)) เริ่มเขียน (f, a1, ' '); อ่าน(f1, a1); อิงค์ (i); จบ; ในขณะที่ (j<s) และ (ไม่ใช่ EOF(f2)) เริ่มเขียน (f, a2, ' '); อ่าน (f2, a2); อิงค์(j); จบ; จบ; จบ; ในขณะที่ไม่ใช่ EOF(f1) ให้เริ่ม tmp:=a1; อ่าน(f1, a1); ถ้าไม่ใช่ EOF(f1) ให้เขียน (f, tmp, ' ') อย่างอื่นเขียน (f, tmp); จบ; ในขณะที่ไม่ใช่ EOF(f2) ให้เริ่ม tmp:=a2; อ่าน (f2, a2); ถ้าไม่ใช่ EOF(f2) ให้เขียน (f, tmp, ' ') อย่างอื่นเขียน (f, tmp); จบ; ปิด (f); ปิด(f1); ปิด(f2); s:=s2; จบ; ลบ(f1); ลบ(f2); จบ;

ภาพ การทำงานของอัลกอริทึมมีลักษณะดังนี้ (ลำดับบน - แบบไม่เรียงลำดับ ล่าง - เรียงลำดับ)






การจัดเรียงข้อมูลภายนอก
บ่อยครั้งที่จำเป็นต้องจัดเรียงข้อมูลบางอย่างที่อยู่ในหน่วยความจำภายนอกของคอมพิวเตอร์ ในบางกรณีอาจมีขนาดที่น่าประทับใจและไม่สามารถวางไว้ใน RAM เพื่อให้เข้าถึงได้ง่ายขึ้น ในกรณีดังกล่าว จะใช้วิธีคัดแยกจากภายนอก
ความจำเป็นในการเข้าถึงสื่อภายนอกลดประสิทธิภาพของเวลาในการประมวลผล
ความซับซ้อนของงานคืออัลกอริธึมสามารถเข้าถึงองค์ประกอบหนึ่งของสตรีมข้อมูลในแต่ละครั้งเท่านั้น และในกรณีนี้ ผลลัพธ์ที่ดีที่สุดวิธีหนึ่งจะแสดงโดยวิธีการจัดเรียงแบบผสาน ซึ่งสามารถเปรียบเทียบองค์ประกอบของสองไฟล์ตามลำดับได้
กำลังอ่านข้อมูลจากแหล่งที่มาภายนอก การประมวลผลและการเขียนไปยังไฟล์สุดท้ายจะดำเนินการในบล็อกที่เรียงลำดับ (ชุด) ตามวิธีการทำงานกับขนาดของซีรีย์ที่สั่งซื้อ การเรียงลำดับมีสองประเภท: การรวมที่เรียบง่ายและเป็นธรรมชาติ






รวมอย่างง่าย
ด้วยการรวมอย่างง่าย ความยาวของซีรีย์ได้รับการแก้ไข
ดังนั้น ในไฟล์ต้นฉบับที่ไม่ได้เรียงลำดับ ทุกชุดประกอบด้วยองค์ประกอบเดียว หลังจากขั้นตอนแรก ขนาดจะเพิ่มขึ้นเป็นสองขนาด ถัดไป - 4, 8, 16 และอื่นๆ
มันทำงานแบบนี้:

ไฟล์ต้นฉบับ (f) แบ่งออกเป็นสองไฟล์เสริม - f1, f2.
รวมเข้าด้วยกันเป็นไฟล์เดียวอีกครั้ง (f) แต่ในขณะเดียวกันองค์ประกอบทั้งหมดจะถูกเปรียบเทียบเป็นคู่และคู่ของรูปแบบ ขนาดชุดในขั้นตอนนี้กลายเป็นสอง
ขั้นตอนที่ 1 ซ้ำแล้วซ้ำอีก
ขั้นตอนที่ 2 ซ้ำแล้วซ้ำอีก แต่ 2s ที่สั่งซื้อแล้วจะถูกรวมเป็น 4s ที่เรียงลำดับ
วนซ้ำไปเรื่อย ๆ เพิ่มชุดในการวนซ้ำแต่ละครั้ง จนกว่าจะจัดเรียงไฟล์ทั้งหมด

คุณทราบได้อย่างไรว่าการจัดเรียงภายนอกด้วยการผสานอย่างง่ายเสร็จสมบูรณ์

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

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

ฟิวชั่นธรรมชาติ
วิธีนี้ไม่จำกัดความยาวซีรี่ย์แต่เลือกได้มากที่สุด
อัลกอริทึมการเรียงลำดับ:

กำลังอ่านลำดับเริ่มต้นจากไฟล์ f. องค์ประกอบที่ได้รับครั้งแรกถูกเขียนลงในไฟล์ f1.
หากรายการถัดไปตรงตามเงื่อนไขการเรียงลำดับ จะถูกเขียนที่นั่น ถ้าไม่ ให้เขียนไปยังไฟล์เสริมที่สอง f2.
ด้วยวิธีนี้ ระเบียนทั้งหมดของไฟล์ต้นฉบับจะถูกแจกจ่าย และลำดับที่จัดลำดับจะเกิดขึ้นใน f1 ซึ่งกำหนดขนาดปัจจุบันของซีรีส์
รวมไฟล์ f1 และ f2 แล้ว
วนซ้ำ

เนื่องจากขนาดไม่คงที่ของซีรีส์ จึงจำเป็นต้องทำเครื่องหมายจุดสิ้นสุดของลำดับด้วยอักขระพิเศษ ดังนั้นเมื่อรวมกัน จำนวนการเปรียบเทียบจึงเพิ่มขึ้น นอกจากนี้ ขนาดของไฟล์เสริมอาจใกล้เคียงกับขนาดของต้นฉบับ
โดยเฉลี่ยแล้ว การผสานตามธรรมชาติจะมีประสิทธิภาพมากกว่าการผสานอย่างง่ายด้วยการจัดเรียงภายนอก

คุณสมบัติของอัลกอริทึม
เมื่อเปรียบเทียบค่าที่เหมือนกันสองค่า วิธีการจะคงลำดับเดิมไว้ นั่นคือค่าคงที่
กระบวนการจัดเรียงสามารถแบ่งออกเป็นหลายเธรดได้สำเร็จ





วิดีโอแสดงให้เห็นอย่างชัดเจนถึงการทำงานของอัลกอริธึมการจัดเรียงการผสาน