DAA - การเรียงลำดับการเลือก

การเรียงลำดับประเภทนี้เรียกว่า Selection Sortเนื่องจากทำงานโดยการจัดเรียงองค์ประกอบซ้ำ ๆ มันทำงานดังนี้: อันดับแรกค้นหาที่เล็กที่สุดในอาร์เรย์และแลกเปลี่ยนกับองค์ประกอบในตำแหน่งแรกจากนั้นค้นหาองค์ประกอบที่เล็กที่สุดอันดับสองและแลกเปลี่ยนกับองค์ประกอบในตำแหน่งที่สองและดำเนินการต่อในลักษณะนี้จนกว่าอาร์เรย์ทั้งหมดจะเป็น จัดเรียง.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

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

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

อย่างไรก็ตามเวลาที่อัลกอริทึมการจัดเรียงแบบเลือกต้องใช้ไม่ไวต่อลำดับดั้งเดิมของอาร์เรย์ที่จะจัดเรียง: ทดสอบว่า A[j] < min x จะดำเนินการในจำนวนครั้งเท่ากันทุกกรณี

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

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

แต่ละ i จาก 1 ถึง n - 1มีการแลกเปลี่ยนและ n - i การเปรียบเทียบดังนั้นจึงมีทั้งหมด n - 1 การแลกเปลี่ยนและ

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 การเปรียบเทียบ

ข้อสังเกตเหล่านี้ถือไม่ว่าข้อมูลที่ป้อนจะเป็นอย่างไร

ในกรณีที่แย่ที่สุดนี่อาจเป็นกำลังสอง แต่ในกรณีโดยเฉลี่ยปริมาณนี้คือ O(n log n). หมายความว่าไฟล์running time of Selection sort is quite insensitive to the input.

การนำไปใช้

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}