Menghitung Kompleksitas Algoritma Pengurutan Descending

Descending

Pengurutan data (sorting) didefinisikan sebagai suatu proses untuk menyusun

kembali humpunan obyek menggunakan aturan tertentu. Mnurut Microsoft Book-shelf,

definisi algoritma pengurutan adalah algoritma untuk meletakkan kumpulan elemen data

ke dalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.

• urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling

kecil.

Contoh : data bilangan 5, 2, 6 dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6 atau diurutkan

turun menjadi 6, 5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil atau

lebih besar dari yang lain didasarkan pada urutan relatif (collating sequence)

Keuntungan dari data yang sudah dalam keadaan terurutkan antara lain :

• data mudah dicari (misalnya dalam buku telepon atau kamus bahasa), mudah untuk

dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadaan terurutkan, kita

mudah melakukan pengeekan apakah ada data yang hilang

• melakukan komppilasi program komputer jika tabel-tabel simbol harus dibentuk

• mempercepat proses pencarian data yang harus dilakukan berulang kali.

48

Data yang diurutkan sangat bervariasi, dalam hal jumlah data maupun jenis data

yang akan diurutkan. Tidak ada algoritma terbaik untuk setiap situasi yang kita hadapi,

bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi

tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan.

Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara

lain:

• banyak data yang diurutkan

• kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki

• tempat penyimpanan data, misalnya piringan, pita atau kartu, atau media penyimpan

yang lain.

Pemilihan algoritma sangat ditentukan oleh struktur data yang digunakan. Metode

pengurutan yang digunakan dapat diklasifikasikan menjadi dua katagori yaitu :

• pengurutan internal, yaitu pengurutan dengan menggunakan larik (array). Larik

tersimpan dalam memori utama komputer

• pengurutan eksternal, yaitu pengurutan dengan menggunakan berkas (sequential

access file). Berkas tersimpan dalam pengingat luar, misalnya cakram atau pita

magnetis.

Untuk menggambarkan pengurutan dengan larik, bisa kita bayangkan semua kartu

terletak di hadapan kita sehingga semua kartu terlihat dengan jelas nomornya. Pada

penyusunan kartu sebagai sebuah berkas, kita bayangkan semua kartu kita tumpuk

sehingga hanya kartu bagian atas saja yang bisa kita lihat nomornya.

Ini adalah sebuah program urut dengan masukan 4 nama buah, yang kemudian akan di keluarkan secara berurutan berdasarkan abjad. Pengurutan dalam program ini dapat kita lakukan secara descending. Berikut adalah Source Code dari program urut.

Berikut ini adalah contoh source code dari descending

Program Urut;

uses wincrt;

label       

1,2;

var       x : array[0..3] of string;

y : array[0..3] of string;

pilih : char;

i : integer;

procedure Descending;

var      

i,j, tempatnya_min : integer;

min, temp : string;

begin

for j := 0 to 3 do

     begin        

         min := x[j];

                    for i := j to 3 do

begin

    if (x[i] >= min) then

        begin

min := x[i];

tempatnya_min := i;

        end;

end;

        temp := x[j];

        x[j] := x[tempatnya_min];

        x[tempatnya_min] := temp;

end;

clrscr;

gotoXY(5,17); writeln('Hasil data yang telah di urut secara Descending');

for i := 0 to 3 do

begin

     gotoxy(25,19+i); write(x[i]);

end;

       end;

C (n)                C op

                   

input1              a

= 6                   b

+1                    c
output 1           d

T (n) =  a + 6.b + c + d