Olimpiade Sains Provinsi (OSP) 2013 - Komputer, Nomor 42

for i:= 1 to 10 do
    data2[i] := 0;
for i:= 1 to 10 do
    inc(data2[data1[i]]);

Pada potongan kode diatas, dan diketahui:

data1 : array[1..10] of integer = (3,9,2,2,1,5,7,5,5,8);

Kita dapat mengetahui pada array data2 akan menjadi tabel yang berisi frekuensi kemunculan elemen-elemen dari array data1.

Array data2

i	1	2	3	4	5	6	7	8	9
data2[i]	1	2	1	0	3	0	1	1	1

 

Selanjutnya, pada kode diatas akan dilanjutkan perintah-perintah sebagai berikut:

for i:= 2 to 10 do
   data2[i] := data2[i] + data2[i-1];

Perintah diatas mengubah array data2 dari tabel frekuensi menjadi tabel frekuensi kumulatif.

Array data2 yang telah di-update

i	1	2	3	4	5	6	7	8	9
data2[i]	1	3	4	4	7	7	8	9	10

Pada perintah berikutnya,

for i:= 10 downto 1 do
begin
    data3[data2[data1[i]]] := data1[i];
    dec(data2[data1[i]]);
end;

Jika dilakukan simulasi, maka didapat array data3 akan berisi:

Array data3

i	1	2	3	4	5	6	7	8	9	10
data3[i]	1	2	2	3	5	5	5	7	8	9

 

Pada perintah berikutnya hanya melakukan pencetakan ke layar dengan write, maka keluarannya adalah: 1223555789

 

(Algoritma ini dapat dikatakan algoritma Count Sort)

 

CMIIW