Algoritma Susun Sisipan

Dalam tutorial ini, anda akan belajar bagaimana penyisipan berfungsi. Anda juga akan dapati contoh penyisipan yang berfungsi di C, C ++, Java dan Python.

Jenis penyisipan berfungsi sama seperti kita menyusun kad di tangan kita dalam permainan kad.

Kami menganggap bahawa kad pertama sudah disusun, kami memilih kad yang tidak disusun. Sekiranya kad yang tidak disusun lebih besar daripada kad di tangan, kad itu diletakkan di sebelah kanan sebaliknya, di sebelah kiri. Dengan cara yang sama, kad lain yang tidak disusun diambil dan diletakkan di tempat yang betul.

Pendekatan serupa digunakan dengan penyisipan.

Jenis penyisipan adalah algoritma penyortiran yang meletakkan elemen yang tidak disusun di tempat yang sesuai dalam setiap lelaran.

Bagaimana Penyisipan Penyisipan Berfungsi?

Katakan kita perlu menyusun susunan berikut.

Susunan awal
  1. Elemen pertama dalam susunan dianggap disusun. Ambil elemen kedua dan simpan secara berasingan di key.
    Bandingkan keydengan elemen pertama. Sekiranya elemen pertama lebih besar daripada key, maka kunci diletakkan di hadapan elemen pertama. Sekiranya elemen pertama lebih besar daripada kunci, maka kunci diletakkan di hadapan elemen pertama.
  2. Sekarang, dua elemen pertama disusun.
    Ambil elemen ketiga dan bandingkan dengan elemen di sebelah kiri. Letakkannya tepat di belakang elemen yang lebih kecil darinya. Sekiranya tidak ada unsur yang lebih kecil darinya, maka letakkan di awal array. Letakkan 1 pada awal
  3. Begitu juga, letakkan setiap elemen yang tidak disusun pada kedudukannya yang betul. Tempat 4 di belakang 1 Tempat 3 di belakang 1 dan susunan disusun

Algoritma Susun Sisipan

 insertionSort (array) mark elemen pertama sebagai disusun untuk setiap elemen yang tidak disusun X 'ekstrak' elemen X untuk j X gerakkan elemen yang disusun ke kanan dengan 1 putaran gelung dan masukkan X di sini akhir penyisipan

Contoh Python, Java dan C / C ++

Python Java C 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); )

Kerumitan

Kerumitan Masa

  • Kerumitan Kes Terburuk: Andaikan, susunan berada dalam urutan menaik, dan anda mahu menyusunnya mengikut urutan menurun. Dalam kes ini, kerumitan kes terburuk berlaku. Setiap elemen harus dibandingkan dengan unsur-unsur yang lain sehingga, untuk setiap elemen ke-9, jumlah perbandingan dibuat. Oleh itu, jumlah perbandingan =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Kerumitan Kes Terbaik: O(n)
    Apabila susunan sudah disusun, gelung luar berjalan nberkali-kali sedangkan gelung dalam tidak berjalan sama sekali. Jadi, hanya ada njumlah perbandingan. Oleh itu, kerumitan adalah linear.
  • Kerumitan Kes Rata-rata: Ia berlaku apabila unsur-unsur array berada dalam urutan yang tidak rata (tidak menaik atau menurun).O(n2)

Kerumitan Ruang

Kerumitan ruang O(1)kerana pemboleh ubah tambahan keydigunakan.

Aplikasi Susun Sisipan

Jenis sisipan digunakan apabila:

  • susunan itu mempunyai sebilangan kecil unsur
  • hanya tinggal beberapa elemen untuk disusun

Artikel menarik...