Algoritma Sortasi Penyisipan

Dalam tutorial ini, Anda akan mempelajari cara kerja penyisipan sort. Selain itu, Anda akan menemukan contoh kerja penyisipan sortir di C, C ++, Java dan Python.

Jenis penyisipan berfungsi sama seperti kita mengurutkan kartu di tangan kita dalam permainan kartu.

Kami berasumsi bahwa kartu pertama sudah diurutkan, lalu kami memilih kartu yang tidak diurutkan. Jika kartu yang tidak disortir lebih besar dari kartu di tangan, itu ditempatkan di kanan sebaliknya, ke kiri. Dengan cara yang sama, kartu lain yang tidak disortir diambil dan diletakkan di tempat yang tepat.

Pendekatan serupa digunakan oleh semacam penyisipan.

Jenis penyisipan adalah algoritma pengurutan yang menempatkan elemen yang tidak disortir di tempat yang sesuai di setiap iterasi.

Bagaimana Cara Kerja Insertion Sort?

Misalkan kita perlu mengurutkan array berikut.

Array awal
  1. Elemen pertama dalam larik diasumsikan diurutkan. Ambil elemen kedua dan simpan secara terpisah key.
    Bandingkan keydengan elemen pertama. Jika elemen pertama lebih besar dari key, maka kunci ditempatkan di depan elemen pertama. Jika elemen pertama lebih besar dari kunci, maka kunci ditempatkan di depan elemen pertama.
  2. Sekarang, dua elemen pertama diurutkan.
    Ambil elemen ketiga dan bandingkan dengan elemen di sebelah kiri. Menempatkannya tepat di belakang elemen yang lebih kecil darinya. Jika tidak ada elemen yang lebih kecil darinya, letakkan di awal larik. Tempatkan 1 di awal
  3. Demikian pula, tempatkan setiap elemen yang tidak disortir pada posisi yang benar. Tempatkan 4 di belakang 1 Tempatkan 3 di belakang 1 dan array diurutkan

Algoritma Sortasi Penyisipan

 insertionSort (array) tandai elemen pertama sebagai diurutkan untuk setiap elemen yang tidak disortir X 'ekstrak' elemen X untuk j X pindahkan elemen yang diurutkan ke kanan dengan 1 break loop dan masukkan X di sini akhiri insertionSort

Contoh Python, Java dan C / C ++

Python Java C ++ 
 # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)
  // Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )
 // Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )

Kompleksitas

Kompleksitas Waktu

  • Kompleksitas Kasus Terburuk: Misalkan, sebuah array dalam urutan naik, dan Anda ingin mengurutkannya dalam urutan turun. Dalam kasus ini, kompleksitas kasus terburuk terjadi. Setiap elemen harus dibandingkan dengan elemen lainnya sehingga, untuk setiap elemen ke-n, jumlah perbandingan dibuat. Jadi, jumlah total perbandingan =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Kompleksitas Kasus Terbaik: O(n)
    Ketika array sudah diurutkan, loop luar berjalan nbeberapa kali sedangkan loop dalam tidak berjalan sama sekali. Jadi, hanya ada nbeberapa perbandingan. Dengan demikian, kompleksitas bersifat linier.
  • Average Case Complexity: Ini terjadi ketika elemen-elemen array berada dalam urutan campur aduk (tidak naik atau turun).O(n2)

Kompleksitas Ruang

Kompleksitas ruang O(1)karena variabel tambahan keydigunakan.

Aplikasi Sortasi Penyisipan

Jenis penyisipan digunakan ketika:

  • array memiliki sejumlah kecil elemen
  • hanya ada beberapa elemen yang tersisa untuk disortir

Artikel yang menarik...