Insertion Sort [Tugas Besar Alpro]

Insertion Sort (Metode Penyisipan) [TUGAS BESAR ALPRO]

14102020 HANA NATASHA

14102063 GUSVIAN AZIZ

14102067 LAURA NOVITA SARAH

14102077 MUHAMMAD RAVI SOFYAN

Disini kita akan mempelajarati tentang sorting. Apa itu SORTING ???

Sorting merupakan suatu proses untuk menyusun kembali himpunan objek yang menggunakan aturan tertentu. Sorting bisa disebut juga sebagai algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci pada tiap-tiap elemen. Ada dua macam urutan yang digunakan proses sorting :

1. Urutan naik (Ascending)

Urutan naik yaitu mengurutkan data yang mempunyai nilai terkecil sampai nilai terbesar

2. Urutan turun (Descending)
Urutan turun yaitu mengurutkan dari nilai terbesar sampai dengan nilai terkecil

Dengan adanya pengurutan data, data akan mudah untuk dicari, diperiksa dan akan mudah dibetulkan jika terjasi kesalahan. Metode-metode sorting ada 6 jenis yaitu :
- Insertion Sort (Metode penyisipan)
- Selection Sort (Metode seleksi)
- Bubble Sort (Metode gelembung)
- Shell Sort (Metode shell)
- Quick Sort (Metode quick)
- Merge Sort (Metode penggabungan)

Namun pada kali ini kami hanya menjelaskan tentang Insertion Sort (Metode penyisipan). pengertian Insertion Sort yaitu metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang paling tepat.
Ada 2 macam metode Insertion sort, yaitu :
- Setraight Insertion Sort
- Binary Insertion Sort

a. Setraight insertion sort
Ilustrasi dari langkah-langkah pengurutan dengan algoritma penyisipan langsung

b. Binary insertion sort
Yaitu metode pengurutan dengan algoritma penyisipan langsung dengan melakukan proses pembandingan yang lebih sedikit sehingga proses pengurutan lebih cepat. metode biner ini melakukan perbandingan dengan membagi dua bagian data dari posisi nol (0) sampai dengan i-1 atau yang bisa di sebut juga bagian kiri dan bagian kanan.

kelebihan dan Kekurangan insertion sort
kelebihan :
- sederhan dalam penerapannya
- jika list sudah terurut maka insertion sort akan lebih cepat di bandingkan quick sort.
- loop pada insertion sort sangat cepat.
- stabil dalam proses

Kekurangan :
- banyaknya oprasi yang di lakukan untuk mencari posisi yang tepat untuk elemen larik
- untuk larik yang jumlahnya besar insertion sort ini tidak praktis
- membutuhkan waktu O(n2) pada data yang tidak terurut

Contoh program :

#include <iostream>
#include <conio.h>

using namespace std;

int main()
{
    int a,b,c,data[20],simpan,min,posisi;
       cout<<"masukkan hasil data= ";cin>>c;
       for(a=1;a<=c;a++)
       {
        cout<<"data "<<a<<" = ";cin>>data[a];
       }
       for(a=1;a<c;a++)
       {
        for(b=a+1;b<=c;b++)
          {
                if(data[a]>data[b])
             {
                simpan=data[a];
                data[a]=data[b];
                data[b]=simpan;
             }
          }
       }
       cout<<"hasil data = ";
       for(a=1;a<=c;a++)
        cout<<data[a]<<" ";

    getch();
    }