อัลกอริทึมการเรียงลำดับแบบแทรกด้วยภาษาซี C++, Java, Python ตัวอย่าง

การเรียงลำดับการแทรกคืออะไร?

การเรียงลำดับแบบแทรก (Insertion Sort) เป็นหนึ่งในอัลกอริธึมการเรียงลำดับแบบเปรียบเทียบที่ใช้ในการเรียงลำดับองค์ประกอบโดยการวนซ้ำทีละองค์ประกอบและวางองค์ประกอบนั้นในตำแหน่งที่ถูกต้องภายในพื้นที่ที่เรียงลำดับไว้แล้ว

แต่ละองค์ประกอบจะถูกแทรกเข้าไปในรายการที่เรียงลำดับแล้วตามลำดับ โดยขนาดของรายการที่เรียงลำดับแล้วในตอนเริ่มต้นคือหนึ่ง อัลกอริทึมการเรียงลำดับแบบแทรก (Insertion Sort) รับประกันว่าองค์ประกอบ k ตัวแรกจะถูกเรียงลำดับหลังจากวนซ้ำครั้งที่ k ของลูปภายนอก

เนื่องจาก Insertion Sort สร้างผลลัพธ์ทีละน้อย จึงสอนได้ง่าย แก้ไขข้อผิดพลาดได้ง่าย และเป็นพื้นฐานที่ดีสำหรับข้อมูลขนาดเล็กมาก ซึ่งอัลกอริทึมที่ซับซ้อนกว่าจะเพิ่มภาระโดยไม่ให้ผลลัพธ์ที่วัดได้

ลักษณะของอัลกอริทึมการเรียงลำดับการแทรก

อัลกอริทึมการเรียงลำดับแบบแทรก (Insertion Sort) มีลักษณะสำคัญดังต่อไปนี้ ซึ่งอธิบายถึงพฤติกรรมของมันในงานจริง:

• เป็นเทคนิคการเรียงลำดับที่มีความเสถียร จึงไม่เปลี่ยนลำดับสัมพัทธ์ขององค์ประกอบที่เท่ากัน
• วิธีนี้มีประสิทธิภาพสำหรับชุดข้อมูลขนาดเล็ก แต่ไม่มีประสิทธิภาพสำหรับรายการขนาดใหญ่ที่การเติบโตแบบกำลังสองเป็นหลัก
• การเรียงลำดับแบบแทรก (Insertion Sort) เป็นแบบปรับตัวได้ ซึ่งจะลดจำนวนขั้นตอนทั้งหมดลงหากข้อมูลป้อนเข้าได้รับการเรียงลำดับบางส่วนแล้ว แถว มีการให้ข้อมูลป้อนเข้าเพื่อให้มีประสิทธิภาพ เนื่องจากวิธีการเข้าถึงแบบสุ่มช่วยให้สามารถเลื่อนข้อมูลได้ในเวลาคงที่ระหว่างลูปภายใน
• เป็นอัลกอริทึมแบบ in-place ดังนั้นจึงไม่จำเป็นต้องใช้พื้นที่จัดเก็บข้อมูลเสริมตามสัดส่วนของขนาดข้อมูลอินพุต

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

แทรกอย่างไร Operaทำงานเหรอ?

ในอัลกอริทึมการเรียงลำดับแบบแทรก (Insertion Sort) การดำเนินการแทรกใช้เพื่อเรียงลำดับองค์ประกอบที่ยังไม่ได้เรียงลำดับ โดยจะช่วยแทรกองค์ประกอบใหม่เข้าไปในรายการที่เรียงลำดับแล้ว ในขณะที่ยังคงรักษาลำดับเดิมของส่วนที่เรียงลำดับไว้

รหัสเทียมของการดำเนินการแทรก:

พิจารณารายการ A ขององค์ประกอบ N

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

ในตัวอย่างข้างต้น มีการแทรกองค์ประกอบใหม่หมายเลข 6 เข้าไปในรายการที่เรียงลำดับแล้ว ขั้นตอนต่อไปนี้ trace วงในขณะที่องค์ประกอบใหม่เคลื่อนที่ไปทางซ้ายไปยังตำแหน่งที่ถูกต้อง

ขั้นตอน 1) เมื่อเปรียบเทียบกับองค์ประกอบที่อยู่ติดกันทางซ้ายของ A[5], 9 > 6 เราจะสลับตำแหน่งที่ 9 และ 6 ตอนนี้องค์ประกอบที่ 6 ถูกย้ายไปที่ A[4]

ขั้นตอน 2) ตอนนี้ เราเปรียบเทียบ A[4] และ A[3] และเราพบว่า A[3] > A[4] ดังนั้นเราจึงสลับตำแหน่งของ 6 และ 8 อีกครั้ง

ขั้นตอน 3) ตอนนี้เปรียบเทียบ A[3] และ A[2] เนื่องจาก A[2] > A[3] เราจึงสลับตำแหน่งของ 7 และ 6

ขั้นตอน 4) เราเปรียบเทียบ A[1] และ A[2] เนื่องจาก A[1] < A[2] องค์ประกอบที่อยู่ติดกันทางซ้ายจึงไม่มากกว่าอีกต่อไป เราสรุปได้ว่า 6 ถูกแทรกอย่างถูกต้อง และเราหยุดลูปภายในตรงนี้

การเรียงลำดับการแทรกทำงานอย่างไร

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

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

เมื่อวางโครงสร้างแนวคิดไว้แล้ว ส่วนต่อไปนี้จะแสดงตัวอย่างการนำไปใช้จริง C++, ซี และ Python เพื่อให้คุณสามารถเปรียบเทียบโครงสร้างลูปในภาษาต่างๆ ได้

C++ โปรแกรมสำหรับการเรียงลำดับการแทรก

การขอ C++ การใช้งานด้านล่างนี้ใช้ลูปซ้อนกันสองชั้น: ลูปภายนอกจะเลือกองค์ประกอบที่ยังไม่ได้เรียงลำดับถัดไป และลูปภายในจะเลื่อนองค์ประกอบนั้นไปทางซ้ายจนกว่าจะพบตำแหน่งที่ถูกต้อง

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

Output:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code สำหรับการเรียงลำดับแบบแทรก

ตรรกะเดียวกันนี้สามารถนำไปใช้กับภาษา C ได้โดยตรง มาตรฐาน printf การเรียกจะแทนที่เอาต์พุตของสตรีม แต่รูปแบบการสลับภายในลูปด้านในนั้นเหมือนกับ C++ รุ่น

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Output:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python โปรแกรมสำหรับการเรียงลำดับการแทรก

Python รองรับการสลับทูเพิลping ในนิพจน์เดียว ดังนั้นลูปภายในจึงกระชับกว่าลูป C และ C++ โดยคงพฤติกรรมของอัลกอริทึมแบบเดิมไว้

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Output:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

คุณสมบัติของการเรียงลำดับการแทรก

ต่อไปนี้คือคุณสมบัติสำคัญของการเรียงลำดับแบบแทรก (Insertion Sort) ที่จะช่วยให้คุณตัดสินใจได้ว่าเมื่อใดควรใช้เครื่องมือนี้:

• ออนไลน์: อัลกอริทึมการเรียงลำดับแบบแทรก (Insertion Sort) สามารถเรียงลำดับองค์ประกอบได้ทันทีที่ได้รับ หากเราได้เรียงลำดับรายการองค์ประกอบไว้แล้ว และต้องการเพิ่มองค์ประกอบใหม่เข้าไปในรายการ เราไม่จำเป็นต้องดำเนินการเรียงลำดับทั้งหมดอีกครั้ง แต่เราจะวนซ้ำเฉพาะกับองค์ประกอบที่เพิ่มเข้ามาใหม่เท่านั้น
• ในสถานที่: ความซับซ้อนของพื้นที่ในการทำงานของอัลกอริทึม Insertion Sort นั้นคงที่และไม่ต้องการพื้นที่เพิ่มเติม อัลกอริทึมนี้จะเรียงลำดับองค์ประกอบในตำแหน่งเดิม
• เสถียร: ในการเรียงลำดับแบบแทรก (Insertion Sort) เราจะไม่สลับตำแหน่งขององค์ประกอบหากค่าขององค์ประกอบเหล่านั้นเท่ากัน ตัวอย่างเช่น หากองค์ประกอบสองตัวคือ x และ y มีค่าเท่ากัน และ x ปรากฏอยู่ก่อน y ในรายการที่ยังไม่เรียงลำดับ ในรายการที่เรียงลำดับแล้ว x ก็จะยังคงปรากฏอยู่ก่อน y เช่นกัน ซึ่งทำให้การเรียงลำดับแบบแทรกมีความเสถียร
• ปรับตัว: A อัลกอริทึมการเรียงลำดับ เรียกว่าอัลกอริทึมการเรียงลำดับแบบปรับตัวได้ หากใช้เวลาน้อยลงเมื่อองค์ประกอบอินพุตหรือกลุ่มย่อยขององค์ประกอบได้รับการเรียงลำดับแล้ว ดังที่เราได้กล่าวไว้ข้างต้น เวลาในการทำงานที่ดีที่สุดของ Insertion Sort คือ O(N) และเวลาในการทำงานที่แย่ที่สุดคือ O(N^2) Insertion Sort เป็นหนึ่งในอัลกอริทึมการเรียงลำดับแบบปรับตัวได้

ความซับซ้อนของการเรียงลำดับแบบแทรก

การอภิปรายเรื่องความซับซ้อนด้านล่างนี้ครอบคลุมทั้งการใช้หน่วยความจำและเวลาในการทำงาน เพื่อให้คุณสามารถเปรียบเทียบ Insertion Sort กับทางเลือกอื่นๆ ได้ เช่น Bubblอีเรียงลำดับ และ จัดเรียงด่วน.

ความซับซ้อนของอวกาศ

การเรียงลำดับแบบแทรก (Insertion Sort) ไม่ต้องการพื้นที่เพิ่มเติมในการเรียงลำดับองค์ประกอบ ความซับซ้อนของพื้นที่คงที่ กล่าวคือ O(1) เนื่องจากมีการใช้ตัวแปรชั่วคราวเพียงไม่กี่ตัวเท่านั้น โดยไม่คำนึงถึงขนาดของข้อมูลนำเข้า

ความซับซ้อนของเวลา

เนื่องจากอัลกอริทึมการเรียงลำดับแบบแทรก (Insertion Sort) จะเรียงลำดับองค์ประกอบทีละหนึ่งรายการ จึงต้องใช้ N-1 รอบในการเรียงลำดับองค์ประกอบ N รายการ ในแต่ละรอบ อาจไม่มีการสลับตำแหน่งเลยหากองค์ประกอบถูกเรียงลำดับแล้ว หรืออาจต้องมีการสลับตำแหน่งหลายครั้งหากองค์ประกอบถูกจัดเรียงในลำดับจากมากไปน้อย

• สำหรับบัตรผ่าน 1 ค่าสวอปขั้นต่ำที่ต้องการคือศูนย์ และค่าสวอปสูงสุดที่ต้องการคือ 1
• สำหรับบัตรผ่าน 2 ค่าสวอปขั้นต่ำที่ต้องการคือศูนย์ และค่าสวอปสูงสุดที่ต้องการคือ 2
• สำหรับ pass N ค่า swap ขั้นต่ำที่ต้องการคือศูนย์ และค่า swap สูงสุดที่ต้องการคือ N
• การสลับขั้นต่ำคือศูนย์ ดังนั้นความซับซ้อนของเวลาที่ดีที่สุดคือ O(N) สำหรับการวนซ้ำ N ครั้ง
• จำนวนการสลับสูงสุดทั้งหมดคือ (1+2+3+4+…+N) หรือ N(N+1)/2 ดังนั้นความซับซ้อนของเวลาที่แย่ที่สุดคือ O(N^2)

ต่อไปนี้คือข้อมูลสำคัญเกี่ยวกับความซับซ้อนของเวลาในการเรียงลำดับแบบแทรก (Insertion Sort):

• ความซับซ้อนของกรณีที่เลวร้ายที่สุด: O(n^2): การเรียงลำดับอาร์เรย์จากมากไปน้อยเมื่อต้องการให้เรียงจากน้อยไปมากเป็นสถานการณ์ที่เลวร้ายที่สุด
• ความซับซ้อนของเคสที่ดีที่สุด: O(n): กรณีที่ดีที่สุดเกิดขึ้นเมื่ออาร์เรย์เรียงลำดับแล้ว ลูปภายนอกจะทำงาน n ครั้ง ในขณะที่ลูปภายในจะไม่ทำงานเลย มีการเปรียบเทียบเพียง n ครั้ง ดังนั้นความซับซ้อนจึงเป็นเชิงเส้น
• ความซับซ้อนของเคสโดยเฉลี่ย: O(n^2): เหตุการณ์นี้เกิดขึ้นเมื่อองค์ประกอบของอาร์เรย์เรียงลำดับไม่ตรงกัน ไม่ใช่ทั้งจากน้อยไปมากหรือจากมากไปน้อย

คำถามที่พบบ่อย