Algoritma Pengurutan Sisipan dengan C, C++, Java, Python contoh

Apa itu Pengurutan Penyisipan?

Insertion Sort adalah salah satu algoritma pengurutan perbandingan yang digunakan untuk mengurutkan elemen dengan cara mengulangi proses pada satu elemen dalam satu waktu dan menempatkan elemen tersebut pada posisi yang benar di dalam wilayah yang sudah terurut.

Setiap elemen dimasukkan secara berurutan ke dalam daftar yang sudah diurutkan. Ukuran daftar yang sudah diurutkan pada awalnya adalah satu. Algoritma Insertion Sort memastikan bahwa k elemen pertama diurutkan setelah iterasi ke-k dari loop luar.

Karena Insertion Sort membangun hasilnya secara bertahap, algoritma ini intuitif untuk diajarkan, mudah untuk di-debug, dan merupakan dasar yang kuat untuk input yang sangat kecil di mana algoritma yang lebih kompleks akan menambah beban tanpa keuntungan yang terukur.

Karakteristik Algoritma Insertion Sort

Algoritma Insertion Sort memiliki karakteristik penting berikut yang menjelaskan perilakunya pada beban kerja nyata:

• Ini adalah teknik pengurutan yang stabil, sehingga tidak mengubah urutan relatif elemen yang sama.
• Metode ini efisien untuk kumpulan data yang lebih kecil tetapi tidak efektif untuk daftar yang lebih besar di mana pertumbuhan kuadratik mendominasi.
• Insertion Sort bersifat adaptif, yang mengurangi jumlah langkah total jika input sebagian sudah terurut. susunan diberikan sebagai input agar efisien karena akses acak memungkinkan pergeseran waktu konstan selama loop dalam.
• Ini adalah algoritma in-place, sehingga tidak memerlukan penyimpanan tambahan yang sebanding dengan ukuran input.

Dengan mempertimbangkan karakteristik tersebut, bagian selanjutnya menjelaskan operasi penyisipan inti yang mendukung setiap tahapan algoritma.

Bagaimana cara Sisipkan Operapekerjaan?

Dalam algoritma Insertion Sort, operasi insert digunakan untuk mengurutkan elemen yang belum terurut. Operasi ini membantu memasukkan elemen baru ke dalam daftar yang sudah terurut sambil mempertahankan urutan yang ada pada bagian yang sudah terurut.

Pseudokode operasi penyisipan:

Pertimbangkan daftar A dari N elemen.

// 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

Pada contoh di atas, elemen baru 6 dimasukkan ke dalam daftar yang sudah diurutkan. Langkah-langkah berikut ini trace. lingkaran dalam saat elemen baru bermigrasi ke kiri menuju posisi yang benar.

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 menemukan bahwa A[3] > A[4], jadi kita kembali menukar posisi 6 dan 8.

Langkah 3) Sekarang bandingkan A[3] dan A[2]. Karena A[2] > A[3], kita tukar posisi 7 dan 6.

Langkah 4) Kita bandingkan A[1] dan A[2]. Karena A[1] < A[2], elemen yang bersebelahan di sebelah kiri tidak lagi lebih besar. Kita simpulkan bahwa 6 dimasukkan dengan benar, dan kita hentikan loop dalam di sini.

Cara Kerja Pengurutan Penyisipan

Operasi penyisipan yang dibahas di atas adalah tulang punggung dari Insertion Sort. Prosedur penyisipan dieksekusi pada setiap elemen, dan pada akhirnya, kita mendapatkan daftar yang sudah diurutkan karena wilayah yang diurutkan bertambah satu elemen pada setiap proses luar.

Gambar di atas menunjukkan cara kerja Insertion Sort dalam sebuah struktur data. Awalnya, hanya ada satu elemen dalam sublist yang diurutkan, yaitu 4. Setelah memasukkan A[1], yaitu 3, ukuran sublist yang diurutkan bertambah menjadi 2, dan algoritma melanjutkan pola ini sampai setiap elemen telah ditempatkan.

Dengan alur konseptual yang sudah terbentuk, bagian-bagian berikut menunjukkan implementasi konkret dalam C++, C, dan Python sehingga Anda dapat membandingkan struktur perulangan di berbagai bahasa.

C++ Program untuk Penyisipan Penyortiran

The C++ Implementasi di bawah ini menggunakan dua loop bersarang: loop luar memilih elemen yang belum diurutkan berikutnya, dan loop dalam menggesernya ke kiri hingga posisi yang benar ditemukan.

#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

C Code untuk Insertion Sort

Logika yang sama berlaku langsung untuk C. Standarnya printf Panggilan tersebut mengganti output aliran, tetapi pola pertukaran di dalam loop dalam identik dengan C++ versi.

#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

Python mendukung pertukaran tupleping dalam satu ekspresi, sehingga loop bagian dalam lebih ringkas daripada C dan C++ rekanan sambil mempertahankan perilaku algoritmik yang sama.

#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 yang membantu Anda memutuskan kapan algoritma ini tepat digunakan:

• On line: Insertion Sort dapat mengurutkan elemen saat menerimanya. Jika kita telah mengurutkan daftar elemen dan menambahkan lebih banyak elemen ke daftar tersebut, maka kita tidak perlu menjalankan seluruh prosedur pengurutan lagi. Sebaliknya, kita hanya melakukan iterasi pada elemen yang baru ditambahkan.
• Di tempat: Kompleksitas ruang dari algoritma Insertion Sort adalah konstan dan tidak memerlukan ruang tambahan. Algoritma ini mengurutkan elemen di tempatnya.
• Stabil: Dalam Insertion Sort, kita tidak menukar elemen jika nilainya sama. Misalnya, jika dua elemen, x dan y, sama dan x muncul sebelum y dalam daftar yang belum diurutkan, maka dalam daftar yang sudah diurutkan, x akan tetap muncul sebelum y. Hal ini membuat Insertion Sort stabil.
• Adaptif: A algoritma penyortiran Algoritma pengurutan dikatakan adaptif jika membutuhkan waktu lebih singkat ketika elemen input atau sebagian elemen sudah terurut. Seperti yang telah kita bahas di atas, waktu eksekusi terbaik dari Insertion Sort adalah O(N), dan waktu eksekusi terburuknya adalah O(N^2). Insertion Sort adalah salah satu algoritma pengurutan adaptif.

Kompleksitas Penyisipan Sortir

Pembahasan kompleksitas di bawah ini mencakup penggunaan memori dan waktu eksekusi sehingga Anda dapat membandingkan Insertion Sort dengan alternatif lain seperti... Bubble Urutkan ke Sortir Cepat.

Kompleksitas Ruang

Insertion Sort tidak memerlukan ruang tambahan untuk mengurutkan elemen. Kompleksitas ruangnya konstan, yaitu O(1), karena hanya beberapa variabel sementara yang digunakan terlepas dari ukuran input.

Kompleksitas Waktu

Karena Insertion Sort melakukan iterasi satu elemen pada satu waktu, algoritma ini membutuhkan N-1 putaran untuk mengurutkan N elemen. Pada setiap putaran, algoritma mungkin tidak melakukan pertukaran sama sekali jika elemen-elemen sudah terurut, atau mungkin membutuhkan banyak pertukaran jika elemen-elemen tersusun 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 pertukaran maksimum adalah (1+2+3+4+…+N) yaitu, N(N+1)/2, sehingga kompleksitas waktu terburuknya adalah O(N^2).

Berikut adalah kompleksitas waktu penting dari Insertion Sort:

• Kompleksitas Kasus TerburukO(n^2): Mengurutkan array dalam urutan menurun padahal seharusnya dalam urutan menaik adalah skenario terburuk.
• Kompleksitas Kasus Terbaik: O(n): Kasus terbaik terjadi ketika array sudah diurutkan; loop luar berjalan n kali, sedangkan loop dalam tidak berjalan sama sekali. Hanya ada n perbandingan, sehingga kompleksitasnya linier.
• Kompleksitas Kasus Rata-rata: O(n^2): Ini terjadi ketika elemen-elemen dalam array muncul dalam urutan acak yang tidak menaik maupun menurun.

Pertanyaan Umum Demo Slot