การจัดเรียง (Sort)

ปรับปรุง : 2566-01-20 (ปรับรุ่นเป็น 9.0)

การเรียงลำดับข้อมูล (Sorting)

การเรียงลำดับข้อมูล (Sorting) คือ การนำชุดข้อมูลมาดำเนินการประมวลผลให้ได้ชุดข้อมูลใหม่ที่มีการจัดเรียงใหม่ ซึ่งผลการจัดเรียงอาจเรียงข้อมูลจากน้อยไปมาก (Ascending) หรือมากไปน้อย (Descending)

อาร์เรย์ (Array) หรือแถวลำดับ คือ การรวมกลุ่มของตัวแปรที่สามารถใช้ตัวแปร ชื่อเดียวกันแทนข้อมูลสมาชิกได้หลายตัวในคราวเดียว ด้วยการใช้เลขดรรชนี (Index) หรือซับสคริปต์ (Subscipt) เป็นตัวอ้างอิงตำแหน่งสมาชิกบนแถวลำดับนั้น [3]p.80

+ sort_sample.xlsx
+ https://en.wikipedia.org/wiki/Sorting_algorithm

Code : Data Structures

เรื่องยกกำลัง และ log [3]p.59
ถ้ามีข้อมูล 10 ตัว ก็จะได้ n = 10
กรณีที่ 1 : linear loops
for(i = 0; i<n; i++) ...
ได้ O(n)

กรณีที่ 2 : nested loops
for(i = 0; i<n; i++) ...
for(j = 0; j<n; j++) ...
ได้ O(n²)

กรณีที่ 3 : logarithmic loops
for(i = 0; i<n; i*=2) ...
ได้ O(log n)

กรณีที่ 4 : nested loops
for(i = 0; i<n; i++) ...
for(j = 0; j<n; j*=2) ...
ได้ O(n log n)

ประสิทธิภาพของการเรียงลำดับข้อมูล 
หรือ BigO ของการจัดเรียงข้อมูลแต่ละแบบ [3]p.334
1. แบบ Selection Sort คือ O(n²)
2. แบบ Heap Sort คือ O(n log n)
3. แบบ Insertion Sort คือ O(n²)
4. แบบ Bubble Sort คือ O(n²)
5. แบบ Quick Sort คือ O(n log n)
6. แบบ Merge Sort คือ O(n log n)

เทียบเวลาการทำงานของฟังก์ชันเมื่อส่งค่า 50 หรือ 100 ข้อมูล [3]p.64
ลำดับ	ฺBigO	f(50)	f(100)
1	O(logn)	5.64	6.64
2	O(n)	50	100
3	O(nlogn)	282	664
4	O(n²)	2500	10,000
5	O(n³)	12,500	100,000
6	O(2ⁿ)	1.126 * 10¹⁵	1.27 * 10³⁰
7	O(n!)	3.0 * 10⁶⁴	9.3 * 10¹⁵⁷

factorial คือ ผลคูณของจำนวนเต็มบวกทั้งหมดที่น้อยกว่าหรือเท่ากับ n
สามารถเขียนแทนด้วย n!

Flash กับ Arrow
ความเร็ว และแม่นยำ มีความสำคัญมาก นึกถึง google กับ yahoo

รหัสต้นฉบับด้วยภาษาจาวา 10 แบบ
- แบบ 1 Bubble Sort(2dim)
- แบบ 2 Selection Sort
- แบบ 3 Insertion Sort
- แบบ 4 Binary Sort
- แบบ 5 Bucket Sort
- แบบ 6 Quick Sort
- แบบ 7 Shell Sort
- แบบ 8 Merge Sort
- แบบ 9 Radix Sort #
- แบบ 10 Heap Sort #
- จัดเรียง 3 แบบ main + Dyn
- แนวคิด sorting (Applet) ubc.ca #

Godzilla 1998 สนใจเรื่อง Size

หนังสือ Data Structures: A Pseudocode Approach with C
Bubble Sort Algorithm

Data Structures: A Pseudocode Approach with C
By Richard F. Gilberg, Behrouz A. Forouzan
Book in github.com

Selection Sort (ม.พะเยา)
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Algorithm selectionSort (list,last)
/* Pre     list must contain at least one item
            last contains index to last element in the list
    Post    list has been rearranged smallest to largest
*/
1   set current to 0
2   loop (until last element sorted)
    1   set smallest to current
    2   set walker to current + 1
    3   loop (walker <= last)
        1   if (walker key < smallest key)
            1   set smallest to walker
        2   end if
        3 increment walker
    4   end loop
        // หน่วยที่เล็กที่สุด เปลี่ยนกับตำแหน่งปัจจุบัน
    5   exchange (current, smallest)
    6   increment current
3   end loop
end selectionSort
Bubble Sort (ม.พะเยา)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* Pre     list must contain at least one item
            last contains index to last element in the list
    Post    list has been rearranged in sequence low to high
*/
Algorithm bubbleSort (list, last)
1   set current to 0
2   set sorted to false // default not finish before loop
3   loop (current <= last AND sorted = false)
        // ทุกการทำซ้ำ เป็นการจัดเรียง
    1   set walker to last
    2   set sourted to true // default finish in loop
    3   loop (walker > current)
        1   if (walker data < walker - 1 data)
                // หากสลับตำแหน่ง แสดงว่าการจัดเรียงยังไม่จบ
            1   set sorted to false // it is not finish
            2   exchange (list, walker, walker - 1)
        2   end if
        3   decrement walker
    4   end loop
    5   increment current
4   end loop
end bubblesort

Algorithm : การจัดเรียงแบบ Bubble sort ด้วยภาษา Pascal [3]p.319
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
procedure <b>bubbleSort</b>( A : list of sortable items )
   n = length(A)
   repeat
     swapped = false
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure
+ https://en.wikipedia.org/wiki/Bubble_sort

Algorithm : Bubble Sort

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<script>
var a = [4, 1, 3, 5, 2, 6];
function bubbleSort(a)
{
    var swapped;
    do {
        swapped = false;
        for (var i=0; i < a.length-1; i++) {
            if (a[i] > a[i+1]) {
                var temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swapped = true;
            }
        }
    } while (swapped);
}
console.log(a);
bubbleSort(a);
console.log(a);
</script>
+ อ้างอิงจาก http://www.stoimen.com

Algorithm : Selection Sort

?
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>
+ อ้างอิงจาก http://codingmiles.com

Algorithm : Quick Sort

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<script>
var a = [4, 1, 3, 5, 2, 6];
console.log(a);
quickSort(a, 0, a.length -1);
console.log(a);
function quickSort(arr, left, right)
{
    var i = left;
    var j = right;
    var tmp;
    pivotidx = (left + right) / 2;
    var pivot = parseInt(arr[pivotidx.toFixed()]);
    /* partition */
    while (i <= j)
    {
        while (parseInt(arr[i]) < pivot)     i++;
        while (parseInt(arr[j]) > pivot)     j--;
        if (i <= j)
        {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    /* recursion */
    if (left < j) quickSort(arr, left, j);
    if (i < right) quickSort(arr, i, right);
    return arr;
}
</script>
+ อ้างอิงจาก https://stackoverflow.com

Algorithm : Heap Sort

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
<script>
var a = [4, 1, 3, 5, 2, 6];
console.log(a);
heapSort(a);
console.log(a);

function swap(a, i, j) {
    var tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

function max_heapify(a, i, length) {
    while (true) {
        var left = i*2 + 1;
        var right = i*2 + 2;
        var largest = i;

        if (left < length && a[left] > a[largest]) {
            largest = left;
        }

        if (right < length && a[right] > a[largest]) {
            largest = right;
        }

        if (i == largest) {
            break;
        }

        swap(a, i, largest);
        i = largest;
    }
}

function heapify(a, length) {
    for (var i = Math.floor(length/2); i >= 0; i--) {
        max_heapify(a, i, length);
    }
}

function heapSort(a) {
    heapify(a, a.length);
    for (var i = a.length - 1; i > 0; i--) {
        swap(a, i, 0);
        max_heapify(a, 0, i-1);
    }
}
</script>
+ อ้างอิงจาก https://gist.github.com

Algorithm : Visualization and Comparison of Sorting Algorithms

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

Heap Sort p.344
เริ่มต้นจากมีข้อมูลในอาร์เรย์แบบ Heap Tree คือ Node พ่อจะมีค่ามากกว่าโหนดลูก นั่นคือ Root node มีค่ามากที่สุด ซึ่งค่ามากที่สุดจะอยู่ตำแหน่งแรก เมื่อจัดเรียงค่าน้อยไปมาก เริ่มจากย้ายค่ามากที่สุดจากตำแหน่งแรกหรือต้นอาร์เรย์ไปตำแหน่งอาร์เรย็สุดท้าย ท้าย node ของ heap ตัวสุดท้าย ถือว่าจัดแล้ว และให้กลับไปเริ่มต้นใหม่ คือ reheap ใหม่ .. ด้วยการ นำโหนดใหม่ที่อยู่ท้ายสุดที่ยังไม่ผ่านการจัดเรียงมาเป็น root หรือ parent แล้ว reheap โดยเริ่มจากการเปรียบเทียบกับ child ทั้ง 2 (ซ้าย,ขวา) จากนั้นสลับตำแหน่งกันกับตัวที่มากกว่า เมื่อสลับแล้ว root ใหม่ก็จะมีมาค่ามากสุด ให้ย้ายไปอยู่ต่อท้ายอาร์เรย์ที่ผ่านการจัดเรียงแล้ว แล้วทำเหมือนเดิม
Insertion Sort p.351
การเรียงด้วยการสลับตำแหน่งที่อยู่ติดกัน เริ่มจากตำแหน่งแรก
เริ่มจากเทียบตัวแรก กับตัวถัดไป หากตัวถัดไปมากกว่าก็จะสลับกัน หากไม่ก็จะจับคู่ใหม่คือตัวที่สองกับสาม สามสี สี่ห้า หากตัวถัดไปน้อยกว่าตัวก่อนหน้า ก็จะเลือนลำดับขึ้นมาด้วยการจับคู่เทียบขึ้นมาจนถึงตำแหน่งที่ถูกต้อง ดังนั้นจำนวนรอบการทำงานจะขึ้นกับลักษณะข้อมูล
Bubble Sort p.356
การเรียงด้วยการสลับตำแหน่งจากตำแหน่งสุดท้าย หาค่าน้อยสุดขึ้นมาตำแหน่งแรก
เริ่มต้นจากอ่านตำแหน่งสุดท้าย เทียบขึ้นมาถึงบนสุด ก็คือการนำค่าน้อยที่สุดขึ้นมาถึงตำแหน่งแรก หากรอบแรกสำเร็จก็จะอ่านตัวสุดท้ายตัวใหม่ แล้วเทียบขึ้นมาถึงตำแหน่งบนสุดอีกครั้ง เพราะตัวสุดท้ายเดิมอาจยังอยู่ที่เดิม หรือเป็นตัวที่น้อยที่สุดไปแล้ว
Quick Sort p.361
การจัดเรียงคล้าย Bubble Sort ที่มีการ exchange แต่แบบนี้จะแบ่งส่วนเป็น Partition โดยข้อมูลแบ่งได้ 3 ส่วน ได้แก่ 1) ค่า pivot สำหรับแบ่งส่วน 2)ค่าที่น้อยกว่า pivot 3)ค่าที่มากกว่า pivot มีขั้นตอนดังนี้
1) ก่อนดำเนินการจะนำค่า Pivot Key ตัวแรก และค่าแรก และค่าสุดท้ายมาเรียกให้ถูกต้องก่อน นั่นคือ ตัวแรกน้อยสุด ตัวกลางค่ากลาง ตัวสุดท้ายน้อยสุด
2) หลังจากนั้น จะย้าย Pivot Key ตัวแรก สลับกับค่าแรก และให้ตัวที่อยู่ถัดค่าแรกเรียกว่า sort left และตัวสุดท้ายเรียกว่า sort right
3) ย้าย sort left ไปทางขวา แล้วย้าย sort right มาทางซ้าย จะหยุดเมื่อ sort left มากกว่า pivot key และ sort right น้อยกว่า pivot key แล้วสลับทั้ง 2 ค่า พร้อมเลื่อนต่อด้วยหลักการเดิม จน sort left กับ sort right มาพบกัน
4) ก่อนเสร็จสิ้นการแบ่ง ให้ย้ายค่าที่เคยเป็นค่าแรก (sort left) กับ pivot key หรือสลับกันนั่นเอง
5) การดำเนินการหลังแบ่งส่วนแล้ว ให้เริ่มจากด้านซ้ายของ pivot key ที่อยู่ตรงกลาง แล้วค่อยทำทางขวา แต่ละด้านทำกันใหม่ ในขณะจัดเรียงทางซ้ายก็จะแบ่งส่วนด้วย pivot key ของด้านซ้าย และแบ่งย่อยลงไปอีก ในขณะจัดเรียงทางขวาก็จะแบ่งส่วนด้วย pivot key ของด้านขวา และแบ่งย่อยลงไปอีก ทำเรื่อยไปจนแบ่งส่วนไม่ได้ ก็จะได้ผลการจัดเรียง
การเรียงแบบนี้ปรับปรุงโดย R.C.Singleton ปีค.ศ.1969 ให้เลือกค่า Pivot Key จากค่ากลาง Median Value คือตำแหน่งที่อยู่ตรงกลาง (ตำแหน่งแรก + ตำแหน่งสุดท้าย/2 แล้วปัดเศษทิ้ง)
Merge Sort p.372
กระบวนการรวมข้อมูล หรือไฟล์ 2 ไฟล์ที่ได้รับการจัดเรียงมาแล้วด้วยคีย์ มาบันทึกลงในไฟล์เดียวกัน คือ แบ่งข้อมูลออกเป็น 2 ส่วน แบ่งไปเรื่อย ๆ จนเหลือ 2 หน่วย แล้วเปรียบเทียบกัน จากนั้นก็นำทีละคู่มารวมกัน ผลการรวมกันแต่ละคู่ก็จะเป็นผลการจัดเรียง
การจัดเรียงที่นิยมใช้กับข้อมูลปริมาณมาก ที่ต้องแบ่งข้อมูลออกไปเก็บในหน่วยความจำสำรอง และนำแต่ละส่วนมาจัดเรียงในหน่วยความจำหลัก เช่น ข้อมูล 2 ล้าน 5 แสนระเบียน อาจแบ่งเป็น 3 ส่วน คือ 2 ส่วนแรกส่วนละ 1 ล้านระเบียน ส่วนสุดท้าย 5 แสนระเบียน เพราะข้อจำกัดของหน่วยความจำหลักที่ไม่อาจรับข้อมูลทั้ง 2 ล้าน 5 แสนระเบียนในคราวเดียวกัน เมื่อเรียงแต่ละส่วนจนครบทั้ง 3 ส่วนแล้ว ก็จะนำผลการจัดเรียงมารวมกัน สำหรับการจัดเรียงจะทำการแบ่งข้อมูลจนเหลือเพียง 2 ส่วน แล้วจัดเรียงกลุ่มเล็กทุกกลุ่มจนหมด แล้วนำทั้งหมดมารวมกัน ก็จะได้ผลการจัดเรียง

เอกสารฉบับเต็ม (Full Text)

รศ.ดร.สมชาย ประสิทธิ์จูตระกูล

Mark Allen Weiss

A Byte of Python

เอกสารอ้างอิง (Reference) [1] นิรุธ อำนวยศิลป์, "โครงสร้างข้อมูล : การเขียนโปรแกรมและการประยุกต์", บริษัท ดวงกมลสมัย จำกัด., กรุงเทพฯ, 2548.
[2] Guy J.Hale, Richard J.Easton, "Applied Daa Structures Using Pascal", D.C.Heath and Company. Canada. 2530.
[3] โอภาส เอี่ยมสิริวงศ์, "โครงสร้างข้อมูล (Data Structures) เพื่อการออกแบบโปรแกรมคอมพิวเตอร์", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2549.
[4] วิวัฒน์ อภิสิทธิ์ภิญโญ, อมร มุสิกสาร, "โครงสร้างข้อมูล (Data Structures)", บริษัท เอ-บุ๊ค ดิสทริบิวชั่น จำกัด., กรุงเทพฯ, 2548.
[5] เนรมิต ชุมสาย ณ อยุธยา, "เรียนรู้โครงสร้างข้อมูลและอัลกอริทึมด้วย Java", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2550.
[6] ขนิษฐา นามี, "โครงสร้างข้อมูลและอัลกอริทึม", บริษัท ไอดีซี อินโฟ ดิสทริบิวเตอร์ เซ็นเตอร์ จำกัด., กรุงเทพฯ, 2548.
[7] Michael McMillan, "Data Structures and Algorithms with JavaScript", O’Reilly Media, Inc., USA., 2014.
[8] Loiane Groner, "Learning JavaScript Data Structures and Algorithms", Packt Publishing, 2014.

ใช้เวลาโหลดเว็บเพจ: 121 มิลลิวินาที สูง: 6746 จุด กว้าง: 1264 จุด

"ไม่เริ่มต้นในวันนี้ จะไม่มีทางสำเร็จในวันพรุ่ง" โดย โยฮัน ว็อล์ฟกัง ฟ็อน เกอเทอ

หน้าหลัก

Lampang.net

Thaiabc.com

Thainame.net

เปิดรับผู้สนับสนุนเพิ่ม

OS

MIS

SWOT

LINUX

Teach Pro.

SPSS

Business

Research

Online Quiz

Data Structure

จรรยาบรรณ

อันดับสถาบัน

ปฏิทินวันหยุด

วิทยาการคำนวณ

การจัดการความรู้

เกี่ยวกับเรา

สนับสนุนเรา

Products

FB : @Thaiall

Blog : เทคโนโลยี

Thaiall.com