การเรียงลำดับโดยตรงค. การเรียงลำดับโดยตรง ประสิทธิภาพของอัลกอริธึมฟีดฟอร์เวิร์ด

วิธีนี้ใช้กันอย่างแพร่หลายในการเล่นไพ่ องค์ประกอบ (การ์ด) จะถูกแบ่งทางจิตออกเป็นลำดับที่ "พร้อม" แล้ว A 1 , A 2 , …, A i -1 และส่วน "ที่เหลือ" (ไม่เรียงลำดับ): A i , A i +1 , …, A N .

สาระสำคัญของวิธีการคือในแต่ละขั้นตอนที่ i (เริ่มจาก i = 2) องค์ประกอบที่ i จะถูกลบออกจากส่วนที่ไม่ได้เรียงลำดับและวางไว้ในส่วน "พร้อม" และจะถูกแทรกลงในตำแหน่งที่ถูกต้อง

อัลกอริธึมข้อความของวิธีการ:

1. จุดเริ่มต้น.

2. วนซ้ำจนกระทั่งฉันได้ค่าตั้งแต่ 2 ถึง N
ขั้นตอน = 1:

a) วางองค์ประกอบ i-th (A(i)) ไว้ในเซลล์ A(0);

b) กำหนด j = -1 นั่นคือ j เท่ากับจำนวนขององค์ประกอบที่อยู่ทางด้านซ้ายของเรื่อง (i-th) และยืนอยู่ในลำดับ "พร้อม"

c) ถ้า A(0) ≥ A(j) ให้วางองค์ประกอบ A(0) ในเซลล์ A(j+1) หรือวางองค์ประกอบ A(j) ในเซลล์ A(j+1) ให้ลดค่า ของ j ทีละอันแล้วทำขั้นตอน c อีกครั้ง

ในรูป รูปที่ 1 แสดงบล็อกไดอะแกรมของการเรียงลำดับโดยใช้วิธีการรวมโดยตรง

วิธีการทำงานดังนี้: ที่ขั้นตอน i-th (เริ่มจาก i = 2) องค์ประกอบ i-th จะถูกวางไว้ในเซลล์อิสระ (เช่น A(0)) องค์ประกอบนี้จะถูกเปรียบเทียบกับองค์ประกอบที่อยู่ในส่วนที่ "เสร็จสิ้น" ทางด้านซ้าย หากองค์ประกอบ A(0) มีขนาดเล็ก ดังนั้นองค์ประกอบที่เปรียบเทียบ (องค์ประกอบที่ j) จะถูกเลื่อนไปทางขวาหนึ่งตำแหน่ง หลังจากนั้นจึงนำองค์ประกอบถัดไปมาเปรียบเทียบ ถ้าองค์ประกอบ A(0) ไม่เล็กระหว่างการเปรียบเทียบ องค์ประกอบนั้นจะถูกวางไว้ในตำแหน่งทันทีหลังจากองค์ประกอบที่ถูกเปรียบเทียบ

ข้าว. 1. แผนผังลำดับงานของการเรียงลำดับโดยใช้วิธีการรวมโดยตรง

ในรูป รูปที่ 2 แสดงตัวอย่างการดำเนินการเรียงลำดับโดยใช้วิธีการรวมโดยตรง

ลำดับดั้งเดิม
	เอ (0)
ฉัน = 2
ฉัน = 3
ฉัน = 4
ฉัน = 5
ฉัน = 6
ฉัน = 7
ฉัน = 8
ผลลัพธ์

ข้าว. 2. ตัวอย่างการเรียงลำดับการรวมโดยตรง

การเรียงลำดับโดยตรงจะเหมาะสมกว่าสำหรับกรณีที่ข้อมูลที่เรียงลำดับมาถึงตามลำดับ (ทีละรายการ)

การเรียงลำดับการเลือกโดยตรง

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

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

อัลกอริธึมข้อความของวิธีการ:

1. จุดเริ่มต้น.

2. วนซ้ำจนกระทั่ง i มีค่าตั้งแต่ 1 ถึง N – 1
ขั้นตอน = 1:

ก) วางองค์ประกอบปัจจุบัน (i-th) ไว้ในเซลล์หน่วยความจำบางส่วน (X) และจำหมายเลขซีเรียล (i) ขององค์ประกอบปัจจุบัน (ในตัวแปร K)

b) ดำเนินการวนซ้ำในขณะที่ j มีค่าตั้งแต่ i + 1 (นั่นคือจากองค์ประกอบถัดจาก i) ถึง N ขั้นตอน = +1:

เนื้อความของลูป: ถ้า X > A(j) ให้วางองค์ประกอบ A(j) ในเซลล์ X และจำหมายเลขของมันไว้ในเซลล์ K;

c) กำหนดให้ A(K) = A(i) และ A(i) = X

ในรูป รูปที่ 3 แสดงตัวอย่างการดำเนินการเรียงลำดับโดยใช้วิธีการเลือกโดยตรง

ข้าว. 3. ตัวอย่างการเรียงลำดับการเลือกโดยตรง

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

27 412 71 81 59 14 273 87.

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

การวนซ้ำ 0

เรียงลำดับ 27

การทำซ้ำ 1ไม่เรียงลำดับ 412 71 81 59 14 273 87

เรียงลำดับแล้ว 27,412

ทำซ้ำ 2ไม่เรียงลำดับ 71 81 59 14 273 87

เรียงลำดับ 27 71 412

ทำซ้ำ 3ไม่เรียงลำดับ 81 59 14 273 87

เรียงลำดับ 27 71 81 412

ทำซ้ำ 4ไม่เรียงลำดับ 59 14 273 87

เรียงลำดับ 27 59 71 81 412

ทำซ้ำ 5ไม่เรียงลำดับ 14,273 87

เรียงลำดับ 14 27 59 71 81 412

ทำซ้ำ 6ไม่เรียงลำดับ 273 87

เรียงลำดับ 14 27 59 71 81 273 412

ทำซ้ำ 7ไม่เรียงลำดับ 87

เรียงลำดับ 14 27 59 71 81 87 273 412

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

อัลกอริทึม SIS(การเรียงลำดับการรวมโดยตรง) เรียงลำดับจำนวนเต็ม I(1), I(2), . - - ,ฉัน (N) ตามลำดับจากน้อยไปมาก

ขั้นตอนที่ 1[การทำซ้ำหลัก]

สำหรับเจ← 2 ถึงเอ็น ทำผ่านขั้นตอนที่ 4 อ.อ ;และหยุด.

ขั้นตอนที่ 2[เลือกจำนวนเต็มถัดไป] ชุด K←ฉัน(เจ); และ L←J−1.

ขั้นตอนที่ 3[เปรียบเทียบกับจำนวนเต็มเรียงลำดับ] ในขณะที่เค

และL≥1 ทำการตั้งค่าฉัน(L+1) ← ฉัน(ล); และ L←L−1 อ.อ.

ขั้นตอนที่ 4[เปิดใช้งาน] ชุดฉัน(L+1)←เค.

เรียงลำดับด่วน:อัลกอริธึมการเรียงลำดับพร้อมเวลาทำงานเฉลี่ย O(N ln N)

สาเหตุหลักที่ทำให้อัลกอริทึม SIS ทำงานช้าก็คือการเปรียบเทียบและการแลกเปลี่ยนระหว่างคีย์ทั้งหมดตามลำดับ 1, 2, . - - และเอ็นเกิดขึ้นกับคู่ขององค์ประกอบข้างเคียง วิธีการนี้ต้องใช้ขนาดค่อนข้างใหญ่

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

สาย 38 08 16 06 79 76 57 24 56 02 58 48 04 70 45 47แอ็กชัน

1 38 47 ลดลง เจ

5 04 38 แลกเปลี่ยน

6 08 38 เพิ่มขึ้น ผม

10 38 79 แลก

14 02 38 แลกเปลี่ยน

15 76 38 เพิ่มขึ้น ผม,>

16 38 76 แลกเปลี่ยน

17 38 56 ลดลง เจ

19 24 38 แลก

20 57 38 เพิ่มขึ้น ผม,>

21 38 57 แลกลดลง

22 04 08 16 06 02 24 38 57 56 76 58 48 79 70 45 47

(1 2 3 4 5 6) 7 (8 9 10 11 12 13 14 15 16)

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

K. Hoor คิดค้นและนำแนวคิดนี้ไปใช้อย่างมีประสิทธิภาพมาก (อัลกอริธึม QUICKSORT) ซึ่งช่วยลดเวลาการทำงานโดยเฉลี่ยของอัลกอริธึม SIS จากลำดับ O(N 2) ไปจนถึงลำดับ O(N ln N) ให้เราอธิบายอัลกอริทึมนี้ด้วยตัวอย่างต่อไปนี้

สมมติว่าเราต้องการเรียงลำดับตัวเลขจากแถวแรกในรูป 15. เรามาเริ่มกันด้วยสมมติฐานที่ว่า อันดับแรกคีย์ในลำดับนี้ (38) ทำหน้าที่เป็นการประมาณคีย์ที่ดีซึ่งในที่สุดจะปรากฏตรงกลางของลำดับที่เรียงลำดับ เราใช้ค่านี้เป็นองค์ประกอบนำหน้า โดยสัมพันธ์กับคีย์ที่สามารถสลับได้ และดำเนินการต่อดังนี้ เราติดตั้งพอยน์เตอร์สองตัว I และ J ซึ่งฉันเริ่มนับจากด้านซ้าย (I=1) และ J เริ่มจากด้านซ้ายในลำดับ (J=N) การเปรียบเทียบ ฉันและ และเจ- ถ้า และฉัน ≤a เจให้ตั้งค่า J←J−1 และทำการเปรียบเทียบต่อไปนี้ มาต่อกัน ลดเจจนกว่าเราจะไปถึง ฉัน >เจงั้นเรามาเปลี่ยนสถานที่กันเถอะ ฉัน ↔a เจ(รูปที่ 15 บรรทัดที่ 5 การแลกเปลี่ยนคีย์ 38 และ 04) ตั้งค่า I←I+1 และดำเนินการต่อ เพิ่มขึ้นฉันจนกว่าเราจะได้ ฉัน >เจหลังจากการแลกเปลี่ยนครั้งถัดไป (บรรทัดที่ 10, 79↔38) เราจะลด J อีกครั้ง สลับระหว่างการลด J และการเพิ่ม I เราจะดำเนินการขั้นตอนนี้ต่อจากปลายทั้งสองของลำดับไปที่ "ตรงกลาง" จนกระทั่งเราได้ I=J

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

สามารถใช้ขั้นตอนเดียวกันนี้กับลำดับย่อยด้านซ้ายและขวาเพื่อเรียงลำดับลำดับทั้งหมดในที่สุด บรรทัดสุดท้าย (หมายเลข 22) ของรูปที่ 15 แสดงว่าเมื่อได้รับ I=J แล้ว I=7 จากนั้นขั้นตอนจะถูกนำมาใช้อีกครั้งกับลำดับย่อย (1,6) และ (8,16)

ลักษณะการเรียกซ้ำของอัลกอริธึมแนะนำว่าควรวางดัชนีขององค์ประกอบด้านนอกสุดของลำดับย่อยที่ใหญ่กว่าของสองลำดับย่อยที่ไม่ได้เรียงลำดับ (8,16) ควรวางบนสแต็ก จากนั้นจึงดำเนินการเรียงลำดับลำดับย่อยที่เล็กกว่า (1,6)

ในบรรทัดที่ 4 ในรูปที่ 15 หมายเลข 04 ได้ย้ายไปที่ตำแหน่ง 2 และลำดับย่อย (1,1) และ (3,6) อาจถูกจัดเรียง เนื่องจาก (1,1) ได้รับการจัดเรียงแล้ว (หมายเลข 02) เราจึงเรียงลำดับ (3,6) ซึ่งจะนำไปสู่บรรทัดที่ 6 ซึ่งจะต้องเรียงลำดับ (3,4) และ (6,6) ในบรรทัดที่ 7 ลำดับย่อย (1,6) จะถูกจัดเรียง ตอนนี้เราแตก (8,16) ออกจากสแต็กและเริ่มเรียงลำดับลำดับย่อยนี้ บรรทัดที่ 13 มีลำดับย่อย (8,11) และ (13,16) ที่ต้องเรียงลำดับ เราใส่ (13,16) ลงบนสแต็ก เรียงลำดับ (8,11) ฯลฯ ในบรรทัดที่ 20 ลำดับทั้งหมดจะถูกจัดเรียง

ก่อนที่จะอธิบายอัลกอริทึม QUICKSORT อย่างเป็นทางการ เราต้องแสดงให้เห็นว่ามันทำงานอย่างไรก่อน เราใช้สแต็ก [ LEFT (K), RIGHT (K) ] เพื่อจดจำดัชนีขององค์ประกอบซ้ายสุดและขวาสุดของลำดับย่อยที่ยังไม่ได้เรียงลำดับ เนื่องจากลำดับย่อยแบบสั้นจะถูกจัดเรียงเร็วกว่าโดยอัลกอริธึมทั่วไป อัลกอริธึม QUICKSORT จึงมีพารามิเตอร์อินพุต M ที่กำหนดว่าลำดับย่อยจะต้องสั้นเพียงใดเพื่อที่จะเรียงลำดับด้วยวิธีทั่วไป เพื่อจุดประสงค์นี้ เราจึงใช้การเรียงลำดับแบบรวมอย่างง่าย (SIS)

ค้นหา

ตอนนี้เรามาดูการตรวจสอบปัญหาพื้นฐานบางประการที่เกี่ยวข้องกับการดึงข้อมูลจากโครงสร้างข้อมูล เช่นเดียวกับในส่วนก่อนหน้าเกี่ยวกับการเรียงลำดับ เราจะถือว่าข้อมูลทั้งหมดถูกจัดเก็บไว้ในบันทึกที่สามารถระบุได้ด้วยค่าคีย์ เช่น บันทึก R i สอดคล้องกับค่าคีย์ที่แสดงโดย K i

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

สมมติว่าเราไปตรงกลางของไฟล์แล้วพบคีย์ K i อยู่ที่นั่น ลองเปรียบเทียบ K และ K i กัน หาก K=K i แสดงว่าพบบันทึกที่ต้องการ ถ้าเค<К i ,то ключ К должен находиться в части файла, предшествующей К i (если запись с ключом К вообще существует) . Аналогично, если К i <К, то дальнейший поиск следует вести в части файла, следующей за К i . Если повторять эту процедуру проверки ключа К i из середины непросмотренной части файла, тогда каждое безуспешное сравнение К с К i будет исключать из рассмотрения приблизительно половину непросмотренной части.

ผังงานของขั้นตอนนี้เรียกว่า การค้นหาแบบไบนารีดังแสดงในรูปที่ 16

อัลกอริทึม BSEARCH (การค้นหาแบบไบนารี) ค้นหาบันทึกด้วยคีย์ K ในไฟล์ที่มีบันทึก N≥2 โดยคีย์จะเรียงลำดับจากน้อยไปหามาก K 1<К 2 …<К N .

ขั้นตอนที่ 0[การเริ่มต้น] ชุดครั้งแรก←1 ; LAST← N. (FIRST และ LAST เป็นตัวชี้ไปยังคีย์แรกและคีย์สุดท้ายในส่วนของไฟล์ที่ยังไม่ได้เปิดดู)

ขั้นตอนที่ 1[วงหลัก] ในขณะที่สุดท้าย≥FIRST ทำผ่านขั้นตอนที่ 4 อ.อ.

ขั้นตอนที่ 2[ได้รับกุญแจกลาง] ชุด I←|_(แรก + สุดท้าย)/2_| .(K i คือคีย์ที่อยู่ตรงกลางหรือทางด้านซ้ายของตรงกลางของส่วนของไฟล์ที่ยังไม่ได้เปิดดู)

ขั้นตอนที่ 3[ตรวจสอบความสำเร็จ] ถ้า K=K ฉัน แล้วพิมพ์ "สำเร็จแล้วคีย์เท่ากับ K I"; และหยุด ฟิ

ขั้นตอนที่ 4[การเปรียบเทียบ] ถ้าเค < เค ฉัน จากนั้นตั้งค่าสุดท้าย←I-1 ตั้งค่าอย่างอื่นที่หนึ่ง←ฉัน+1 ฟิ

ขั้นตอนที่ 5[การค้นหาล้มเหลว] พิมพ์ "ไม่สำเร็จ"; และหยุด.

อัลกอริธึม BSEARCH ใช้เพื่อค้นหา K=42 ในรูปที่ 17

วิธีค้นหาแบบไบนารียังสามารถใช้เพื่อแทนไฟล์ที่เรียงลำดับเป็นแผนผังไบนารีได้ ค่าคีย์ที่พบในการดำเนินการครั้งแรกของขั้นตอนที่ 2 (K(8)=53) คือรากของแผนผัง ช่วงเวลาสำคัญทางซ้าย (1,7) และขวา (9,16) ของค่านี้จะถูกผลักลงบนสแต็ก ช่วงบนสุดจะถูกลบออกจากสแต็ก และใช้ขั้นตอนที่ 2 จะพบองค์ประกอบตรงกลาง (หรือองค์ประกอบทางด้านซ้ายของตรงกลาง) อยู่ภายใน คีย์นี้ (K(4)=33) จะกลายเป็นองค์ประกอบที่อยู่ถัดจากด้านซ้ายหลังจากรูท หากค่าของมันน้อยกว่าค่าของรูท และองค์ประกอบถัดไปทางด้านขวา ช่วงเวลาย่อยของช่วงเวลานี้ทางด้านขวาและซ้ายของคีย์ที่เพิ่มใหม่ [(1,3) , (5,7)] จะถูกวางไว้บนสแต็ก ขั้นตอนนี้จะถูกทำซ้ำจนกว่าสแต็กจะว่างเปล่า รูปที่ 18 แสดงแผนผังไบนารีที่จะสร้างขึ้นสำหรับคีย์ที่เรียงลำดับ 16 อันจากรูปที่ 17

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

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

การเรียงลำดับด้วยวิธีนี้จะดำเนินการตามลำดับทีละขั้นตอน บน เค-ขั้นที่ 1 ถือว่าส่วนของอาเรย์ประกอบด้วยส่วนแรก เค-มีการสั่งซื้อองค์ประกอบ 1 รายการแล้ว นั่นคือ .

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

ในแต่ละขั้นตอน ส่วนที่เรียงลำดับของอาร์เรย์จะเพิ่มขึ้น หากต้องการดำเนินการเรียงลำดับให้สมบูรณ์ คุณจะต้องดำเนินการ น– 1 ขั้นตอน

ยังคงตอบคำถามว่าจะหาสถานที่ที่เหมาะสมสำหรับองค์ประกอบได้อย่างไร เอ็กซ์- ดำเนินการดังนี้: เราจะดูองค์ประกอบที่อยู่ทางด้านซ้าย เอ็กซ์(นั่นคือส่วนที่สั่งไปแล้ว) ย้ายไปยังจุดเริ่มต้นของอาร์เรย์ ต้องดูรายการ ก(เจ), เจแตกต่างกันไปจาก เค- l ถึง 1 การตรวจสอบนี้จะสิ้นสุดเมื่อตรงตามเงื่อนไขข้อใดข้อหนึ่งต่อไปนี้:

พบองค์ประกอบซึ่งระบุถึงความจำเป็นในการแทรก เอ็กซ์ระหว่างและ ก(เจ).

ถึงจุดสิ้นสุดด้านซ้ายของส่วนที่สั่งของอาร์เรย์แล้ว ดังนั้นเราจึงจำเป็นต้องแทรก เอ็กซ์เป็นที่หนึ่ง

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

เทคนิคการเรียงลำดับแสดงไว้ในตารางที่ 2:

ตารางที่ 2 - ตัวอย่างการเรียงลำดับโดยใช้การรวมโดยตรง

ลำดับการสั่งซื้อเริ่มแรกประกอบด้วยองค์ประกอบที่ 1 9 องค์ประกอบ เอ( 2) =5 – ลำดับแรกของลำดับที่ไม่เรียงลำดับและ 5< 9, поэтому ставится на его место, а 9 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 5, 9. Элемент เอ( 3) =15 ของลำดับไม่เรียงลำดับมากกว่าองค์ประกอบทั้งหมดของลำดับเรียงลำดับ ดังนั้นมันจึงยังคงอยู่ในตำแหน่งเดิม และในขั้นตอนต่อไป ลำดับอันดับจะประกอบด้วย 5, 9, 15 และองค์ประกอบที่เป็นปัญหาคือ 6 กระบวนการดำเนินต่อไป จนกระทั่งลำดับกลายเป็นลำดับ

การเรียงลำดับเชคเกอร์

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

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

ตารางที่ 3 – ตัวอย่างการคัดแยกเชคเกอร์

จัดเรียงอาร์เรย์โดยใช้การรวมด้วยระยะทางที่ลดลง (วิธีเชลล์)

D. Schell เสนอการปรับปรุงในการเรียงลำดับโดยใช้การรวมโดยตรง

แนวคิดของวิธีการ: องค์ประกอบทั้งหมดของอาร์เรย์จะถูกแบ่งออกเป็นกลุ่มในลักษณะที่แต่ละกลุ่มรวมองค์ประกอบที่เว้นระยะห่างจากกันตามจำนวนตำแหน่งที่แน่นอน ล- องค์ประกอบของแต่ละกลุ่มจะถูกจัดเรียง หลังจากนั้น องค์ประกอบทั้งหมดจะรวมกันอีกครั้งและจัดเรียงเป็นกลุ่ม ในขณะที่ระยะห่างระหว่างองค์ประกอบจะลดลง กระบวนการสิ้นสุดหลังจากเรียงลำดับองค์ประกอบโดยมีระยะห่างระหว่างองค์ประกอบเท่ากับ 1

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

ตารางที่ 4 – ตัวอย่างการเรียงลำดับโดยใช้วิธีเชลล์

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

แยกการเรียงลำดับ (การเรียงลำดับด่วน)

วิธีการเรียงลำดับแบบแยกเสนอโดย Charles Hoare วิธีนี้เป็นการพัฒนาวิธีแลกเปลี่ยนอย่างง่ายและมีประสิทธิภาพมากจนเรียกว่าวิธี Quicksort

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

กระบวนการเรียงลำดับอาร์เรย์โดยใช้วิธีที่รวดเร็วแสดงไว้ในตารางที่ 5

ตารางที่ 5 – ตัวอย่างการเรียงลำดับแบบด่วน

ข้อมูลทั่วไป

การเรียงลำดับด้วยวิธีนี้จะดำเนินการตามลำดับทีละขั้นตอน ในขั้นตอนที่ k จะถือว่าส่วนของอาเรย์ที่มีองค์ประกอบ k-1 แรกได้รับการสั่งซื้อแล้ว นั่นก็คือ ถัดไปคุณจะต้องใช้องค์ประกอบ kth และเลือกตำแหน่งในส่วนที่เรียงลำดับของอาร์เรย์เพื่อที่ว่าหลังจากการแทรกแล้วการเรียงลำดับจะไม่หยุดชะงักนั่นคือคุณต้องค้นหาสิ่งนั้น จากนั้นคุณจะต้องแทรกองค์ประกอบ a[k] ในตำแหน่งที่พบ

ยังคงตอบคำถามว่าจะค้นหาสถานที่ที่เหมาะสมสำหรับองค์ประกอบ x ได้อย่างไร ดำเนินการต่อดังนี้: เราจะดูองค์ประกอบที่อยู่ทางด้านซ้ายของ x (นั่นคือองค์ประกอบที่เรียงลำดับแล้ว) โดยย้ายไปยังจุดเริ่มต้นของอาร์เรย์ คุณต้องดูองค์ประกอบ a[j] j โดยเปลี่ยนจาก k-l เป็น 1 การสแกนดังกล่าวจะสิ้นสุดเมื่อตรงตามเงื่อนไขข้อใดข้อหนึ่งต่อไปนี้: พบองค์ประกอบ a[j] ตัวอย่าง เรามาอธิบายสั้นๆ ในส่วนของอัลกอริทึมการเรียงลำดับ การใช้การรวมโดยตรง: สำหรับ k:= 2 ถึง n ให้เริ่มต้น x:= a[k]; เจ:= k-1;

วิธีนี้ใช้กันอย่างแพร่หลายในการเล่นไพ่ องค์ประกอบ (การ์ด) จะถูกแบ่งทางจิตใจออกเป็นลำดับที่ "พร้อม" แล้ว A1 ... An และลำดับดั้งเดิม Ai ... An ในแต่ละขั้นตอน เริ่มจาก i=2 และเพิ่ม I ทีละขั้น องค์ประกอบ i-th จะถูกแยกออกจากลำดับดั้งเดิมและถ่ายโอนไปยังลำดับที่เสร็จสิ้นแล้ว และจะถูกแทรกลงในตำแหน่งที่ถูกต้อง

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

สำหรับ i:=2 ถึง n ทำ

รวม x ในตำแหน่งที่สอดคล้องกันระหว่าง ... a[j];

ในกระบวนการจริงของการค้นหาสถานที่ที่เหมาะสมจะสะดวกโดยสลับการเปรียบเทียบและการเคลื่อนไหวตามลำดับเพื่อกรอง X เหมือนเดิมนั่นคือ X ถูกเปรียบเทียบกับองค์ประกอบถัดไป aj จากนั้น X ใด ๆ จะถูกแทรกลงในช่องว่าง space หรือ aj ถูกเลื่อน (ส่ง) ไปทางขวา และกระบวนการ "ไป" ไปทางซ้าย โปรดทราบว่ากระบวนการกรองอาจสิ้นสุดหากตรงตามเงื่อนไขข้อใดข้อหนึ่งจากสองเงื่อนไขที่แตกต่างกันต่อไปนี้:

1. พบองค์ประกอบ aj ที่มีคีย์น้อยกว่าคีย์ของ X

2. ถึงจุดสิ้นสุดด้านซ้ายของลำดับที่เสร็จแล้วแล้ว

กรณีทั่วไปของกระบวนการทำซ้ำที่มีเงื่อนไขการสิ้นสุดสองเงื่อนไขทำให้เราสามารถใช้เทคนิคสิ่งกีดขวางที่รู้จักกันดี (แมวมอง) สามารถใช้ได้อย่างง่ายดายที่นี่โดยตั้งค่าสิ่งกีดขวาง a0 ด้วยค่า X (โปรดทราบว่าสำหรับสิ่งนี้จำเป็นต้องขยายช่วงของดัชนีในคำอธิบายของตัวแปร a เป็น 0 ... n)

การวิเคราะห์วิธีการรวมโดยตรง จำนวนการเปรียบเทียบคีย์ (Ci) ในระหว่างการกรอง i-th มีค่ามากที่สุดเท่ากับ i - 1 อย่างน้อย 1; หากเราถือว่าการเรียงสับเปลี่ยนของคีย์ n ทั้งหมดมีความน่าจะเป็นเท่ากัน ดังนั้นจำนวนการเปรียบเทียบโดยเฉลี่ยคือ i/2 จำนวนการถ่ายโอน (การกำหนดองค์ประกอบ) Mi เท่ากับ Ci + 2 (รวมสิ่งกีดขวาง) ดังนั้นจำนวนการเปรียบเทียบและจำนวนการโอนทั้งหมดจึงเป็นดังนี้:

บันทึก = (n2 + n - 2)/4,

Сmax = (n2 + n - 4)/4,

M นาที = З*(n - 1)

M ave = (n2 + 9n - 10)/4,

M สูงสุด = (n2 + 3n - 4)/2

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

อัลกอริธึมที่มีการรวมโดยตรงสามารถปรับปรุงได้อย่างง่ายดายหากคุณใส่ใจกับความจริงที่ว่าลำดับที่เสร็จสิ้นแล้ว (a1 ... ai-1 ที่ต้องแทรกองค์ประกอบใหม่นั้นได้รับคำสั่งในตัวมันเองแล้ว เป็นเรื่องปกติที่จะมุ่งเน้นไปที่การค้นหาแบบไบนารี โดยมีความพยายามที่จะเปรียบเทียบกับตรงกลางของลำดับที่เสร็จแล้ว จากนั้นกระบวนการลดลงครึ่งหนึ่งจะดำเนินต่อไปจนกระทั่งพบจุดแทรก อัลกอริธึมการเรียงลำดับที่แก้ไขนี้เรียกว่าวิธีการแทรกแบบไบนารี