Sortir Penyisipan: Algoritma dengan C, C++, Java, Python contoh

Apa itu Pengurutan Penyisipan?

Insertion sort adalah salah satu algoritma pengurutan perbandingan yang digunakan untuk mengurutkan elemen dengan melakukan iterasi pada satu elemen pada satu waktu dan menempatkan elemen pada posisi yang benar.

Setiap elemen dimasukkan secara berurutan ke dalam daftar yang sudah diurutkan. Ukuran daftar yang sudah diurutkan awalnya adalah satu. Algoritme pengurutan penyisipan memastikan bahwa k elemen pertama diurutkan setelah iterasi ke-k.

Karakteristik Algoritma Insertion Sort

Algoritma untuk Insertion Sort memiliki Karakteristik penting berikut:

• Ini adalah teknik pengurutan yang stabil, sehingga tidak mengubah urutan relatif elemen yang sama.
• Ini efisien untuk kumpulan data yang lebih kecil tetapi tidak efektif untuk daftar yang lebih besar.
• Pengurutan Penyisipan bersifat adaptif, yang mengurangi jumlah langkah jika diurutkan sebagian. susunan diberikan sebagai masukan untuk membuatnya efisien.

Bagaimana cara Sisipkan Operapekerjaan?

Dalam algoritma Insertion Sort, operasi penyisipan digunakan untuk mengurutkan elemen yang tidak disortir. Ini membantu untuk memasukkan elemen baru ke dalam daftar yang sudah diurutkan.

Pseudocode operasi penyisipan:

Pertimbangkan daftar A dari N elemen.

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   

Dalam contoh di atas, elemen baru 6 akan dimasukkan ke dalam daftar yang sudah diurutkan.

Langkah 1) Dibandingkan dengan elemen bersebelahan kiri A[5], 9 > 6, kita menukar posisi 9 dan 6. Sekarang elemen 6 dipindahkan ke A[4].

Langkah 2) Sekarang, kita bandingkan A[4] dan A[3], dan kita temukan bahwa A[3] > A[4], kita tukar lagi posisi 6 dan 8.

Langkah 3) Sekarang bandingkan A[3] dan A[2], karena A[2] > A[3] menukar posisi 7 dan 6.

Langkah 4) Kita bandingkan A[1] dan A[2], dan karena A[1] < A[2], yaitu, elemen di sebelah kiri tidak lagi lebih besar. Sekarang kami menyimpulkan bahwa 6 dimasukkan dengan benar, dan kami menghentikan algoritme di sini.

Cara Kerja Pengurutan Penyisipan

Operasi penyisipan yang dibahas di atas adalah tulang punggung jenis penyisipan. Prosedur penyisipan dijalankan pada setiap elemen, dan pada akhirnya, kita mendapatkan daftar yang diurutkan.

Contoh gambar di atas menunjukkan cara kerja insertion sort dalam struktur data. Awalnya, hanya ada satu elemen di subdaftar yang diurutkan, yaitu 4. Setelah memasukkan A[1], yaitu 3, ukuran subdaftar yang diurutkan bertambah menjadi 2.

C++ Program untuk Penyisipan Penyortiran

#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;
}

Keluaran:

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

Kode C untuk Pengurutan Penyisipan

#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;
}

Keluaran:

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

Python Program untuk Penyisipan Penyortiran

#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=" ")

Keluaran:

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

Properti Pengurutan Penyisipan

Berikut adalah properti penting dari Insertion Sort:

• On line: Pengurutan penyisipan dapat mengurutkan elemen saat diterima. Artinya, jika kita sudah mengurutkan daftar elemen dan menambahkan beberapa elemen lagi ke daftar, maka kita tidak perlu menjalankan seluruh prosedur pengurutan lagi. Sebaliknya, kita hanya perlu melakukan iterasi pada elemen yang baru ditambahkan.
• Di tempat: Kompleksitas ruang dari algoritma insertion sort bersifat konstan dan tidak memerlukan ruang tambahan. Algoritma ini mengurutkan elemen pada tempatnya.
• Stabil: Dalam jenis penyisipan, kita tidak menukar elemen jika nilainya sama. Misalnya, dua elemen, x, dan y, adalah sama, dan x muncul sebelum y dalam daftar yang tidak diurutkan, maka dalam daftar yang diurutkan, x akan muncul sebelum y. Ini membuat penyisipan menjadi stabil.
• Adaptif: A algoritma penyortiran bersifat adaptif jika memerlukan waktu lebih sedikit jika elemen masukan atau subkumpulan elemen sudah diurutkan. Seperti yang telah kita bahas di atas, waktu berjalan terbaik dari insertion sort adalah O(N), dan waktu berjalan terburuk adalah O(N^2). Insertion sort merupakan salah satu algoritma pengurutan adaptif.

Kompleksitas Penyisipan Sortir

Kompleksitas Ruang

Pengurutan penyisipan tidak memerlukan ruang tambahan untuk mengurutkan elemen, kompleksitas ruang bersifat konstan, yaitu O(1).

Kompleksitas Waktu

Karena insertion sort mengulang setiap elemen secara bersamaan, maka diperlukan N-1 kali proses untuk mengurutkan N elemen. Untuk setiap kali proses, proses ini dapat melakukan nol pertukaran jika elemen-elemennya sudah diurutkan, atau melakukan pertukaran jika elemen-elemennya disusun dalam urutan menurun.

• Untuk pass 1, swap minimum yang diperlukan adalah nol, dan swap maksimum yang diperlukan adalah 1.
• Untuk pass 2, swap minimum yang diperlukan adalah nol, dan swap maksimum yang diperlukan adalah 2.
• Untuk pass N, swap minimum yang diperlukan adalah nol, dan swap maksimum yang diperlukan adalah N.
• Pertukaran minimum adalah nol, jadi kompleksitas waktu terbaik adalah O(N) untuk mengulangi N lintasan.
• Jumlah swap maksimum adalah (1+2+3+4+..+N) yaitu N(N+1)/2, kompleksitas waktu terburuk adalah O(N^2).

Berikut ini adalah kompleksitas waktu penting dari insertion sort:

• Kompleksitas Kasus Terburuk: O(n2): Mengurutkan array dalam urutan menurun saat array dalam urutan menaik adalah skenario terburuk.
• Kompleksitas Kasus Terbaik: O(n): Kompleksitas Kasus Terbaik terjadi saat array sudah diurutkan, loop luar berjalan sebanyak n kali sedangkan loop dalam tidak berjalan sama sekali. Hanya ada n kali perbandingan. Jadi, dalam kasus ini, kompleksitas bersifat linier.
• Kompleksitas Kasus Rata-rata: O(n2): Ini terjadi ketika elemen-elemen array muncul dalam urutan campur aduk, yaitu tidak menaik atau menurun.

Kesimpulan

• Insertion sort merupakan metode algoritma pengurutan yang didasarkan pada perbandingan.
• Ini adalah teknik pengurutan yang stabil, sehingga tidak mengubah urutan relatif elemen yang sama.
• Pada setiap elemen, operasi penyisipan digunakan untuk menyisipkan elemen ke dalam subdaftar yang diurutkan.
• Pengurutan penyisipan adalah algoritma pengurutan di tempat.
• Kompleksitas waktu penyisipan sort yang terburuk dan rata-rata adalah kuadratik, yaitu O(N^2).
• Pengurutan penyisipan tidak memerlukan ruang tambahan apa pun.