Selection Sort

Selection Sort
     การเรียงลำดับแบบเลือกไม่เพียงง่ายต่อการเข้าใจแล้ว ก็ง่ายต่อการวิเคราะห์ด้วยเพราะว่าข้อมูลที่อยู่ในรายการนั้นแทบไม่มีผลต่อการทำงานของการเรียงลำดับแบบเลือกเลย เริ่มด้วยส่วนของการเลือกค่าที่เหมาะสมที่สุด (มากสุดหรือน้อยสุด) จากข้อมูลส่วนที่ยังไม่เรียงนั้นหากในส่วนนี้มีข้อมูลอยู่ n ตัว ก็จะเปรียบเทียบอย่างน้อย n-1 ครั้ง เมื่อได้ค่าเหมาะสมที่สุดแล้วก็สลับกับตัวแรกของส่วนที่ยังไม่เรียง แล้วลดขนาดของส่วนที่ยังไม่เรียงลงหนึ่ง แล้วก็หาค่าเหมาะสมที่สุดใหม่อีกครั้ง และแน่นอนส่วนที่ยังไม่เรียงก็จะเหลือข้อมูล n-1 ตัว (ก็ต้องเปรียบเทียบ n-2 ครั้ง) ทำเช่นนั้นไปเรื่อยๆดังนั้นจำนวนการเปรียบเทียบทั้งหมดเท่ากับ 


 ตัวอย่างทีละขั้นตอน

การเรียงลำดับข้อมูลในรายการดังนี้ 64 25 12 22 11 ด้วยขั้นตอนวิธีแบบเลือก เริ่มต้นถือว่าทุกตัวในรายการยังไม่เรียง
ครั้งที่ 1 หาตัวที่มีค่าน้อยที่สุดในรายการส่วนที่ยังไม่เรียงนั่นคือ 11 สลับกับตัวแรกของข้อมูลที่ยังไม่เรียงนั่นคือ 64
(64 25 12 22 11)  (11 25 12 22 64)
ครั้งที่ 2 หาตัวที่มีค่าน้อยที่สุดนั่นคือ 12 สลับกับตัวแรกนั่นคือ 25
(11 25 12 22 64)  (11 12 25 22 64)
ครั้งที่ 3 หาตัวที่มีค่าน้อยที่สุดนั่นคือ 22 สลับกับตัวแรกนั่นคือ 25
(11 12 25 22 64)  (11 12 22 25 64)
เรียงเสร็จเรียบร้อย


Algorithms Selection
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<script>
var a = [4, 1, 3, 5, 2, 6];
function selectionSort(a) { 
    var length = a.length;
    for (var i = 0; i < length - 1; i++) {
        var min = i;
        for (var j = i + 1; j < length; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        if (min != i) {
            var tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}
console.log(a);
selectionSort(a);
console.log(a);
</script>

ไม่มีความคิดเห็น:

แสดงความคิดเห็น

สมัครสมาชิก: บทความ (Atom)