Insertion Sort in Java

Ngurutake array minangka salah sawijining operasi sing paling umum sing kudu dingerteni para pamula Jawa. Sanajan array ora mesthi cara sing paling trep kanggo ngatur data lan iki umume ditrapake kanggo nomer cilik, konsep ing mburi ngurutake array nduweni akeh aplikasi ing piranti lunak lan ilmu data sing rumit. Ing kirim iki, kita bakal nliti kanthi luwih rinci babagan jinis selipan. Kita kalebu sawetara conto lan masalah latihan kanggo mbantu sampeyan ngerti konsep iki.

Apa Insertion Sort?

Sejatine, insertion sort minangka algoritma sing digunakake pangembang kanggo ngatur senar saka nomer cilik. Iki mbagi kabeh nilai dadi rong tumpukan - sing diurutake lan sing ora diurutake. Siji-siji, nomer ing tumpukan "ora diurut" dipilih lan dilebokake ing urutan sing bener. Ayo goleki kanthi luwih rinci babagan input lan output saka insertion sort:

• Input: array A kanthi unsur numerik sing ora diurutake: A[0,1, n, n-2...].
• Output: larik sing ngemot nomer sing padha nanging diurutake kanthi lengkap. Iki biasane diarani B: B[0]B[1]...B[n-1].

Ana sawetara cara kanggo nggunakake ngurutake sisipan - iki sing paling populer:

• Ngurutake angka (urutan mundhak): [1, 2, 3, 4, 5]
• Ngurutake angka (urutan mudhun): [5, 4, 3, 2, 1]
• Urutan abjad: [a, b, c, d]

Cathetan: yen sampeyan duwe array kosong utawa singleton, iki dianggep diurutake kanthi standar.

Pangertosan Teori Insertion Sort

Sadurunge njelajah kode ing mburi ngurutake sisipan, ayo ngrusak algoritma nggunakake basa non-teknis. Amarga kita bakal nuduhake kode kanggo ngurutake ing urutan munggah, iku ndadekake pangertèn kanggo nerangake algoritma langkah dening langkah ing kirim iki. Langkah 1. Iterating antarane arr[1]lan arr[n]endi nnilai numerik biasane kurang saka 10. Langkah 2. Mbandhingaké unsur sing milih (dikenal minangka key) kanggo nomer sadurunge ing urutan nggunakake sort()cara. Langkah 3. Yen kabeh unsur luwih cilik tinimbang peneruse, baleni perbandingan nganti sampeyan nemokake nilai sing luwih gedhe. Langkah 4. Ganti nilai sing luwih gedhe siji posisi ngluwihi sing luwih cilik kanggo nggawe urutan sing diurutake. Langkah 5. Baleni proses nganti sampeyan entuk senar karakter sing diurutake

Ngurutake array primitif

Amarga algoritma kasebut minangka salah sawijining operasi Java sing paling gampang, sanajan pamula sing lengkap ora duwe masalah kanggo ngetrapake. Iki minangka pandhuan langkah-langkah kanggo ngurutake array

1. Wara-wara array kanggo ngurutake

Kanggo miwiti, ayo nggawe senar nilai sing bakal ditampilake nggunakake Java. Kanggo nggunakake insertion sort, sampeyan kudu nggawe array. Kanggo iku, gunakakeint[]

int[] arrayA = {10, 14, 20, 30};

2. Gunakake sort_arr kanggo ngleksanakake algoritma

Cara sort_arr minangka salah sawijining cara sing paling umum kanggo ngetrapake urutan sisipan. Ing laku, katon kaya iki:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Nggawe daur ulang lan iterator

Kanthi nggunakake daur ulang ing algoritma ngurutake sisipan, pangembang ora kudu mbaleni logika kanggo saben unsur. Sanajan nggawe puteran katon rumit, cukup prasaja - iki contone:

for(int i=0; i< sort_arr.length; ++i){

Saiki sampeyan duwe daur ulang sing berfungsi, wektune nggawe iterator sing bakal ngurutake kabeh unsur ing urutan sing dikarepake. Wiwit saiki, kita bakal nyebut iterator minangka " j".

        int j = i;

4. Nggawe "while loop"

Nalika nerangake ngurutake sisipan, daur ulang "nalika" penting kanggo array sing diurutake anyar. Kanggo nyiyapake urutan sisipan munggah-munggah, pangembang kudu netepi rong syarat:

• Nilai sing diwenehake marang j kudu luwih saka 0
• Nilai sing ditugasake j-1kudu luwih gedhe tinimbang jindeks

Sanalika kondisi loro ing loop while bener, nilai kunci array bakal padha karo indeks j.

5. Ngurutake larik

Sawise sampeyan nyiyapake loop while, nilai jlan j-1bakal diganti nganti siji utawa loro kondisi ing loop while gagal. Kajaba iku, ngurutake bakal diulang kanggo saben nilai ing daur ulang kanggo nganti kahanan kanggo daur ulang uga gagal. Mangkene carane proses ngurutake sisipan ing praktik:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

Ngurutake ArrayList

Sanajan ngerti matématika ing mburi ngurutake sisipan iku penting, nalika nerangake pangembangan piranti lunak nyata, sampeyan bakal ngurutake ArrayLists luwih akeh tinimbang urutan ing array primitif. Mangkene pandhuan langkah-langkah kanggo ngurutake ArrayList:

1. Nggawe kelas anyar Elementkanggo item sing dadi koleksi.

   
   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }
   

2. Ing koleksi, ana compareTo()cara - kita bakal nggunakake iki kanggo mbandhingake id saka rong unsur.

   
       public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }
   

3. Gunakake algoritma lan nggawe sawetara puteran kanggo ngurutake obyek ArrayListtinimbang mbandhingake.

   
   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }
   

4. ArrayListSampeyan uga bisa nambah unsur liyane , kaya sing ditampilake ing ngisor iki:

   
   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);
   

5. Saiki wektune kanggo ngurutake:

   
   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array 
   list.forEach(e -> System.out.print(e.getId() + ", "));
   

6. Saiki ayo mbandhingake input lan output kanggo mesthekake yen ora ana kesalahan. Iki minangka perbandingan string sing digunakake minangka conto.

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
   

Masalah Laku Urut Selipan

Saiki sampeyan wis ngerti algoritma pangurutan iki, wektune kanggo nyoba katrampilan teoretis lan praktis. Kuis teori #1 Sampeyan diwenehi array [1, 4, 6, 8] lan nambah unsur anyar n = 7. Apa nomer mbandhingake sampeyan kudu nggawe kanggo njaluk urutan nomer sing diurutake? Nuduhake nilai pungkasan indeks n ing larik. Kuis Teori #2 Ing wawancara kerja, pimpinan tim njaluk sampeyan mbuktekake manawa sisipan ngurutake minangka cara sing ora efisien. Diwenehi string angka [0, 3, 6, 8, 9], apa urutan urutan input sampeyan kanggo maksimalake wektu mlaku sing dibutuhake kanggo ngurutake? Masalah latihan Urutake larik [0, 1, 4, 5, 2, 3, 7, 9, 8] ing urutan munggah nggunakake urutan sisipan kanggo Jawa.

Kesimpulan

Tantangan paling gedhe kanggo nangkep urutan sisipan yaiku ngerteni cara proses kasebut. Sawise sampeyan ngerti, ngowahi cithakan dadi kode minangka kue. Anggere sampeyan latihan lan bali maneh masalah latihan sing relevan saka wektu, sampeyan bakal kanthi cepet nambah kacepetan ngurutake sisipan.