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

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

การเรียงลำดับแบบแทรกเป็นหนึ่งในอัลกอริทึมการเรียงลำดับแบบเปรียบเทียบที่ใช้ในการเรียงลำดับองค์ประกอบด้วยการทำซ้ำกับองค์ประกอบหนึ่งครั้งละหนึ่งองค์ประกอบและวางองค์ประกอบไว้ในตำแหน่งที่ถูกต้อง

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

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

อัลกอริทึมสำหรับการเรียงลำดับแบบแทรกมีคุณลักษณะสำคัญดังต่อไปนี้:

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

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

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

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

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

A[N-1] is the element to be inserted in the 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 จะถูกแทรกลงในรายการที่เรียงลำดับแล้ว

ขั้นตอน 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 อย่างถูกต้อง และเราหยุดอัลกอริทึมที่นี่

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

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

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

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 สำหรับการเรียงลำดับการแทรก

#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 โปรแกรมสำหรับการเรียงลำดับการแทรก

#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

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

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

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

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

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

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

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

เนื่องจากการเรียงลำดับแบบแทรกจะวนซ้ำแต่ละองค์ประกอบพร้อมกัน จึงต้องใช้การเรียงลำดับ 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)

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

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

สรุป

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