Halving Convention
เมื่อจำนวนองค์ประกอบในรายการเป็นเลขคู่ การลดรายการลงครึ่งหนึ่งหมายความว่าครึ่งแรกของรายการคือครึ่งแรก และครึ่งหลังตามตัวอักษรของรายการคือครึ่งหลัง องค์ประกอบกลาง (กลาง) ของรายการทั้งหมด เป็นองค์ประกอบสุดท้ายของรายการแรก ซึ่งหมายความว่าดัชนีตรงกลางมีความยาว / 2 – 1 เนื่องจากการนับดัชนีเริ่มจากศูนย์ ความยาวคือจำนวนขององค์ประกอบในรายการ ตัวอย่างเช่น หากจำนวนองค์ประกอบเท่ากับ 8 ครึ่งแรกของรายการจะมีองค์ประกอบ 4 รายการ และครึ่งหลังของรายการก็มีองค์ประกอบ 4 รายการด้วย นั่นเป็นเรื่องปกติ เนื่องจากการนับดัชนีเริ่มต้นจาก 0 ดัชนีกลางคือ 3 = 8 / 2 – 1
แล้วกรณีที่จำนวนขององค์ประกอบในรายการหรือรายการย่อยเป็นเลขคี่? ในตอนเริ่มต้น ความยาวยังคงหารด้วย 2 ตามธรรมเนียมแล้ว จำนวนองค์ประกอบในครึ่งแรกของการหารนี้คือ ความยาว / 2 + 1/2 การนับดัชนีเริ่มจากศูนย์ ดัชนีกลางกำหนดโดยความยาว / 2 - 1/2 นี่ถือเป็นระยะกลางโดยอนุสัญญา ตัวอย่างเช่น หากจำนวนองค์ประกอบในรายการคือ 5 ดัชนีตรงกลางจะเป็น 2 = 5/2 – 1/2 และมีสามองค์ประกอบในครึ่งแรกของรายการและสององค์ประกอบในครึ่งหลัง องค์ประกอบตรงกลางของรายการทั้งหมดเป็นองค์ประกอบที่สามที่ดัชนี 2 ซึ่งเป็นดัชนีกลางเนื่องจากการนับดัชนีเริ่มต้นจาก 0
การหารด้วยวิธีนี้เป็นตัวอย่างของเลขคณิตจำนวนเต็ม
ค่ามัธยฐานของสามค่า
คำถาม: ค่ามัธยฐานของลำดับคืออะไร:
ซี บี เอ
สารละลาย:
เรียงลำดับรายการจากน้อยไปมาก:
เอ บี ซี
ระยะกลาง B เป็นค่ามัธยฐาน เป็นขนาดที่อยู่ระหว่างอีกสองขนาด
การหาค่ามัธยฐานในรายการไม่ใช่แบบนั้น ตัวอย่างเช่น ในรายการองค์ประกอบ 19 รายการที่ไม่ได้จัดเรียง อาจต้องมีค่ามัธยฐานสำหรับองค์ประกอบแรก องค์ประกอบกลาง และองค์ประกอบสุดท้าย ค่าทั้งสามนี้อาจไม่เรียงลำดับจากน้อยไปมาก ดังนั้นจึงต้องคำนึงถึงดัชนีของพวกเขาด้วย
ด้วย Quick Sort จำเป็นต้องมีค่ามัธยฐานสำหรับรายการทั้งหมดและรายการย่อย pseudocode เพื่อค้นหาค่ามัธยฐานของค่าสามค่าที่เว้นระยะห่างในรายการ (อาร์เรย์) คือ:
กลาง: =⌊(ต่ำ+สูง) / 2⌋ถ้าarr[กลาง] <arr[ต่ำ]
แลกเปลี่ยน arr[ต่ำ]กับ arr[กลาง]
ถ้าarr[สูง] <arr[ต่ำ]
แลกเปลี่ยน arr[ต่ำ]กับ arr[สูง]
ถ้าarr[กลาง] <arr[สูง]
แลกเปลี่ยน arr[กลาง]กับ arr[สูง]
หมุน: =arr[สูง]
คำว่า arr หมายถึงอาร์เรย์ ส่วนรหัสนี้จะค้นหาค่ามัธยฐานและทำการเรียงลำดับด้วย ส่วนรหัสนี้ดูเรียบง่าย แต่อาจสร้างความสับสนได้ ดังนั้น ให้ความสนใจกับคำอธิบายต่อไปนี้:
การเรียงลำดับในบทช่วยสอนนี้จะสร้างรายการโดยที่ค่าแรกเป็นค่าที่น้อยที่สุด และค่าสุดท้ายคือค่าที่มากที่สุด ด้วยตัวอักษร A น้อยกว่า Z
ในที่นี้เดือยคือค่ามัธยฐานที่ได้ ต่ำคือดัชนีต่ำสุดของรายการหรือรายการย่อย (ไม่จำเป็นสำหรับค่าต่ำสุด) high คือดัชนีสูงสุดของรายการหรือรายการย่อย (ไม่จำเป็นสำหรับค่าสูงสุด) และค่ากลางคือดัชนีระดับกลางแบบธรรมดา (ไม่จำเป็นสำหรับค่ากลางของรายการทั้งหมด)
ดังนั้น ค่ามัธยฐานที่จะได้รับอยู่ระหว่างค่าดัชนีต่ำสุด ค่าดัชนีกลาง และค่าดัชนีสูงสุด
ในโค้ด จะได้ค่าดัชนีกลางแบบธรรมดาก่อน ในตอนเริ่มต้นนี้ รายการจะไม่ถูกจัดเรียง การเปรียบเทียบและการจัดเรียงใหม่บางส่วนโดยเรียงลำดับจากน้อยไปมากของค่าทั้งสามจะต้องเกิดขึ้นพร้อมกัน if-statement แรกเปรียบเทียบค่าสำหรับดัชนีต่ำสุดและดัชนีกลาง หากดัชนีกลางน้อยกว่าดัชนีต่ำสุด ค่าทั้งสองจะสลับตำแหน่ง การดำเนินการนี้จะเริ่มต้นการเรียงลำดับและเปลี่ยนแปลงการจัดเรียงค่าในรายการหรือรายการย่อย คำสั่ง if ที่สองเปรียบเทียบค่าสำหรับดัชนีสูงสุดและดัชนีต่ำสุด หากดัชนีสูงสุดน้อยกว่าดัชนีต่ำสุด ค่าทั้งสองจะสลับตำแหน่ง สิ่งนี้ดำเนินการในการเรียงลำดับและเปลี่ยนแปลงการจัดเรียงของค่าในรายการหรือรายการย่อย คำสั่ง if ที่สามเปรียบเทียบค่าของดัชนีกลางและดัชนีสูงสุด หากดัชนีสูงสุดน้อยกว่าดัชนีกลาง ค่าทั้งสองจะสลับตำแหน่ง การจัดเรียงหรือการจัดเรียงใหม่อาจเกิดขึ้นที่นี่เช่นกัน ถ้าเงื่อนไขที่สามนี้ไม่เหมือนสองก่อนหน้านี้
ในตอนท้ายของการแลกเปลี่ยนทั้งสามนี้ ค่ากลางของค่าทั้งสามที่เป็นปัญหาจะเป็น A[สูง] ซึ่งเนื้อหาดั้งเดิมอาจมีการเปลี่ยนแปลงในส่วนโค้ด ตัวอย่างเช่น พิจารณาลำดับที่ไม่เรียงลำดับ:
ซี บี เอ
เรารู้แล้วว่าค่ามัธยฐานคือ B อย่างไรก็ตาม สิ่งนี้ควรได้รับการพิสูจน์ จุดมุ่งหมายที่นี่คือเพื่อให้ได้ค่ามัธยฐานของค่าทั้งสามนี้โดยใช้ส่วนของโค้ดด้านบน คำสั่ง if แรกเปรียบเทียบ B และ C หาก B น้อยกว่า C จะต้องสลับตำแหน่งของ B และ C B น้อยกว่า C ดังนั้นการจัดเรียงใหม่จึงกลายเป็น:
บี ซี เอ
สังเกตว่า ค่าสำหรับดัชนีต่ำสุดและดัชนีกลางมีการเปลี่ยนแปลง คำสั่ง if ที่สองเปรียบเทียบ A และ B หาก A น้อยกว่า B จะต้องสลับตำแหน่งของ A และ B A น้อยกว่า B ดังนั้นการจัดเรียงใหม่จึงกลายเป็น:
เอ ซี บี
สังเกตว่า ค่าสำหรับดัชนีสูงสุดและดัชนีต่ำสุดมีการเปลี่ยนแปลง คำสั่ง if ที่สามเปรียบเทียบ C และ B หาก C น้อยกว่า B ตำแหน่งของ C และ B จะต้องสลับกัน C ไม่น้อยกว่า B ดังนั้นจึงไม่มีการสลับเกิดขึ้น ข้อตกลงใหม่ยังคงเหมือนเดิม กล่าวคือ:
เอ ซี บี
B คือค่ามัธยฐาน ซึ่งก็คือ A[high] และมันคือเดือย ดังนั้นเดือยจึงเกิดที่ปลายสุดของรายการหรือรายการย่อย
ฟังก์ชันการแลกเปลี่ยน
คุณสมบัติอื่นที่จำเป็นสำหรับ Quick Sort คือฟังก์ชันการสลับ ฟังก์ชัน swapping แลกเปลี่ยนค่าของตัวแปรสองตัว pseudocode สำหรับฟังก์ชันการสลับคือ:
กำหนด swap(NS,และ)อุณหภูมิ: =NS
NS: =และ
และ: =อุณหภูมิ
ในที่นี้ x และ y หมายถึงค่าจริงไม่ใช่ค่าสำเนา
การเรียงลำดับในบทความนี้จะสร้างรายการโดยที่ค่าแรกเป็นค่าที่น้อยที่สุด และค่าสุดท้ายคือค่าที่มากที่สุด
เนื้อหาบทความ
อัลกอริธึมการเรียงลำดับอย่างรวดเร็ว
วิธีปกติในการเรียงลำดับรายการที่ไม่เรียงลำดับคือการพิจารณาค่าสองค่าแรก ถ้าไม่เป็นระเบียบก็จัดไปเลยครับ ต่อไป ให้พิจารณาสามค่าแรก สแกนสองค่าแรกเพื่อดูว่าค่าที่สามตรงตำแหน่งใดและเหมาะสมที่สุด จากนั้นให้พิจารณาสี่ค่าแรก สแกนสามค่าแรกเพื่อดูว่าค่าที่สี่พอดีและเหมาะสมที่สุด ทำตามขั้นตอนนี้ต่อไปจนกว่าจะจัดเรียงรายการทั้งหมด
ขั้นตอนนี้เรียกอีกอย่างว่าการจัดเรียงแบบเดรัจฉานในภาษาการเขียนโปรแกรมคอมพิวเตอร์ช้าเกินไป อัลกอริทึม Quick Sort มาพร้อมกับขั้นตอนที่เร็วกว่ามาก
ขั้นตอนสำหรับอัลกอริธึม Quicksort มีดังนี้:
- ตรวจสอบให้แน่ใจว่ามีอย่างน้อย 2 หมายเลขที่จะเรียงลำดับในรายการที่ไม่ได้เรียงลำดับ
- รับค่าส่วนกลางโดยประมาณสำหรับรายการ เรียกว่าเดือย ค่ามัธยฐานตามที่อธิบายไว้ข้างต้นเป็นวิธีหนึ่งในการรับเดือย วิธีการต่าง ๆ มาพร้อมกับข้อดีและข้อเสีย - ดูในภายหลัง
- แบ่งรายการ. ซึ่งหมายความว่า วางเดือยในรายการ ด้วยวิธีนี้ องค์ประกอบทั้งหมดทางด้านซ้ายจะน้อยกว่าค่า pivot และองค์ประกอบทั้งหมดทางด้านขวาจะมากกว่าหรือเท่ากับค่า pivot มีหลายวิธีในการแบ่งพาร์ติชัน วิธีการแบ่งพาร์ติชันแต่ละวิธีมีข้อดีและข้อเสีย การแบ่งแยกคือการแบ่งแยกและพิชิตกระบวนทัศน์
- ทำซ้ำขั้นตอนที่ 1, 2 และ 3 ซ้ำๆ สำหรับคู่รายการย่อยใหม่ที่ปรากฏจนกว่าจะจัดเรียงรายการทั้งหมด นี่คือการพิชิตในกระบวนทัศน์การแบ่งแยกและพิชิต
รหัสเทียม Quick Sort คือ:
อัลกอริทึม quicksort(arr,ต่ำ,สูง)เป็นถ้าต่ำ<สูงแล้ว
หมุน(ต่ำ,สูง)
NS: =พาร์ทิชัน(arr,ต่ำ,สูง)
Quicksort(arr,ต่ำ,NS- 1)
Quicksort(arr,NS+ 1,สูง)
พาร์ทิชัน Pseudocode
pseudocode ของพาร์ติชันที่ใช้ในบทช่วยสอนนี้คือ:
พาร์ทิชันอัลกอริทึม(arr,ต่ำ,สูง)เป็นหมุน: =arr[สูง]
ผม: =ต่ำ
NS: =สูง
ทำ
ทำ
++ผม
ในขณะที่(arr[ผม] <หมุน)
ทำ
-NS
ในขณะที่(arr[NS] >หมุน)
ถ้า (ผม<NS)
แลกเปลี่ยน arr[ผม]กับ arr[NS]
ในขณะที่(ผม<NS)
แลกเปลี่ยน arr[ผม]กับ arr[สูง]
กลับผม
ในภาพประกอบของ Quick Sort ด้านล่าง รหัสนี้ถูกใช้:
ภาพประกอบของ Quick Sort
พิจารณารายการที่ไม่เรียงลำดับ (อาร์เรย์) ของตัวอักษรตามตัวอักษรต่อไปนี้:
Q W E R T Y U I O P
โดยการตรวจสอบ รายการที่เรียงลำดับคือ:
E I O P Q R T U W Y
รายการที่เรียงลำดับจะได้รับการพิสูจน์แล้ว โดยใช้อัลกอริทึมด้านบนและเซกเมนต์ pseudocode จากรายการที่ไม่เรียงลำดับ:
Q W E R T Y U I O P
pivot แรกถูกกำหนดจาก arr[0]=Q, arr[4]=T และ arr[9]=P และระบุเป็น Q และวางไว้ที่ด้านขวาสุดของรายการ ดังนั้น รายการที่มีการจัดเรียงฟังก์ชัน pivot จะกลายเป็น:
P W E R T Y U I O Q
pivot ปัจจุบันคือ Q ขั้นตอน pivot ทำการเรียงลำดับเล็กน้อยและวาง P ไว้ที่ตำแหน่งแรก รายการผลลัพธ์จะต้องถูกจัดเรียงใหม่ (แบ่งพาร์ติชั่น) เพื่อให้องค์ประกอบทั้งหมดทางด้านซ้ายมีค่าน้อยกว่า จากนั้นเดือยและองค์ประกอบทั้งหมดทางด้านขวาของเดือยจะเท่ากับหรือมากกว่าเดือย คอมพิวเตอร์ไม่สามารถแบ่งพาร์ติชันโดยการตรวจสอบได้ ทำได้โดยใช้ดัชนีและอัลกอริธึมพาร์ติชั่นด้านบน
ดัชนีระดับต่ำและระดับสูงในตอนนี้คือ 0 และ 9 ดังนั้น คอมพิวเตอร์จะเริ่มต้นด้วยการสแกนจากดัชนี 0 จนกว่าจะถึงดัชนี ซึ่งมีค่าเท่ากับหรือมากกว่าเดือยและหยุดอยู่ที่นั่นชั่วคราว นอกจากนี้ยังจะสแกนจากปลายสูง (ขวา) ดัชนี 9 ลงมาจนกว่าจะถึงดัชนีที่มีค่าน้อยกว่าหรือเท่ากับเดือยและหยุดที่นั่นชั่วคราว นี่หมายถึงตำแหน่งหยุดสองตำแหน่ง หาก i ตัวแปรดัชนีส่วนเพิ่ม จากค่าต่ำยังไม่เท่ากับหรือมากกว่าตัวแปรดัชนีที่ลดลง j จากค่าสูง ค่าสองค่านี้จะถูกสลับ ในสถานการณ์ปัจจุบัน การสแกนจากปลายทั้งสองข้างจะหยุดที่ W และ O ดังนั้นรายการจึงกลายเป็น:
P O E R T Y U I W Q
เดือยยังคงเป็น Q การสแกนในทิศทางตรงกันข้ามจะดำเนินต่อไปและหยุดตามนั้น หาก i ยังไม่เท่ากับหรือมากกว่า j ค่าสองค่าที่หยุดการสแกนจากปลายทั้งสองข้างจะถูกสลับ คราวนี้ การสแกนจากปลายทั้งสองข้างหยุดที่ R และ I ดังนั้น การจัดเรียงรายการจะกลายเป็น:
P O E I T Y U R W Q
เดือยยังคงเป็น Q การสแกนในทิศทางตรงกันข้ามจะดำเนินต่อไปและหยุดตามนั้น หาก i ยังไม่เท่ากับหรือมากกว่า j ค่าทั้งสองที่หยุดการสแกนจะถูกสลับ คราวนี้ การสแกนจากปลายทั้งสองข้างจะหยุดที่ T for i และ I for j ฉันและเจได้พบหรือข้าม ดังนั้นจึงไม่มีการสับเปลี่ยน รายการยังคงเหมือนเดิม:
P O E I T Y U R W Q
ณ จุดนี้ เดือย Q จะต้องอยู่ในตำแหน่งสุดท้ายในการเรียงลำดับ ทำได้โดยสลับ arr[i] กับ arr[high], สลับ T และ Q รายการจะกลายเป็น:
P O E I Q Y U R W T
ณ จุดนี้ การแบ่งพาร์ติชันสำหรับรายการทั้งหมดได้สิ้นสุดลงแล้ว pivot = Q มีบทบาท ตอนนี้มีรายการย่อยสามรายการ ได้แก่ :
P O E I Q Y U R W T
การแบ่งแยกคือการแบ่งและพิชิต (การเรียงลำดับ) ในกระบวนทัศน์ Q อยู่ที่ตำแหน่งการจัดเรียงที่ถูกต้อง ทุกองค์ประกอบทางด้านซ้ายของ Q มีขนาดเล็กกว่า Q และทุกองค์ประกอบทางด้านขวาของ Q นั้นใหญ่กว่า Q อย่างไรก็ตาม รายการด้านซ้ายยังไม่ได้จัดเรียง และรายการที่ถูกต้องยังไม่ถูกจัดเรียง ต้องเรียกใช้ฟังก์ชัน Quick Sort ทั้งหมดซ้ำๆ เพื่อจัดเรียงรายการย่อยด้านซ้ายและรายการย่อยด้านขวา การเรียกคืน Quick Sort นี้ต้องดำเนินต่อไป รายการย่อยใหม่จะพัฒนาจนกว่ารายการดั้งเดิมทั้งหมดจะถูกจัดเรียงอย่างสมบูรณ์ สำหรับการเรียกคืนฟังก์ชัน Quick Sort แต่ละครั้ง รายการย่อยด้านซ้ายจะถูกเข้าร่วมก่อนที่จะเข้าร่วมรายการย่อยด้านขวาที่เกี่ยวข้อง ต้องได้รับ pivot ใหม่สำหรับแต่ละรายการย่อย
สำหรับรายการย่อย:
พี โอ อี
กำหนดเดือย (ค่ามัธยฐาน) สำหรับ P, O และ I pivot จะเป็น O สำหรับรายการย่อยนี้ และเกี่ยวข้องกับรายการทั้งหมด arr[low] ใหม่คือ arr[0] และ arr[high] ใหม่คือ arr[i-1] สุดท้าย = arr[ 4-1] = arr[3] โดยที่ i คือดัชนี pivot สุดท้ายจากพาร์ติชั่นก่อนหน้า หลังจากเรียกใช้ฟังก์ชัน pivot() แล้ว ค่า pivot ใหม่ pivot = O อย่าสับสนระหว่างฟังก์ชัน pivot กับค่า pivot ฟังก์ชันเดือยอาจทำการเรียงลำดับเล็กน้อยและวางเดือยที่ด้านขวาสุดของรายการย่อย รายการย่อยนี้จะกลายเป็น
ไอ พี อี โอ
ด้วยโครงร่างนี้ pivot จะสิ้นสุดที่ด้านขวาสุดของรายการย่อยหรือรายการหลังจากการเรียกใช้ฟังก์ชันเสมอ การสแกนจากปลายทั้งสองข้างเริ่มต้นจาก arr[0] และ arr[3] จนกระทั่ง i และ j พบกันหรือข้าม การเปรียบเทียบเสร็จสิ้นด้วย pivot = O จุดแวะแรกอยู่ที่ P และ E โดยจะสลับกัน และรายการย่อยใหม่จะกลายเป็น:
ไอ อี พี โอ
การสแกนจากปลายทั้งสองจะดำเนินต่อไป และจุดแวะใหม่อยู่ที่ P for i และ E for j ตอนนี้ฉันและเจได้พบหรือข้าม ดังนั้นรายการย่อยยังคงเหมือนเดิม:
ไอ อี พี โอ
การแบ่งพาร์ติชั่นของรายการย่อยหรือรายการสิ้นสุดลงเมื่อเดือยถูกวางในตำแหน่งสุดท้าย ดังนั้น ค่าใหม่สำหรับ arr[i] และ arr[high] จะถูกสลับ นั่นคือ P และ O ถูกสลับกัน รายการย่อยใหม่จะกลายเป็น:
ไอ อี โอ พี
ตอนนี้ O อยู่ที่ตำแหน่งสุดท้ายของรายการทั้งหมด บทบาทในฐานะแกนหมุนได้สิ้นสุดลงแล้ว ขณะนี้รายการย่อยถูกแบ่งออกเป็นสามรายการเพิ่มเติม ซึ่งได้แก่:
ไอ อี โอ พี
ณ จุดนี้ ต้องเรียก Quick Sort ของรายการย่อยด้านขวารายการแรก อย่างไรก็ตามจะไม่ถูกเรียก แต่จะมีการจดบันทึกและสงวนไว้เพื่อเรียกในภายหลัง เนื่องจากคำสั่งของฟังก์ชันการแบ่งพาร์ติชันถูกดำเนินการ จากด้านบนของฟังก์ชัน จะเป็น Quick Sort สำหรับรายการย่อยด้านซ้ายที่ต้องเรียกตอนนี้ (หลังจากเรียก pivot() แล้ว) มันจะถูกเรียกสำหรับรายการ:
เช่น
โดยจะเริ่มจากการหาค่ามัธยฐานของ I และ E ในที่นี้ arr[low] = I, arr[mid] = I และ arr[high] = E ดังนั้นค่ามัธยฐาน pivot จึงควรกำหนดโดยอัลกอริทึม pivot ดังนี้ , I. อย่างไรก็ตาม pseudocode pivot ด้านบนจะกำหนด pivot เป็น E ข้อผิดพลาดนี้เกิดขึ้นที่นี่เนื่องจาก pseudocode ด้านบนมีไว้สำหรับองค์ประกอบสามองค์ประกอบ ไม่ใช่สององค์ประกอบ ในการใช้งานด้านล่าง มีการปรับเปลี่ยนโค้ดบางส่วน รายการย่อยจะกลายเป็น
อีฉัน
จุดหมุนจะสิ้นสุดที่ด้านขวาสุดของรายการย่อยหรือรายการหลังจากการเรียกใช้ฟังก์ชัน การสแกนจากปลายทั้งสองข้างเริ่มต้นจาก arr[0] และ arr[1] แบบเอกสิทธิ์เฉพาะจนกระทั่ง i และ j พบกันหรือข้าม การเปรียบเทียบเสร็จสิ้นด้วย pivot = I จุดแวะแรกและจุดเดียวอยู่ที่ I และ E: ที่ I สำหรับ i และที่ E สำหรับ j ตอนนี้ฉันกับเจได้พบกันหรือข้ามไป ดังนั้น รายการย่อยยังคงเหมือนเดิม:
อีฉัน
การแบ่งพาร์ติชั่นของรายการย่อยหรือรายการสิ้นสุดลงเมื่อเดือยถูกวางในตำแหน่งสุดท้าย ดังนั้น ค่าใหม่สำหรับ arr[i] และ arr[high] จะถูกสลับ มันเกิดขึ้นที่นี่ว่า arr[i] = I และ arr[high] = I ดังนั้น ค่าเดียวกันจะถูกสลับกับตัวมันเอง รายการย่อยใหม่จะกลายเป็น:
อีฉัน
ตอนนี้ฉันอยู่ที่ตำแหน่งสุดท้ายสำหรับรายการทั้งหมด บทบาทในฐานะแกนหมุนได้สิ้นสุดลงแล้ว ตอนนี้รายการย่อยถูกแบ่งออกเป็นสองรายการเพิ่มเติมคือ
อีฉัน
ตอนนี้ pivots จนถึงตอนนี้คือ Q, O และ I Pivots จะสิ้นสุดที่ตำแหน่งสุดท้าย รายการย่อยขององค์ประกอบเดียว เช่น P ด้านบน จะสิ้นสุดที่ตำแหน่งสุดท้ายเช่นกัน
ณ จุดนี้ รายการย่อยด้านซ้ายรายการแรกได้รับการจัดเรียงอย่างสมบูรณ์ และขั้นตอนการคัดแยกอยู่ที่:
E I O P Q Y U R W T
รายการย่อยขวารายการแรก:
ยู อาร์ ดับเบิลยู ที
ยังคงต้องเรียงลำดับ
พิชิตรายการย่อยที่ใช่คนแรก
โปรดจำไว้ว่าการเรียก Quick Sort สำหรับรายการย่อยด้านขวารายการแรกนั้นได้รับการบันทึกและสงวนไว้แทนที่จะดำเนินการ ณ จุดนี้จะดำเนินการ ดังนั้น arr[low] = arr[5] = arr[QPivotIndex+1] ใหม่ และ arr[high] ใหม่ยังคงเป็น arr[9] กิจกรรมชุดเดียวกันที่เกิดขึ้นสำหรับรายการย่อยด้านซ้ายรายการแรกจะเกิดขึ้นที่นี่ และรายการย่อยด้านขวาแรกนี้ถูกจัดเรียงเป็น:
R T U W Y
และรายการที่ไม่เรียงลำดับดั้งเดิมได้รับการจัดเรียงเป็น:
E I O P Q R T U W Y
Java Coding
การวางอัลกอริธึมใน Java เป็นเพียงการใส่เซ็กเมนต์ pseudocode ด้านบนทั้งหมดลงในเมธอด Java ในคลาสเดียว อย่าลืมว่าต้องมีเมธอด main() ในคลาสที่จะเรียกใช้ฟังก์ชัน quicksort() ด้วยอาร์เรย์ที่ไม่เรียงลำดับ
วิธี pivot()
Java pivot() วิธีการส่งกลับค่า pivot ควรเป็น:
โมฆะหมุน(chararr[], intต่ำ, intสูง) {intกลาง= (ต่ำ+สูง) / 2;
ถ้า (arr[กลาง] <arr[ต่ำ])
แลกเปลี่ยน(arr,ต่ำ,กลาง);
ถ้า (arr[สูง] <arr[ต่ำ])
แลกเปลี่ยน(arr,ต่ำ,สูง);
ถ้า ((สูง-ต่ำ) > 2) {
ถ้า (arr[กลาง] <arr[สูง])
แลกเปลี่ยน(arr,กลาง,สูง);
}
}
วิธีการแลกเปลี่ยน ()
วิธีการ swap() ควรเป็น:
โมฆะแลกเปลี่ยน(chararr[], intNS, intและ) {charอุณหภูมิ=arr[NS];
arr[NS] =arr[และ];
arr[และ] =อุณหภูมิ;
}
Quicksort() Method
วิธี quicksort() ควรเป็น:
โมฆะQuicksort(chararr[], intต่ำ, intสูง) {ถ้า (ต่ำ<สูง) {
หมุน(arr,ต่ำ,สูง);
intNS=พาร์ทิชัน(arr,ต่ำ,สูง);
Quicksort(arr,ต่ำ,NS- 1);
Quicksort(arr,NS+ 1,สูง);
}
}
พาร์ติชัน() วิธีการ
วิธี partition() ควรเป็น:
intพาร์ทิชัน(chararr[], intต่ำ, intสูง) {charหมุน=arr[สูง];
intผม=ต่ำ;
intNS=สูง;
ทำ {
ทำ
++ผม;
ในขณะที่(arr[ผม] <หมุน);
ทำ
-NS;
ในขณะที่(arr[NS] >หมุน);
ถ้า (ผม<NS)
แลกเปลี่ยน(arr,ผม,NS);
}ในขณะที่(ผม<NS);
แลกเปลี่ยน(arr,ผม,สูง);
กลับผม;
}
หลัก() วิธีการ
วิธี main() สามารถ:
สาธารณะคงที่ โมฆะหลัก(สตริง[]args) {chararr[] = {'NS', 'ใน', 'และ', 'NS', 'NS', 'และ', 'ยู', 'ผม', 'หรือ', 'NS'};
TheClass QuickSort= ใหม่ห้องเรียน();
QuickSortQuicksort(arr, 0, 9);
ระบบ.ออก.println('องค์ประกอบที่เรียงลำดับ:');
สำหรับ(intผม=0;ผม<10;ผม++) {
ระบบ.ออก.พิมพ์(arr[ผม]);ระบบ.ออก.พิมพ์('');
}
ระบบ.ออก.println();
}
วิธีการทั้งหมดข้างต้นสามารถจัดเป็นคลาสเดียวได้
บทสรุป
Quick Sort คืออัลกอริธึมการเรียงลำดับที่ใช้กระบวนทัศน์การแบ่งแยกและพิชิต เริ่มต้นด้วยการแบ่งรายการที่ไม่เรียงลำดับออกเป็นสองหรือสามรายการย่อย ในบทช่วยสอนนี้ Quick Sort ได้แบ่งรายการออกเป็นสามรายการย่อย ได้แก่ รายการย่อยด้านซ้าย รายการตรงกลางขององค์ประกอบเดียว และรายการย่อยด้านขวา การพิชิตใน Quick Sort คือการแบ่งรายการหรือรายการย่อยขณะเรียงลำดับโดยใช้ค่า Pivot บทช่วยสอนนี้ได้อธิบายการใช้งาน Quick Sort ในภาษาคอมพิวเตอร์ Java
เกี่ยวกับผู้เขียน
ดอกเบญจมาศ Forcha
ผู้ค้นพบการรวมคณิตศาสตร์จากหลักการแรกและชุดที่เกี่ยวข้อง ปริญญาโทด้านการศึกษาด้านเทคนิค เชี่ยวชาญด้านอิเล็กทรอนิกส์และซอฟต์แวร์คอมพิวเตอร์ วท.บ. อิเล็คทรอนิคส์. ฉันยังมีความรู้และประสบการณ์ในระดับปริญญาโทด้านคอมพิวเตอร์และโทรคมนาคม จากนักเขียน 20,000 คน ฉันเป็นนักเขียนอันดับที่ 37 ที่ devarticles.com ฉันทำงานในสาขาเหล่านี้มานานกว่า 10 ปี
ดูกระทู้ทั้งหมดโพสต์คำแนะนำ LINUX ที่เกี่ยวข้อง
- การเปรียบเทียบสตริงใน Java
- วิธีใช้ HashMap ใน Java
- เรียงลำดับอย่างรวดเร็วใน Java อธิบาย
- Binary Tree Preorder Traversal ใน Java
- ผสานการเรียงลำดับใน Java อธิบาย
- วิธีใช้สแกนเนอร์ใน Java
- Java เขียนไปยังไฟล์