จะใช้การเรียงลำดับการเลือกใน C ได้อย่างไร

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

ตัวอย่างการเรียงลำดับ Selection ในภาษาซี

หากเรานำอาร์เรย์ที่มีตัวเลข [10,2,8,4,6] ซึ่งจำนวนที่น้อยที่สุดคือ 2 ดังนั้น เราจะวางจำนวนที่น้อยที่สุดซึ่งก็คือ 2 ในตำแหน่งแรก หลังจากนั้นอาร์เรย์จะมีลักษณะ เช่น [2,10,8,4,6] ต่อไปเราจะใช้จำนวนที่น้อยที่สุดถัดไป เพราะ 2 อยู่ในตำแหน่งที่ถูกต้องแล้ว จำนวนที่น้อยที่สุดถัดไปคือ 4 ซึ่งจะถูกวางไว้ในตำแหน่งที่สอง หลังจากนั้นอาร์เรย์จะถูกค้นหาในทำนองเดียวกันจนกว่าจะถูกจัดเรียงในที่สุด

การเรียงลำดับการเลือกใน C จะเรียงลำดับตัวเลขจากน้อยไปหามาก การแก้ไขอัลกอริทึมทำให้สามารถจัดเรียงตัวเลขใน Selection Sort จากมากไปหาน้อยได้ นอกจากนี้ยังสามารถดำเนินการในภาษาอื่นนอกเหนือจาก C เช่น Selection Sort C++ หรือ Selection Sort Python

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

อัลกอริทึมการเรียงลำดับการเลือก

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

หลักสูตรและบทความยอดนิยมเกี่ยวกับวิศวกรรมซอฟต์แวร์

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

ทำซ้ำ #1

ฉัน [ ] = 8,5,2,6,4

ตั้งค่าขั้นต่ำ - 8

เปรียบเทียบ i 0 และ i 1

เช่น i 0 > i 1 ตั้งค่าขั้นต่ำ = 5

• เปรียบเทียบ i 1 กับ i 2

เช่น i 1 > i 2 ตั้งค่าค่าต่ำสุด = 2

• เปรียบเทียบ i 2 และ i 3

เช่น i 2 < i 3 ตั้งค่าค่าต่ำสุด= 2

• เปรียบเทียบ i 2 และ i 4

เช่น i 2 < i 4 ตั้งค่าค่าต่ำสุด =2

2 เป็นจำนวนที่น้อยที่สุดในบรรดาองค์ประกอบทั้งหมด เราต้องสลับ i 0 กับ i 2

­ การทำซ้ำ #2

ฉัน [ ]= 2,5,8,6,4

ตั้งขั้นต่ำ5

• เปรียบเทียบ i 1 กับ i 2

เช่น i 1 < i 2 ตั้งค่าขั้นต่ำ = 5

• เปรียบเทียบ i 1 และ i 3

เมื่อ i 1 < i 3 ตั้งค่าค่าต่ำสุด = 5

• เปรียบเทียบ i 1 และ i 4

อีกครั้ง i 1 < i 4 ตั้งค่าขั้นต่ำ = 4

4 เป็นองค์ประกอบที่เล็กที่สุดในอาร์เรย์ ดังนั้น เราต้องสลับ i 1 และ i 4

การทำซ้ำ #3

ฉัน [ ]= 2,4,8,6,5

ตั้งขั้นต่ำ8

• เปรียบเทียบ i 2 และ i 3

เช่น i 2 > i 3 ตั้งค่าขั้นต่ำ = 6

• เปรียบเทียบ i 3 และ i 4

เช่น i 3 > i 4 ตั้งค่าขั้นต่ำ = 5

5 เป็นองค์ประกอบที่เล็กที่สุดในอาร์เรย์ คุณต้องสลับ i 2 และ i 4

การทำซ้ำ #4

ฉัน [ ] = 2,4,5,6,8

ตั้งขั้นต่ำ6

• เปรียบเทียบ i 3 และ i 4

เมื่อ i 3 < i 4 ตั้งค่าค่าต่ำสุด = 6

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

ตัวอย่างการเรียงลำดับการเลือกในภาษาซี

// เรียงลำดับการเลือกในภาษาซี

#รวม <stdio.h>

// ฟังก์ชั่นสลับตำแหน่งของสององค์ประกอบ

การแลกเปลี่ยนเป็นโมฆะ (int *a, int *b) {

อุณหภูมิ int = *a;

*ก = *ข;

*b = อุณหภูมิ;

}

ถือเป็นโมฆะ SelectionSort (int อาร์เรย์ [], ขนาด int) {

สำหรับ (int step = 0; step <ขนาด – 1; step++) {

int min_idx = ขั้นตอน;

สำหรับ (int i = step + 1; i <ขนาด; i++) {

// หากต้องการเรียงลำดับจากมากไปน้อย ให้เปลี่ยน > เป็น < ในบรรทัดนี้

// เลือกองค์ประกอบขั้นต่ำในแต่ละลูป

ถ้า (อาร์เรย์[i] < อาร์เรย์[min_idx])

min_idx = ฉัน;

}

// ใส่ min ที่ตำแหน่งที่ถูกต้อง

สลับ (&อาร์เรย์[min_idx], &อาร์เรย์[ขั้นตอน]);

}

}

// ฟังก์ชันพิมพ์อาร์เรย์

เป็นโมฆะ printArray (int อาร์เรย์ [], ขนาด int) {

สำหรับ (int i = 0; i <ขนาด; ++i) {

printf(“%d“, อาร์เรย์[i]);

}

printf(“\n”);

}

// รหัสไดรเวอร์

int หลัก () {

ข้อมูล int[] = {20, 12, 10, 15, 2};

ขนาด int = sizeof (ข้อมูล) / sizeof (ข้อมูล [0]);

SelectionSort (ข้อมูล, ขนาด);

printf(“เรียงอาร์เรย์ตามลำดับ:\n”);

printArray(ข้อมูล, ขนาด);

}

การวิเคราะห์ความซับซ้อนของการเรียงลำดับการเลือก

อินพุต – n รายการอินพุตจะได้รับ

เอาต์พุต – จำนวนขั้นตอนที่จำเป็นในการเรียงลำดับรายการ

ลอจิก – ถ้าเราได้รับ n รายการ มันจะทำการเปรียบเทียบ n-1 ในรอบแรก, n-2 เปรียบเทียบในรอบที่สอง, n-3 เปรียบเทียบในรอบที่สาม และอื่นๆ ดังนั้น จำนวนรวมของการเปรียบเทียบอาจคำนวณได้โดยใช้

เอาท์พุต –

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

ผลรวม = n(n-1)/2 เช่น O(n²)

เนื่องจากวิธีการเรียงลำดับแบบเลือกต้องการพื้นที่หน่วยความจำเพิ่มเติมสำหรับตัวแปรชั่วคราวสำหรับการสลับ จึงมีความซับซ้อนของเวลาเท่ากับ O(n2) และความซับซ้อนของพื้นที่เท่ากับ O(1)

การวิเคราะห์ความซับซ้อนของการเรียงลำดับเวลา

กรณีที่ดีที่สุด: สำหรับอาร์เรย์ที่มีการเรียงลำดับก่อนหน้านี้ วิธีการเรียงลำดับแบบเลือกจะมีความซับซ้อนของเวลาในกรณีที่ดีที่สุดเท่ากับ O(n²)

กรณีเฉลี่ย: อัลกอริทึมการเรียงลำดับการเลือกมีความซับซ้อนของเวลาเฉลี่ยกรณีและปัญหาเท่ากับ O(n²) เมื่อรายการถูกจัดเรียงแบบสับสน กล่าวคือ ไม่ได้เรียงลำดับจากน้อยไปหามากหรือจากมากไปน้อย

Worst Case: เมื่อเรากลับลำดับจากมากไปน้อยของอาร์เรย์เป็นลำดับจากน้อยไปมาก ความซับซ้อนของเวลาที่เลวร้ายที่สุดคือ O(n²)

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

บทสรุป

นี่เป็นการปิดบล็อกโพสต์เรื่อง “Selection Sort In C” คุณต้องเข้าใจว่าสามารถดำเนินการในภาษาอื่นได้เช่นกัน เช่น Selection Sort C++ และ Selection Sort Python เราหวังว่าบทความนี้จะช่วยให้คุณเข้าใจวิธีการจัดเรียงองค์ประกอบในภาษาซี

การเรียงลำดับการเลือกไม่ได้เป็นเพียงส่วนเดียวในการเดินทางสู่การเป็นโปรแกรมเมอร์ หากคุณหวังว่าจะได้รับการส่งเสริมที่สำคัญในอาชีพการพัฒนาซอฟต์แวร์ของคุณด้วยวุฒิการศึกษาระดับมืออาชีพ upGrad อยู่ที่นี่แล้ว! การพัฒนาส่วนหน้าของ upGrad (JavaScript, HTML, CSS), แบ็กเอนด์ (NoSQL-MongoDB) และไมโครเซอร์วิส จากนั้นคุณสามารถเรียนหลักสูตรวิทยาศาสตรมหาบัณฑิตสาขาวิทยาการคอมพิวเตอร์ของ UpGrad ได้ จัดทำโดย IIIT Bangalore & LJMU Alumni Status หลักสูตรนี้ช่วยให้คุณมีอาชีพเป็นวิศวกรซอฟต์แวร์/นักพัฒนาฟูลสแตกกับยักษ์ใหญ่ด้านเทคโนโลยีทั่วโลก

หลักสูตรนี้ครอบคลุมความรู้พื้นฐานของเครื่องมือต่างๆ เช่น Java, Spring และ Hibernate ซึ่งจะช่วยเสริมทักษะการพัฒนาแบบฟูลสแต็กของเราเพื่อสำรวจตลาดงานด้วยโอกาสที่น่าทึ่ง

ลงทะเบียน เพื่อเรียนรู้เพิ่มเติม!