Sunday, December 25, 2016

Bab 6. Visual C# Untuk Programer



Pencarian dan Pengurutan






6.1 Pengantar

Pencarian nomor telepon, mencari sebuah situs internet melalui mesin pencari, dan memeriksa definisi sebuah kata di dalam kamus semuanya melibatkan pencarian terhadap banyak data. Dua bagian ke depan mendiskusikan dua algoritma pencarian yang umum dijumpai, yaitu satu algoritma yang mudah diprogram tetapi tidak efisien dan satu algoritma lain yang relatif efisien tetapi lebih kompleks dan sulit untuk diprogram.

6.2 Pencarian Linier
Algoritma pencarian linier melakukan pencarian terhadap setiap elemen di dalam sebuah array secara sekuensial. Jika kunci pencarian tidak cocok dengan salah satu elemen di dalam array sampai akhir array diraih, maka algoritma akan memberitahukan pengguna bahwa kunci pencarian tidak ada. Jika kunci pencarian ada di dalam array, algoritma akan menguji setiap elemen sampai ia menemukan yang cocok dengan kunci pencarian dan menghasilkan nilai balik berupa indeks dari elemen tersebut.

Sebagai contoh, perhatikan sebuah array yang memuat nilai-nilai berikut:

34 56 2 10 77 51 93 30 5 52

dan sebuah program yang melakukan pencarian untuk menemukan 51. Dengan menggunakan algoritma pencarian, program pertama-tama memeriksa apakah 34 cocok dengan kunci pencarian. Jika tidak, maka algoritma akan memeriksa apakah 56 cocok dengan kunci pencarian. Program melanjutkan proses yang sama untuk menguji 2, kemudian 10, dan kemudian 77. Ketika program menguji 51, yang cocok dengan kunci pencarian, program menghasilkan indeks 5, yang merupakan lokasi dari 51 di dalam array. Jika, setelah pemeriksaan atas setiap elemen array, program menentukan bahwa kunci pencarian tidak cocok dengan sembarang elemen di dalam array, maka ia akan menghasilkan sebuah nilai sentinel (misalnya, -1).

Gambar 6.1 mendeklarasikan kelas LinierArray. Kelas ini mempunyai satu variabel instans private, yaitu sebuah array bernama data yang memuat beberapa int dan sebuah objek static Random untuk mengisi array dengan beberapa int yang dibangkitkan secara acak. Ketika sebuah objek dari kelas LinierArray diinstansiasi, konstruktor (baris 12-19) menciptakan dan menginisialisasi array data dengan beberapa int acak dalam rentang 10-99. Jika terdapat nilai-nilai duplikat di dalam array, maka pencarian linier akan menghasilkan indeks dari elemen pertama di dalam array yang cocok dengan kunci pencarian.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Gambar 6.1: LinearArray.cs
// Kelas yang memuat sebuah array dengan integer-integer acak dan sebuah metode
// yang melakukan pencarian pada array secara sekuensial.
using System;

public class LinearArray
{
    private int[] data; // array dengan int-int
    private static Random pembangkit = new Random();

    // menciptakan array dengan ukuran tertentu dan mengisinya dengan int-int acak
    public LinearArray( int ukuran )
    {
        data = new int[ ukuran ]; // menciptakan ruang untuk array

        // mengisi array dengan int-int acak dalam rentang 10-99
        for ( int i = 0; i < ukuran; i++ )
            data[ i ] = pembangkit.Next( 10, 100 );
    } // akhir konstruktor LinearArray

// melakukan pencarian linier pada data
public int PencarianLinier( int kunciPencarian )
{
    // loop menjelajah array secara sekuensial
    for ( int indeks = 0; indeks < data.Length; indeks++ )
        if ( data[ indeks ] == kunciPencarian )
            return indeks; // menghasilkan indeks dari integer

    return -1; // integer tidak ditemukan
} // akhir metode PencarianLinier

    // metode untuk menampilkan nilai-nilai di dalam array
    public override string ToString()
    {
        string sementara = string.Empty;

        // beriterasi menjelajah array
        foreach ( int elemen in data )
            sementara += elemen + " ";

        sementara += "\n"; // karakter garis-baru
        return sementara;
    } // akhir metode ToString
 } // akhir kelas LinearArray

Baris 23-31 melakukan pencarian linier. Kunci pencarian dilewatkan kepada parameter kunciPencarian. Baris 25-27 menjelajah elemen-elemen di dalam array. Baris 26 membandingkan setiap elemen di dalam array dengan kunciPencarian. Jika sebuah elemen cocok dengan kunciPencarian, maka baris 27 akan menghasilkan indeks dari elemen tersebut. Jika loop berhenti tanpa menemukan sebuah nilai yang cocok dengan kunciPencarian, maka baris 29 akan menghasilkan -1. Baris 33-43 mendeklarasikan metode ToString, yang menggunakan metode static ToString untuk menghasilkan representasi string dari array.

Gambar 6.2 menciptakan sebuah objek LinierArray yang memuat sebuah array 10 int (baris 13) dan memampukan pengguna untuk melakukan pencarian pada array itu. Baris 17-18 meminta pengguna untuk memberikan kunciPencarian dan menyimpannya di dalam cariInt. Baris 21-37 beriterasi sampai pengguna memasukkan nilai sentinel -1. Array memuat beberapa int dari 10-99 (baris 18 pada Gambar 6.1). Baris 24 memanggil metode PencarianLinier untuk menentukan apakah cariInt ada di dalam array atau tidak. Jika tidak, PencarianLinier akan menghasilkan -1 dan program akan memberitahu pengguna (baris 31-32). Jika cariInt ada di dalam array, maka PencarianLinier akan menghasilkan posisi dari elemen, yang ditampilkan program pada baris 27-29. Baris 35-36 membaca masukan berikutnya dari pengguna.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Gambar 6.2: UjiPencarianLinier.cs
// Pencarian sekuensial pada array.
using System;

public class UjiPencarianLinier
{
    public static void Main( string[] args )
    {
        int cariInt; // kunci pencarian
        int posisi; // lokasi dari kunci pencarian pada array

        // menciptakan array dan menampilkannya
        LinearArray pencarianArray = new LinearArray( 10 );
        Console.WriteLine( pencarianArray ); // menampilkan array

        // membaca int pertama dari pengguna
        Console.Write( "Silahkan masukkan sebuah nilai integer (-1 untuk keluar): ");
        cariInt = Convert.ToInt32( Console.ReadLine() );

        // secara berulang memasukkan integer; -1 menghentikan aplikasi
        while ( cariInt != -1 )
        {
            // melakukan pencarian linier
            posisi = pencarianArray.PencarianLinier( cariInt );

            if ( posisi != -1 ) // integer tidak ditemukan
                Console.WriteLine(
                    "Integer {0} ditemukan pada posisi {1}.\n",
                    cariInt, posisi );
            else // integer ditemukan
                Console.WriteLine( "Integer {0} tidak ditemukan.\n",
                    cariInt );

            // membaca int berikutnya dari pengguna
            Console.Write( "Silahkan masukkan sebuah nilai integer (-1 untuk keluar): " );
            cariInt = Convert.ToInt32( Console.ReadLine() );
        } // akhir while
    } // akhir Main
} // akhir kelas UjiPencarianLinier

37 98 98 25 89 73 59 39 43 75

Silahkan masukkan sebuah nilai integer (-1 untuk keluar): 78
Integer 78 tidak ditemukan.

Silahkan masukkan sebuah nilai integer (-1 untuk keluar): 64
Integer 64 tidak ditemukan.

Silahkan masukkan sebuah nilai integer (-1 untuk keluar): 65
Integer 65 tidak ditemukan.

Silahkan masukkan sebuah nilai integer (-1 untuk keluar): -1



6.3 Pencarian Biner
Algoritma pencarian biner lebih efisien daripada pencarian linier, tetapi ia mensyaratkan bahwa array harus telah terurut. Iterasi pertama pada algoritma ini menguji elemen tengah di dalam array. Jika elemen ini cocok dengan kunci pencarian, maka algoritma berhenti. Diasumsikan bahwa array telah diurutkan dengan tatanan menaik, kemudian jika kunci pencarian bernilai kurang dari elemen tengah, maka kunci pencarian tidak akan cocok dengan sembarang elemen pada bagian setengah kedua dari array dan algoritma berlanjut melakukan pencarian hanya terhadap setengah bagian pertama dari array (yaitu, elemen pertama sampai elemen sebelum elemen tengah). Jika kunci pencarian bernilai lebih besar daripada elemen tengah, maka kunci pencarian itu tidak akan cocok dengan sembarang elemen di dalam setengah bagian pertama dari array dan algoritma berlanjut melakukan pencarian terhadap setengah bagian kedua dari array (yaitu, elemen sesudah elemen tengah sampai elemen terakhir). Setiap iterasi menguji nilai tengah pada bagian array yang tersisa. Algoritma berhenti karena telah menemukan elemen yang cocok dengan kunci pencarian atau karena subarray telah menjadi nol.

Sebagai contoh, perhatikan array 15-elemen terurut berikut

2 3 5 10 27 30 34 51 56 65 77 81 82 93 99

dan dengan kunci pencarian 65. Sebuah program yang mengimplementasikan algoritma pencarian biner pertama-tama akan memeriksa apakah 51 adalah kunci pencarian (karena 51 merupakan elemen tengah array). Kunci pencarian (65) lebih besar dari 51, jadi 51 diabaikan bersama dengan setengah bagian pertama dari array (semua elemen yang lebih kecil dari 51), yang menghasilkan

56 65 77 81 82 93 99

Selanjutnya, algoritma memeriksa apakah 81 (elemen tengah dari subarray yang tersisa) cocok dengan kunci pencarian atau tidak. Kunci pencarian (65) lebih kecil dari 81, jadi 81 akan diabaikan bersama dengan semua elemen yang lebih besari dari 81. Setelah dua kali pengujian, algoritma telah menyempitkan jumlah angka yang akan diperiksa menjadi hanya tiga (56, 65, dan 77). Program kemudian memeriksa 65 (yang cocok dengan kunci pencarian) dan menghasilkan indeks dari elemen array yang memuat 65. Algoritma ini hanya memerlukan tiga perbandingan dalam menentukan apakah kunci pencarian cocok dengan sebuah elemen array. Penggunaan algoritma pencarian linier akan memerlukan 10 perbandingan.

Implementasi Pencarian Biner
Gambar 6.3 mendeklarasikan kelas BinerArray. Kelas ini sama dengan LinierArray, dimana ia memiliki dua variabel instans private, sebuah konstruktor, sebuah metode pencarian (PencarianBiner), sebuah metode ElemenSisa, dan sebuah metode ToString. Baris 12-21 mendeklarasikan konstruktor. Setelah array diinisialisasi dengan beberapa int acak dari 10-99 (baris 17-18), baris 20 memanggil metode Array.Sort pada array data. Metode Sort merupakan sebuah metode static dari kelas Array yang mengurutkan elemen-elemen sebuah array dalam tatanan menaik secara default; versi teroverload dari metode ini memampukan Anda untuk mengubah tatanan pengurutan. Ingat bahwa algoritma pencarian biner hanya akan bekerja pada sebuah array terurut.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// Gambar 6.3: BinerArray.cs
// Kelas yang memuat sebuah array dengan int-int acak dan sebuah metode
// yang menggunakan pencarian biner untuk menemukan sebuah integer.
using System;

public class BinerArray
{
    private int[] data; // array dengan int-int
    private static Random pembangkit = new Random();

    // menciptakan array dengan ukuran tertentu dan mengisinya dengan int-int acak
    public BinerArray( int ukuran )
    {
        data = new int[ ukuran ]; // menciptakan ruang untuk array

        // mengisi array dengan int-int acak dalam rentang 10-99
        for ( int i = 0; i < ukuran; i++ )
            data[ i ] = pembangkit.Next( 10, 100 );

        Array.Sort(data);
    } // akhir konstruktor BinaryArray

// melakukan pencarian biner pada data
public int PencarianBiner( int cariElemen )
{
    int rendah = 0; // akhir bawah dari area pencarian
    int tinggi = data.Length - 1; // akhir atas area pencurian
    int tengah = ( rendah + tinggi + 1 ) / 2; // elemen tengah
    int lokasi = -1; // menghasilkan nilai; -1 jika tidak ditemukan

    do // menjelajah untuk mencari elemen
    {
        // menampilkan elemen-elemen sisa pada array
        Console.Write( ElemenSisa( rendah, tinggi ) );

        // menampilkan spasi-spasi untuk penyejajaran
        for ( int i = 0; i < tengah; i++ )
            Console.Write( " " );

        Console.WriteLine( " * " ); // indikasi elemen tengah

        // jika elemen ditemukan di tengah
        if ( cariElemen == data[ tengah ] )
            lokasi = tengah; // lokasi adalah tengah

        // elemen tengah terlalu tinggi
        else if ( cariElemen < data[ tengah ] )
            tinggi = tengah - 1; // eleminasi setengah potongan atas
        else // elemen tengah terlalu rendah
            rendah = tengah + 1; // eleminasi setengah potongan bawah

        tengah = ( rendah + tinggi + 1 ) / 2; // menghitung ulang tengah
    } while ( ( rendah <= tinggi ) && ( lokasi == -1 ) );

    return lokasi; // menhasilkan lokasi dari kunci pencarian
} // akhir metode PencarianBiner

    // metode untuk menampilkan nilai-nilai tertentu pada array
    public string ElemenSisa(int rendah, int tinggi)
    {
        string temporer = string.Empty;

        // menampilkan spasi untuk penyejajaran
        for (int i = 0; i < rendah; i++)
            temporer += " ";

        // menampilkan elemen-elemen sebelah kiri array
        for ( int i = rendah; i <= tinggi; i++ )
            temporer += data[ i ] + " ";

        temporer += "\n";
        return temporer;
    } // akhir metode ElemenSisa

    // metode untuk menampilkan nilai-nilai di dalam array
    public override string ToString()
    {
        return ElemenSisa(0, data.Length - 1);
    } // akhir metode ToString
} // akhir kelas BinerArray

Baris 25-56 mendeklarasikan metode PencarianBiner. Kunci pencarian dilewatkan kepada parameter cariElemen (baris 24). Baris 26-28 menghitung indeks akhir rendah, indeks akhir tinggi, dan indeks tengah dari potongan array yang sedang dilakukan pencarian. Di awal metode, rendah bernilai 0, tinggi adalah panjang array dikurangi 1, dan tengah adalah rerata dari kedua nilai tersebut. Baris 29 menginisialisasi lokasi dari elemen menjadi -1, nilai yang akan dijadikan nilai balik jika elemen tidak ditemukan. Baris 31-53 menjelajah sampai rendah lebih besar daripada tinggi (ini terjadi ketika elemen tidak ditemukan) atau lokasi tidak sama dengan -1 (mengindikasikan bahwa kunci pencarian ditemukan). Baris 43 menguji apakah nilai pada elemen tengah sama dengan cariElemen atau tidak. Jika ini bernilai true, maka baris 44 akan menugaskan tengah kepada lokasi. Kemudian loop berhenti dan lokasi dikembalikan kepada pemanggil. Setiap iterasi loop memeriksa sebuah nilai tunggal (baris 43) dan mengeliminasi setengah bagian array (baris 48 atau baris 50).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Gambar 6.4: UjiPencarianBiner.cs
// Menggunakan pencarian biner untuk mencari sebuah elemen pada array.
using System;

public class UjiPencarianBiner
{
    public static void Main( string[] args )
    {
        int cariInt; // kunci pencarian
        int posisi; // lokasi kunci pencarian pada array

        // menciptakan array dan menampilkannya
        BinerArray cariArray = new BinerArray(15);
        Console.WriteLine( cariArray );

        // meminta pengguna memasukkan int pertama
        Console.Write( "Silahkan masukkan sebuah nilai integer (-1 untuk keluar): " );
        cariInt = Convert.ToInt32( Console.ReadLine() );
        Console.WriteLine();

        // secara berulang membaca integer; -1 menghentikan aplikasi
        while ( cariInt != -1 )
        {
            // menggunakan pencarian biner
            posisi = cariArray.PencarianBiner(cariInt);
   
            // nilai balik -1 mengindikasikan integer tidak ditemukan
            if ( posisi == -1 )
                Console.WriteLine( "Integer {0} tidak ditemukan.\n",
                    cariInt );
            else
                Console.WriteLine(
                    "Integer {0} ditemukan pada posisi {1}.\n",
                    cariInt, posisi);

            // meminta pengguna memasukkan int berikutnya
            Console.Write("Silahkan masukkan sebuah nilai integer (-1 untuk keluar): ");
            cariInt = Convert.ToInt32( Console.ReadLine() );
            Console.WriteLine();
        } // akhir while
    } // akhir Main
} // akhir kelas UjiPencarianBiner

16 17 20 25 26 27 29 29 33 46 61 62 68 76 91

Silahkan masukkan sebuah nilai integer (-1 untuk keluar): 76

16 17 20 25 26 27 29 29 33 46 61 62 68 76 91
                      *
                        33 46 61 62 68 76 91
                                  *
                                    68 76 91
                                        *
Integer 76 ditemukan pada posisi 13.

Silahkan masukkan sebuah nilai integer (-1 untuk keluar): 20

16 17 20 25 26 27 29 29 33 46 61 62 68 76 91
                      *
16 17 20 25 26 27 29
          *
16 17 20
    *
      20
       *
Integer 20 ditemukan pada posisi 2.

Silahkan masukkan sebuah nilai integer (-1 untuk keluar): 9

16 17 20 25 26 27 29 29 33 46 61 62 68 76 91
                      *
16 17 20 25 26 27 29
          *
16 17 20
    *
16
 *
Integer 9 tidak ditemukan.

Silahkan masukkan sebuah nilai integer (-1 untuk keluar): -1

6.4 Algoritma Pengurutan
Pengurutan data (menempatkan data dalam urutan tertentu, seperti menaik atau menurun) adalah salah satu aplikasi komputer yang paling penting. Sebuah bank mengurutkan semua rekening dengan nomor akun sehingga ia dapat mempersiapkan administrasi pada tiap akhir bulan. Perusahaan telepon mengurutkan daftar pelanggannya berdasarkan nama pertama, dan seterusnya.

Satu hal penting yang perlu Anda pahami tentang pengurutan adalah bahwa hasil akhir, array terurut, akan sama tidak peduli algoritma mana yang Anda gunakan untuk mengurutkan array. Pilihan algoritma hanya mempengaruhi waktu komputasi dan penggunaan memori pada program.

6.5 Pengurutan Seleksi
Pengurutan seleksi adalah algoritma pengurutan sederhana, tetapi tidak efisien. Iterasi pertamanya menyeleksi elemen terkecil di dalam array dan menukarnya dengan elemen pertama. Iterasi kedua memilih item terkecil-kedua dan menukarnya dengan elemen kedua. Algoritma ini berlanjut sampai iterasi terakhir menyeleksi elemen terbesar-kedua dan menukarnya dengan elemen dengan indeks terbesar-kedua, yang menyisakan elemen dengan indeks terakhir. Sebagai contoh, perhatikan array

34 56 4 10 77 51 93 30 5 52

Sebuah program yang mengimplementasikan pengurutan seleksi pertama-tama menentukan elemen terkecil (4) pada array ini, yang dimuat pada indeks 2. Program menukar 4 dengan 34, yang menghasilkan

4 56 34 10 77 51 93 30 5 52

Program kemudian menentukan elemen terkecil dari elemen-elemen sisa (semua elemen kecuali 4), yaitu 5, yang dimuat pada indeks 8. Program menukar 5 dengan 56, yang menghasilkan

4 5 34 10 77 51 93 30 56 52

Pada iterasi ketiga, program menentukan elemen terkecil berikutnya (10) dan menukarnya dengan 34, yang menghasilkan

4 5 10 34 77 51 93 30 56 52

Proses berlanjut sampai array terurut sepenuhnya, yang memuat

4 5 10 30 34 51 52 56 77 93

Setelah iterasi pertama, elemen terkecil berada pada posisi pertama. Setelah iterasi kedua, dua elemen terkecil berada secara berurutan berada pada dua posisi pertama. Setelah iterasi ketiga, tiga elemen terkecil secara berurutan berada pada tiga posisi pertama.

Gambar 6.5 mendeklarasikan kelas PengurutanSeleksi. Kelas ini mempunyai dua variabel instans private, yaitu sebuah array bernama data yang memuat beberapa int dan sebuah objek static Random untuk membangkitkan integer-integer acak untuk mengisi array. Ketika sebuah objek dari kelas PengurutanSeleksi diinstansiasi, konstruktor (baris 12-19) menciptakan dan menginisialisasi array data dengan beberapa int acak dalam rentang 10-99.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Gambar 6.5: PengurutanSeleksi.cs
// Kelas yang menciptakan sebuah array yang diisi dengan int-int acak.
// Menyediakan sebuah metode untuk mengurutkan array dengan pengurutan seleksi.
using System;

public class PengurutanSeleksi
{
    private int[] data; // array dengan nilai-nilai
    private static Random pembangkit = new Random();

    // menciptakan sebuah array dengan ukuran tertentu dan mengisi int-int acak
    public PengurutanSeleksi( int ukuran )
    {
        data = new int[ ukuran ]; // menciptakan ruang untuk array

        // mengisi array dengan int-int acak dalam rentang 10-99
        for ( int i = 0; i < ukuran; i++ )
            data[ i ] = pembangkit.Next( 10, 100 );
    } // akhir konstruktor PengurutanSeleksi

// mengurutkan array dengan pengurutan seleksi
public void Urut()
{
    int terkecil; // indeks dari elemen terkecil
       
    // menjelajah array dengan data.Length - 1 elemen
    for ( int i = 0; i < data.Length - 1; i++ )
    {
        terkecil = i; // indeks pertama pada array sisa

        // loop untuk menemukan indeks dari elemen terkecil
        for ( int indeks = i + 1; indeks < data.Length; indeks++ )
            if ( data[ indeks ] < data[ terkecil ] )
                terkecil = indeks;

        Tukar( i, terkecil ); // menukar elemen terkecil
        TampilPass( i + 1, terkecil ); // menampilkan pass dari algoritma
    } // akhir for luar
} // akhir metode Urut

// metode helper untuk menukar nilai-nilai dari dua elemen
public void Tukar( int pertama, int kedua )
{
    int sementara = data[ pertama ]; // menyimpan pertama pada sementara
    data[pertama] = data[kedua]; // mengganti pertama dengan kedua
    data[kedua] = sementara; // menempatkan sementara pada kedua
} // akhir metode Tukar

    // menampilkan sebuah pass dari algoritma
    public void TampilPass( int pass, int indeks )
    {
        Console.Write( "setelah pass {0}: ", pass );

        // menampilkan elemen-elemen sampai item terpilih
        for ( int i = 0; i < indeks; i++ )
            Console.Write( data[ i ] + " " );

        Console.Write( data[ indeks ] + "* " ); // indikasi penukaran

        // menampilkan isi array lainnya
        for ( int i = indeks + 1; i < data.Length; i++ )
            Console.Write( data[ i ] + "  " );

        Console.Write( "\n         " ); // untuk penyejajaran

        // mengindikasikan jumlah array yang diurutkan
        for( int j = 0; j < pass; j++ )
            Console.Write( "--  " );
        Console.WriteLine( "\n" ); // melompati sebaris pada keluaran
    } // akhir metode TampilPass

    // metode untuk menampilkan nilai-nilai pada array
    public override string ToString()
    {
        string sementara = string.Empty;

        // menjelajah array
        foreach ( int elemen in data )
            sementara += elemen + "  ";

        sementara += "\n"; // karakter garis-baru
        return sementara;
    } // akhir metode ToString
} // akhir kelas PengurutanSeleksi

Baris 22-39 mendeklarasikan metode Urut. Baris 24 mendeklarasikan variabel terkecil, yang akan menyimpan indeks dari elemen terkecil pada sisa array. Baris 27-38 menjelejah sebanyak data.length – 1 kali. Baris 29 menginisialisasi indeks dari elemen terkecil menjadi item sekarang. Baris 32-34 melakukan penjelajahan atas elemen-elemen sisa di dalam array. Untuk tiap elemen ini, baris 33 akan membandingkan nilainya dengan nilai dari elemen terkecil. Jika elemen sekarang lebih kecil dari elemen terkecil, maka baris 34 akan menugaskan indeks dari elemen sekarang kepada terkecil. Ketika loop ini selesai, terkecil akan memuat indeks dari elemen terkecil pada sisa array.

Baris 10 pada Gambar 6.6 menciptakan sebuah objek PengurutanSeleksi dengan 10 elemen. Baris 13 menampilkan objek tak-terurut. Baris 14 memanggil metode urut (baris 22-39 pada Gambar 5.5), yang mengurutkan elemen-elemen menggunakan pengurutan seleksi. Kemudian baris 17-18 menampilkan objek terurut. Keluaran menggunakan garis putus-putus (baris 67-68) untuk mengindikasikan potongan array yang telah diurutukan setelah tiap iterasi dilakukan.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Gambar 6.6: UjiPengurutanSeleksi.cs
// Menguji kelas pengurutan seleksi.
using System;

public class UjiPengurutanSeleksi
{
    public static void Main( string[] args )
    {
        // menciptakan objek untuk melakukan pengurutan seleksi
        PengurutanSeleksi urutArray = new PengurutanSeleksi(10);

        Console.WriteLine( "Array tak-terurut:" );
        Console.WriteLine( urutArray ); // menampilkan array tak-terurut

        urutArray.Urut(); // mengurutkan array

        Console.WriteLine( "Array terurut:" );
        Console.WriteLine(urutArray); // menampilkan array terurut
    } // akhir Main
} // akhir kelas UjiPengurutanSeleksi

Array tak-terurut:
36  45  39  92  18  33  39  74  33  44

setelah pass 1: 18 45 39 92 36* 33  39  74  33  44
             --

setelah pass 2: 18 33 39 92 36 45* 39  74  33  44
             --  --

setelah pass 3: 18 33 33 92 36 45 39 74 39* 44
             --  --  --

setelah pass 4: 18 33 33 36 92* 45  39  74  39  44
             --  --  --  --

setelah pass 5: 18 33 33 36 39 45 92* 74  39  44
             --  --  --  --  --

setelah pass 6: 18 33 33 36 39 39 92 74 45* 44
             --  --  --  --  --  --

setelah pass 7: 18 33 33 36 39 39 44 74 45 92*
             --  --  --  --  --  --  --

setelah pass 8: 18 33 33 36 39 39 44 45 74* 92
             --  --  --  --  --  --  --  --

setelah pass 9: 18 33 33 36 39 39 44 45 74* 92
             --  --  --  --  --  --  --  --  --

Array terurut:
18  33  33  36  39  39  44  45  74  92

Array tak-terurut:
90  58  25  62  47  99  93  45  89  28

setelah pass 1: 25 58 90* 62  47  99  93  45  89  28
             --

setelah pass 2: 25 28 90 62 47 99 93 45 89 58*
             --  --

setelah pass 3: 25 28 45 62 47 99 93 90* 89  58
             --  --  --

setelah pass 4: 25 28 45 47 62* 99  93  90  89  58
             --  --  --  --

setelah pass 5: 25 28 45 47 58 99 93 90 89 62*
             --  --  --  --  --

setelah pass 6: 25 28 45 47 58 62 93 90 89 99*
             --  --  --  --  --  --

setelah pass 7: 25 28 45 47 58 62 89 90 93* 99
             --  --  --  --  --  --  --

setelah pass 8: 25 28 45 47 58 62 89 90* 93  99
             --  --  --  --  --  --  --  --

setelah pass 9: 25 28 45 47 58 62 89 90 93* 99
             --  --  --  --  --  --  --  --  --

Array terurut:
25  28  45  47  58  62  89  90  93  99

6.6 Pengurutan Penyisipan
Pengurutan penyisipan merupakan contoh lain dari algoritma pengurutan sederhana, tetapi tidak efisien. Iterasi pertama dari algoritma ini mengambil elemen kedua di dalam array dan, jika ia bernilai kurang dari elemen pertama, maka algoritma menukarnya dengan elemen pertama. Iterasi kedua mengambil elemen ketiga dan menyisipkannya ke posisi tepat, sehingga ketiga elemen pertama menjadi terurut. Pada iterasi ke-i dari algoritma ini, sejumlah i elemen pertama pada array asli akan menjadi terurut.

Perhatikan sebuah contoh array berikut. Perhatikan bahwa array ini identik dengan yang digunakan pada pengurutan seleksi dan pengurutan merge.

34 56 4 10 77 51 93 30 5 52

Sebuah program yang mengimplementasikan algoritma pengurutan penyisipan pertama-tama akan melihat dua elemen pertama array, 34 dan 56. Karena keduanya telah terurut, program akan berlanjut. (Jika kedua elemen tidak terurut, maka program akan menukarkannya).

Pada iterasi berikutnya, program akan melihat nilai ketiga, 4. Nilai ini bernilai kurang dari 56, jadi program menyimpan 4 di dalam sebuah variabel temporer dan menggeser 56 satu elemen ke kanan. Program kemudian memeriksa dan menentukan bahwa 4 bernilai kurang dari 34, jadi ia menggeser 34 satu elemen ke kanan. Program sekarang telah meraih awal array, jadi ia menempatkan 4 di dalam elemen ke-nol. Array sekarang menjadi

4 34 56 10 77 51 93 30 5 52

Pada iterasi berikutnya, program menyimpan 10 di dalam sebuah variabel temporer. Kemudian ia membandingkan 10 dengan 56 dan memindahkan 56 sejauh satu elemen ke kanan karena ia bernilai lebih besar dari 10. Program kemudian membandingkan 10 dengan 34, memindahkan 34 sejauh satu elemen ke kanan. Ketika program membandingkan 10 dengan 4, ia mengamati bahwa 10 lebih besar dari 4 dan menempatkan 10 pada elemen 1. Array sekarang menjadi

4 10 34 56 77 51 93 30 5 52

Dengan menggunakan algoritma ini, pada iterasi ke-i, sejumlah i elemen pertama pada array asli menjadi terurut.

Gambar 6.7 mendeklarasikan kelas PengurutanSeleksi. Baris 22-46 mendeklarasikan metode Urut. Baris 24 mendeklarasikan variabel sisip, yang menampung elemen yang akan Anda sisipkan sementara Anda memindahkan elemen-elemen lain. Baris 27-45 menjelajah sebanyak data.Length – 1 item di dalam array. Pada tiap iterasi, baris 30 menyimpan di dalam sisip nilai dari elemen yang akan disisipkan ke dalam potongan terurut dari array. Baris 33 mendeklarasikan dan menginisialisasi variabel pindahItem, yang berguna untuk menjejak tempat penyisipan elemen.

Baris 36-41 menjelajah array untuk mencari lokasi yang tepat untuk menempatkan elemen yang akan disisipkan. Loop akan berhenti ketika program meraih depan array atau ketika ia menjumpai sebuah elemen yang bernilai kurang dari nilai yang akan disisipkan. Baris 39 memindahkan sebuah elemen ke kanan, dan baris 40 mendekremen posisi di mana elemen berikutnya akan disisipkan. Setelah loop berhenti, baris 43 menyisipkan elemen ke posisi yang tepat.

Gambar 6.8 sama dengan Gambar 6.6 kecuali bahwa ia menciptakan dan menggunakan sebuah objek PengurutanPenyisipan. Keluaran dari program ini menggunakan garis putus-putus untuk mengindikasikan potongan array yang telah terurut setelah tiap iterasi dilakukan.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Gambar 6.7: PengurutanPenyisipan.cs
// Kelas yang menciptakan sebuah array yang diisi dengan int-int acak.
// Menyediakan sebuah metode untuk mengurutkan array dengan pengurutan penyisipan.
using System;

public class PengurutanPenyisipan
{
    private int[] data; // array dengan nilai-nilai
    private static Random pembangkit = new Random();

    // menciptakan sebuah array dengan ukuran tertentu dan mengisi int-int acak
    public PengurutanPenyisipan(int ukuran)
    {
        data = new int[ukuran]; // menciptakan ruang untuk array

        // mengisi array dengan int-int acak dalam rentang 10-99
        for (int i = 0; i < ukuran; i++)
            data[i] = pembangkit.Next(10, 100);
    } // akhir konstruktor PengurutanPenyisipan

// mengurutkan array dengan pengurutan seleksi
public void Urut()
{
    int sisip; // variabel sementara untuk menampung elemen yang akan disisipkan

    // loop menjelajah data.Length - 1 elemen
    for (int berikut = 1; berikut < data.Length; berikut++)
    {
        // menyimpan nilai di dalam elemen sekarang
        sisip = data[berikut];

        // menginisialisasi lokasi untuk menempatkan elemen
        int pindahItem = berikut;

        // mencari tempat untuk menempatkan elemen sekarang
        while (pindahItem > 0 && data[pindahItem - 1] > sisip)
        {
            // menggeser elemen ke kanan
            data[pindahItem] = data[pindahItem - 1];
            pindahItem--;
        } // akhir while

        data[pindahItem] = sisip; // menempatkan elemen yang akan disisipkan
        TampilPass(berikut, pindahItem); // menampilkan pass algoritma
    } // akhir for
} // akhir metode Urut

    // menampilkan sebuah pass dari algoritma
    public void TampilPass(int pass, int indeks)
    {
        Console.Write("setelah pass {0}: ", pass);

        // menampilkan elemen-elemen sampai item terpilih
        for (int i = 0; i < indeks; i++)
            Console.Write(data[i] + " ");

        Console.Write(data[indeks] + "* "); // indikasi penukaran

        // menampilkan isi array lainnya
        for (int i = indeks + 1; i < data.Length; i++)
            Console.Write(data[i] + "  ");

        Console.Write("\n             "); // untuk penyejajaran

        // mengindikasikan jumlah array yang diurutkan
        for (int j = 0; j < pass; j++)
            Console.Write("--  ");
        Console.WriteLine("\n"); // melompati sebaris pada keluaran
    } // akhir metode TampilPass

    // metode untuk menampilkan nilai-nilai pada array
    public override string ToString()
    {
        string sementara = string.Empty;

        // menjelajah array
        foreach (int elemen in data)
            sementara += elemen + "  ";

        sementara += "\n"; // karakter garis-baru
        return sementara;
    } // akhir metode ToString
} // akhir kelas PengurutanPenyisipan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Gambar 6.8: UjiPengurutanPenyisipan.cs
// Menguji kelas pengurutan penyisipan.
using System;

public class UjiPengurutanPenyisipan
{
    public static void Main(string[] args)
    {
        // menciptakan objek untuk melakukan pengurutan penyisipan
        PengurutanPenyisipan urutArray = new PengurutanPenyisipan(10);

        Console.WriteLine("Array tak-terurut:");
        Console.WriteLine(urutArray); // menampilkan array tak-terurut

        urutArray.Urut(); // mengurutkan array

        Console.WriteLine("Array terurut:");
        Console.WriteLine(urutArray); // menampilkan array terurut
    } // akhir Main
} // akhir kelas UjiPengurutanPenyisipan

Array tak-terurut:
50  88  52  71  33  55  40  60  33  51

setelah pass 1: 50 88* 52  71  33  55  40  60  33  51
             --

setelah pass 2: 50 52* 88  71  33  55  40  60  33  51
             --  --

setelah pass 3: 50 52 71* 88  33  55  40  60  33  51
             --  --  --

setelah pass 4: 33* 50  52  71  88  55  40  60  33  51
             --  --  --  --

setelah pass 5: 33 50 52 55* 71  88  40  60  33  51
             --  --  --  --  --

setelah pass 6: 33 40* 50  52  55  71  88  60  33  51
             --  --  --  --  --  --

setelah pass 7: 33 40 50 52 55 60* 71  88  33  51
             --  --  --  --  --  --  --

setelah pass 8: 33 33* 40  50  52  55  60  71  88  51
             --  --  --  --  --  --  --  --

setelah pass 9: 33 33 40 50 51* 52  55  60  71  88
             --  --  --  --  --  --  --  --  --

Array terurut:
33  33  40  50  51  52  55  60  71  88

Array tak-terurut:
30  72  26  62  54  86  11  39  20  97

setelah pass 1: 30 72* 26  62  54  86  11  39  20  97
             --

setelah pass 2: 26* 30  72  62  54  86  11  39  20  97
             --  --

setelah pass 3: 26 30 62* 72  54  86  11  39  20  97
             --  --  --

setelah pass 4: 26 30 54* 62  72  86  11  39  20  97
             --  --  --  --

setelah pass 5: 26 30 54 62 72 86* 11  39  20  97
             --  --  --  --  --

setelah pass 6: 11* 26  30  54  62  72  86  39  20  97
             --  --  --  --  --  --

setelah pass 7: 11 26 30 39* 54  62  72  86  20  97
             --  --  --  --  --  --  --

setelah pass 8: 11 20* 26  30  39  54  62  72  86  97
             --  --  --  --  --  --  --  --

setelah pass 9: 11 20 26 30 39 54 62 72 86 97*
             --  --  --  --  --  --  --  --  --

Array terurut:
11  20  26  30  39  54  62  72  86  97

6.7 Pengurutan Merge
Pengurutan merge merupakan algoritma pengurutan efisien tetapi secara konseptual lebih kompleksi dari pengurutan seleksi dan pengurutan penyisipan. Algoritma pengurutan merge mengurutkan sebuah array dengan membaginya menjadi dua subarray yang berukuran sama, mengurutkan setiap subarray, kemudian menggabungkannya menjadi satu array kembali. Bila terdapat jumlah elemen ganjil, algoritma akan menciptakan dua subarray sehingga salah satu subarray lebih besar dari subarray yang lain.

Implementasi atas pengurutan array pada contoh ini adalah implementasi rekursif. Kasus basis adalah sebuah array dengan satu elemen, yang tentu saja, terurut. Langkah rekursi memecah array menjadi dua subarray berukuran hampir sama (sama jika jumlah elemen genap), mengurutkan kedua subarray, kemudian menggabungkan kedua subarray terurut tersebut menjadi satu array terurut.

Dimisalkan bahwa algoritma telah mengurutkan kedua subarray A:

4 10 34 56 77

dan subarray B:

5 30 51 52 93

Pengurutan merge menggabungkan kedua subarray tersebut menjadi satu array terurut. Elemen terkecil pada A adalah 4 (berlokasi pada indeks ke-nol pada A). Elemen terkecil pada B adalah 5 (berlokasi pada indeks ke-nol pada B). Untuk menentukan elemen terkecil di dalam array, algoritma ini membandingkan 4 dengan 5. Nilai dari A lebih kecil, jadi 4 menjadi elemen pertama di dalam array hasil penggabungan. Algoritma berlanjut dengan membandingkan 10 (elemen kedua di dalam A) dengan 5 (elemen pertama di dalam B). Nilai dari B lebih kecil, jadi 5 menjadi elemen kedua di dalam array hasil penggabungan. Algoritma berlanjut dengan membandingkan 10 dengan 30, dengan 10 menjadi elemen ketiga pada array hasil penggabungan, dan seterusnya.

Baris 22-25 pada Gambar 6.9 mendeklarasikan metode Urut. Baris 24 memanggil metode UrutArray dengan 0 dan data.length – 1 sebagai argumen, yang berkaitan dengan indeks awal dan indeks akhir dari array yang akan diurutkan. Kedua nilai ini memberitahu metode UrutArray untuk beroperasi pada keseluruhan array.

Metode UrutArray dideklarasikan pada baris 28-49. Baris 31 menguji kasus basis. Jika ukuran array adalah 1, maka array tersebut telah terurut, jadi metode selesai dieksekusi. Jika ukuran array lebih besar dari 1, maka metode akan memecah array menjadi dua, secara rekursif memanggil metode UrutArray untuk mengurutkan kedua subarray, kemudian menggabungkan keduanya. Baris 43 secara rekursif memanggil metode UrutArray pada setengah bagian pertama dari array, dan baris 44 secara rekursif memanggil metode UrutArray pada setengah bagian kedua dari array. Ketika dua pemanggilan ini selesai dilakukan, setiap setengah bagian array telah terurut. Baris 47 memanggil metode Gabung (baris 52-91) pada dua subarray terurut untuk menggabungkan keduanya menjadi satu array terurut.

Baris 64-72 pada metode Gabung menjelajah sampai program meraih akhir dari salah satu subarray. Baris 68 menguji apakah elemen pada awal array lebih kecil. Jika elemen di array kiri lebih kecil, maka baris 69 menempatkannya pada posisi yang tepat pada array hasil penggabungan. Jika elemen di array kanan lebih kecil, maka baris 71 menempatkannya pada posisi yang tepat pada array hasil penggabungan. Ketika loop while selesai dieksekusi (baris 72), salah satu subarray telah selesai ditempatkan pada array hasil penggabungan, tetapi subarray lain masih memuat data. Baris 75 menguji apakan array kiri teleh mencapai akhir array. Jika ya, maka baris 77-78 akan mengisi array hasil penggabungan dengan elemen-elemen dari array kanan. Jika array kiri belum mencapai akhir, maka array kanan pasti telah mencapai akhir, dan baris 81-82 mengisi array hasil penggabungan dengan elemen-elemen dari array kiri. Terakhir, baris 85-86 menyalin array hasil penggabungan ke dalam array asli. Gambar 6.10 menciptakan dan menggunakan sebuah objek PengurutanMerge. Keluaran dari program ini menampilkan pemecahan dan penggabungan yang dilakukan pengurutan merge, menampilkan kemajuan pengurutan pada tiap langkah algoritma.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// Gambar 6.9: PengurutanMerge.cs
// Kelas yang menciptakan sebuah array yang diisi dengan int-int acak.
// Menyediakan sebuah metode untuk mengurutkan array dengan pengurutan merge.
using System;

public class PengurutanMerge
{
    private int[] data; // array dengan nilai-nilai
    private static Random pembangkit = new Random();

    // menciptakan sebuah array dengan ukuran tertentu dan mengisi int-int acak
    public PengurutanMerge(int ukuran)
    {
        data = new int[ukuran]; // menciptakan ruang untuk array

        // mengisi array dengan int-int acak dalam rentang 10-99
        for (int i = 0; i < ukuran; i++)
            data[i] = pembangkit.Next(10, 100);
    } // akhir konstruktor PengurutanMerge

    // memanggil metode urutArray secara rekursif
public void Urut()
{
    UrutArray(0, data.Length - 1); // memecah array
} // akhir metode urut

    // memecah array, mengurutkan subarray, dan menggabungkannya
    private void UrutArray(int rendah, int tinggi)
    {
       // menguji kasus basi; ukuran array sama dengan 1
        if ( ( tinggi - rendah ) >= 1 ) // jika tidak kasus basis
        {
            int tengah1 = ( rendah + tinggi ) / 2; // menghitung tengah array
            int tengah2 = tengah1 + 1; // menghitung elemen berikutnya
           
            // menampilkan langkah pemecahan
            Console.WriteLine("pecah:   " + Subarray( rendah, tinggi ) );
            Console.WriteLine("         " + Subarray(rendah, tengah1));
            Console.WriteLine("         " + Subarray(tengah2, tinggi));
            Console.WriteLine();
           
            // memecah array menjadi dua; mengurutkannya (rekursi)
            UrutArray( rendah, tengah1 ); // setengah pertama
            UrutArray( tengah2, tinggi ); // setengah kedua dari array
           
            // menggabungkan array terurut
            Gabung ( rendah, tengah1, tengah2, tinggi );
        } // akhir if
    } // akhir metode UrutArray

    // menggabungkan dua subarray terurut menjadi satu array terurut
    private void Gabung(int kiri, int tengah1, int tengah2, int kanan)
    {
        int indeksKiri = kiri; // indeks dari subarray kiri
        int indeksKanan = tengah2; // indeks dari subarray kanan
        int indeksGabung = kiri; // indeks dari array sementara
        int[] tergabung = new int[data.Length]; // array hasil penggabungan

        // menampilkan dua subarray sebelum penggabungan
        Console.WriteLine("gabung:  " + Subarray(kiri, tengah1));
        Console.WriteLine("          " + Subarray(tengah2, kanan));

        // menggabungkan dua subarray sampai mencapai akhir salah satu subarray
        while (indeksKiri <= tengah1 && indeksKanan <= kanan)
        {
            // menempatkan yang terkecil dari dua elemen sekarang pada hasil
            // dan menggeser ke ruang berikutnya di dalam array
            if (data[indeksKiri] <= data[indeksKanan])
                tergabung[indeksGabung++] = data[indeksKiri++];
            else
                tergabung[indeksGabung++] = data[indeksKanan++];
        } // akhir while

        // jika array kiri kosong
        if (indeksKiri == tengah2)
            // menyalin sisa dari array kanan
            while (indeksKanan <= kanan)
                tergabung[indeksGabung++] = data[indeksKanan++];
        else // array kanan kosong
            // menyalin sisa dari array kiri
            while (indeksKiri <= tengah1)
                tergabung[indeksGabung++] = data[indeksKiri++];

        // menyalin nilai-nilai kembali ke array asli
        for (int i = kiri; i <= kanan; i++)
            data[i] = tergabung[i];

        // menampilkan array tergabung
        Console.WriteLine("        " + Subarray(kiri, kanan));
        Console.WriteLine();
    } // akhir metode Gabung

    // metode untuk menampilkan nilai-nilai tertentu pada array
public string Subarray( int rendah, int tinggi )
{
    string temporer = string.Empty;

    // menampilkan spasi untuk penyejajaran
    for ( int i = 0; i < rendah; i++ )
        temporer += "  ";

    // menampilkan elemen-elemen kiri di dalam array
    for ( int i = rendah; i <= tinggi; i++ )
        temporer += " " + data[ i ];

    return temporer;
} // akhir metode subarray

    // metode untuk menampilkan nilai-nilai pada array
    public override string ToString()
    {
        return Subarray(0, data.Length - 1);
    } // akhir metode ToString
} // akhir kelas PengurutanMerge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Gambar 6.10: UjiPengurutanMerge.cs
// Menguji kelas pengurutan merge.
using System;

public class UjiPengurutanMerge
{
    public static void Main(string[] args)
    {
        // menciptakan objek untuk melakukan pengurutan penyisipan
        PengurutanMerge urutArray = new PengurutanMerge(10);

        Console.WriteLine("Array tak-terurut:");
        Console.WriteLine(urutArray); // menampilkan array tak-terurut

        urutArray.Urut(); // mengurutkan array

        Console.WriteLine("Array terurut:");
        Console.WriteLine(urutArray); // menampilkan array terurut
    } // akhir Main
} // akhir kelas UjiPengurutanMerge

Array tak-terurut:
 65 65 30 97 73 37 88 90 27 90
pecah:    65 65 30 97 73 37 88 90 27 90
          65 65 30 97 73
                         37 88 90 27 90

pecah:    65 65 30 97 73
          65 65 30
                   97 73

pecah:    65 65 30
          65 65
                30

pecah:    65 65
          65
             65

gabung:   65
             65
          65 65

gabung:   65 65
                30
          30 65 65

pecah:          97 73
                97
                   73

gabung:         97
                   73
                73 97

gabung:   30 65 65
                   73 97
          30 65 65 73 97

pecah:              37 88 90 27 90
                    37 88 90
                             27 90

pecah:              37 88 90
                    37 88
                          90

pecah:              37 88
                    37
                       88

gabung:             37
                       88
                    37 88

gabung:             37 88
                          90
                    37 88 90

pecah:                    27 90
                          27
                             90

gabung:                   27
                             90
                          27 90

gabung:             37 88 90
                             27 90
                    27 37 88 90 90

gabung:   30 65 65 73 97
                         27 37 88 90 90
          27 30 37 65 65 73 88 90 90 97

Array terurut:
 27 30 37 65 65 73 88 90 90 97

Array tak-terurut:
 89 35 40 70 17 73 44 34 30 92
pecah:    89 35 40 70 17 73 44 34 30 92
          89 35 40 70 17
                    73 44 34 30 92

pecah:    89 35 40 70 17
          89 35 40
                   70 17

pecah:    89 35 40
          89 35
                40

pecah:    89 35
          89
             35

gabung:   89
             35
          35 89

gabung:   35 89
               40
          35 40 89

pecah:          70 17
                70
                   17

gabung:         70
                   17
                17 70

gabung:   35 40 89
                   17 70
          17 35 40 70 89

pecah:              73 44 34 30 92
                    73 44 34
                             30 92

pecah:              73 44 34
                    73 44
                          34

pecah:              73 44
                    73
                       44

gabung:             73
                       44
                    44 73

gabung:             44 73
                          34
                    34 44 73

pecah:                    30 92
                          30
                             92

gabung:                   30
                             92
                          30 92

gabung:             34 44 73
                             30 92
                    30 34 44 73 92

gabung:   17 35 40 70 89
                         30 34 44 73 92
          17 30 34 35 40 44 70 73 89 92

Array terurut:
 17 30 34 35 40 44 70 73 89 92





Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)