การเรียงลำดับ เป็นฟังก์ชันพื้นฐานและมีประโยชน์ที่สุดอย่างหนึ่งที่ใช้กับข้อมูล มีจุดมุ่งหมายเพื่อจัดเรียงข้อมูลในรูปแบบเฉพาะซึ่งสามารถเพิ่มหรือลดได้ตามความต้องการ มีฟังก์ชัน builtin ใน C ++ STL โดยใช้ชื่อว่า 'sort ()' ซึ่งช่วยให้เราดำเนินการเรียงลำดับขั้นตอนวิธีได้อย่างง่ายดาย ในบทความนี้เราจะสำรวจฟังก์ชันการเรียงลำดับใน C ++
คำแนะนำต่อไปนี้จะกล่าวถึงในบทความนี้:
- ฟังก์ชัน Sort ()
- ตัวอย่าง - ในการจัดเรียงข้อมูลจากน้อยไปมาก
- ตัวอย่าง - ในการจัดเรียงข้อมูลจากมากไปหาน้อย
- Partial_sort
ไปต่อกับบทความนี้เกี่ยวกับฟังก์ชันการเรียงลำดับใน C ++
จัดเรียง ( ) ฟังก์ชัน
เป็นฟังก์ชันในตัวของไฟล์ส่วนหัวของอัลกอริทึมที่ใช้ในการจัดเรียงคอนเทนเนอร์เช่นอาร์เรย์เวกเตอร์ตามลำดับที่ระบุ ภายในฟังก์ชันนี้จะถูกนำไปใช้เป็น Quick-sort
Quicksort คืออัลกอริธึมการแบ่งและพิชิต Quicksort จะแบ่งรายการองค์ประกอบขนาดใหญ่ออกเป็นสองรายการย่อยที่เล็กกว่า ได้แก่ องค์ประกอบด้านล่างและองค์ประกอบที่สูงกว่า Quicksort จากนั้นเรียงลำดับรายการย่อยซ้ำ
ขั้นตอนมีดังนี้:
1. เลือกองค์ประกอบแบบสุ่ม (โดยปกติจะเป็นองค์ประกอบสุดท้าย) ที่เรียกว่าเดือยจากรายการ
2. จัดลำดับรายการใหม่ในลักษณะที่องค์ประกอบทั้งหมดที่มีค่าน้อยกว่าเดือยมาก่อนเดือยในขณะที่องค์ประกอบทั้งหมดที่มีค่ามากกว่าเดือยตามหลังมาและค่าที่เท่ากันสามารถไปทางใดทางหนึ่งกระบวนการนี้เรียกว่าการดำเนินการแบ่งพาร์ติชัน
3. เรียงลำดับรายการย่อยขององค์ประกอบที่น้อยกว่าและรายการย่อยขององค์ประกอบที่ใหญ่กว่าซ้ำแล้วซ้ำอีกเลือกเดือยในรายการย่อยแล้วแบ่งออก
กรณีพื้นฐานของการเรียกซ้ำคือรายการขนาดศูนย์หรือหนึ่งรายการซึ่งไม่จำเป็นต้องเรียงลำดับดังนั้นการรวมเข้าด้วยกันเราจึงจัดเรียงรายการของเรา
Quicksort เร็วกว่าในทางปฏิบัติอัลกอริทึม O (n log n) อื่น ๆ เช่นการเรียงลำดับการแทรกหรือการเรียงฟอง Quicksort สามารถใช้งานได้ด้วยอัลกอริทึมการแบ่งพาร์ติชันแบบแทนที่ซึ่งหมายความว่าการจัดเรียงทั้งหมดสามารถทำได้โดยมีพื้นที่เพิ่มเติม O (log n) เท่านั้น Quicksort ไม่ใช่การจัดเรียงที่มั่นคง
ความซับซ้อนมีดังนี้:
กรณีที่ดีที่สุด - O (n log n)
กรณีที่เลวร้ายที่สุด - O (n ^ 2)
กรณีเฉลี่ย - O (n log n)
ไวยากรณ์:
เรียงลำดับ (แรกสุดท้าย)
ที่นี่
อันดับแรก - คือดัชนี (ตัวชี้) ขององค์ประกอบแรกในช่วงที่จะจัดเรียง
last - คือดัชนี (ตัวชี้) ขององค์ประกอบสุดท้ายในช่วงที่จะจัดเรียง
ตัวอย่างเช่นเราต้องการจัดเรียงองค์ประกอบของอาร์เรย์ 'arr' ตั้งแต่ 1 ถึง 10 ตำแหน่งเราจะใช้การจัดเรียง (arr, arr + 10) และจะเรียงลำดับ 10 องค์ประกอบตามลำดับจากน้อยไปมาก
ส่งคืนค่า
ไม่มี
ความซับซ้อน
Hadoop เป็นเรื่องง่ายที่จะเรียนรู้
ค่าเฉลี่ยของความซับซ้อนของการเรียงลำดับคือ N * log2 (N) โดยที่ N = สุดท้าย - ก่อน
ช่วงข้อมูล
วัตถุในช่วง [แรกสุดท้าย) ถูกแก้ไข
ข้อยกเว้น
โอเวอร์โหลดด้วยพารามิเตอร์เทมเพลตที่มีชื่อว่า ExecutionPolicy รายงานข้อผิดพลาดดังนี้:
หากอัลกอริทึมไม่สามารถจัดสรรหน่วยความจำได้ std :: bad_alloc จะถูกส่งเป็นข้อยกเว้น
หากการเรียกใช้ฟังก์ชันที่เรียกใช้เป็นส่วนหนึ่งของอัลกอริทึมจะแสดงข้อยกเว้น std :: terminate
ไปต่อกับบทความนี้เกี่ยวกับฟังก์ชันการเรียงลำดับใน C ++
ตัวอย่าง - ในการจัดเรียงข้อมูลจากน้อยไปมาก:
#include โดยใช้ namespace std int main () {int array [] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10} int n = sizeof (array) / sizeof (array [0] ) // 'sizeof' ให้ขนาดของอาร์เรย์ทั้งหมดคือขนาดของแต่ละอักขระ * no ของอักขระ // ดังนั้นจึงจะไม่ได้รับ ของอักขระ // เราแบ่ง sizeof (อาร์เรย์) ด้วยขนาดของอักขระตัวใดตัวหนึ่งของอาร์เรย์ // ในที่นี้คือ array [0] sort (array, array + n) cout<< 'nArray after sorting using ' 'default sort is : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } เอาท์พุต:
คำอธิบาย
จากตัวอย่างข้างต้นเราจะเห็นว่าฟังก์ชัน sort () ตามค่าเริ่มต้นจะเรียงลำดับอาร์เรย์จากน้อยไปหามาก
ไปต่อกับบทความนี้เกี่ยวกับฟังก์ชันการเรียงลำดับใน C ++
ตัวอย่าง - ในการจัดเรียงข้อมูลจากมากไปหาน้อย:
ในการเรียงลำดับข้อมูลของอาร์เรย์จากมากไปหาน้อยเราจำเป็นต้องแนะนำพารามิเตอร์ที่สามที่ใช้เพื่อระบุลำดับที่จะจัดเรียงองค์ประกอบ เราสามารถใช้ฟังก์ชัน“ greater ()” เพื่อเรียงลำดับข้อมูลจากมากไปหาน้อย
#include โดยใช้ namespace std int main () {int array [] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10} int n = sizeof (array) / sizeof (array [0] ) เรียงลำดับ (อาร์เรย์อาร์เรย์ + n ค่าที่มากกว่า ())<< 'Array after sorting : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } เอาท์พุต:
ประสบการณ์ ล anation
ฟังก์ชัน sort () ที่นี่ทำการเปรียบเทียบในลักษณะที่ทำให้องค์ประกอบที่มากกว่าอยู่ก่อน
ไปต่อกับบทความนี้เกี่ยวกับฟังก์ชันการเรียงลำดับใน C ++
Partial_sort
C ++ STL ให้ฟังก์ชันการเรียงลำดับบางส่วนแก่เราฟังก์ชันนี้คล้ายกับฟังก์ชัน sort () แต่ต่างจากฟังก์ชัน sort () ซึ่งไม่ได้ใช้เพื่อจัดเรียงช่วงทั้งหมด แต่จะใช้เพื่อจัดเรียงเฉพาะส่วนย่อยของฟังก์ชัน มันจัดเรียงองค์ประกอบในช่วง [แรกสุดท้าย) ในลักษณะที่องค์ประกอบก่อนองค์ประกอบกลางจะเรียงลำดับจากน้อยไปมากในขณะที่องค์ประกอบหลังกลางจะถูกปล่อยทิ้งไว้ตามที่เป็นอยู่
สามารถใช้เพื่อค้นหาองค์ประกอบที่ใหญ่ที่สุดหากเราใช้วัตถุฟังก์ชันเพื่อจัดเรียงสำหรับตำแหน่งแรก
ตัวอย่าง
#include #include #include โดยใช้ namespace std int main () {vector vec = {10, 45, 60, 78, 23, 21, 30} vector :: iterator iptr partial_sort (vec.begin (), vec.begin () + 1, vec.end (), มากกว่า ()) iptr = vec.begin () cout<< 'The largest element is = ' << *iptr return 0 } เอาท์พุต:
คำอธิบาย:
โค้ดด้านบนสามารถใช้เพื่อค้นหาจำนวนที่มากที่สุดในอนุกรมเพื่อค้นหาจำนวนที่น้อยที่สุดในอนุกรมเราเพียงแค่ต้องลบคำสั่งที่มากขึ้น
ดังนั้นเราจึงมาถึงตอนท้ายของบทความนี้เกี่ยวกับ 'Sort Function in C ++' หากคุณต้องการเรียนรู้เพิ่มเติมโปรดดู Java Training โดย Edureka บริษัท การเรียนรู้ออนไลน์ที่เชื่อถือได้ Edureka’s หลักสูตรได้รับการออกแบบมาเพื่อฝึกอบรมคุณสำหรับแนวคิด Java ทั้งหลักและขั้นสูงพร้อมกับกรอบงาน Java ต่างๆเช่น Hibernate & Spring
ตัวสร้างสามารถเป็นส่วนตัวได้
มีคำถามสำหรับเรา? โปรดระบุไว้ในส่วนความคิดเห็นของบล็อกนี้และเราจะติดต่อกลับโดยเร็วที่สุด