Rabu, 10 Juni 2015

Mengurutkan data dengan menghitung

Diberikan N buah bilangan bulat (1<N<=20.000.000) dalam rentang antara 1...(2^15-1) (inklusif), urutkanlah data tersebut secara menaik dalam waktu kurang dari atau sama dengan 1 detik! (Asumsikan 1 detik = 100.000.000 operasi).
Mungkin ada yang terkejut melihat besarnya nilai N,dan mungkin ada yang mencoba Quicksort dan berharap lebih banyak testcase yang angkanya manusiawi (apabila soal menggunakan sistem penilaian parsial), dan mungkin juga ada yang sudah tau solusi tepat untuk masalah ini.
Yap!Counting Sort!
Dasar ide :
Terlihat di soal, jangkauan angka pada data tidak besar (2^15-1 itu masih sangat manusiawi),tetapi N sangat besar.Tentunya Quicksort tidak akan mampu melakukan itu dalam 1 detik, apalagi kemungkinan besar pembuat soal sudah menyiapkan testcase yang membuat Quicksort mengalami worst case.

Untuk itu kita perlu strategi sebagai berikut :
Kita hitung satu persatu angka yang ada,angka 1 ada berapa,2 ada berapa,dsb.Setelah itu,kita assign nilai-nilai yang sudah kita hitung tersebut ke dalam array.

Contoh :
Data yang ada:
4 3 5 1 2 3 5 5 1 2
Hitungan :
1 ---- 2
2 ---- 2
3 ---- 2
4 ---- 1
5 ---- 3
Setelah assignment :
1 1 2 2 3 3 4 5 5 5

Potongan kodenya dalam C++:
for(i=0;i<=n-1;i++){
  memo[data[i]]++;      //hitung
}
pos=0;
for(i=min_range;i<=maks_range;i++){
  if (memo[i]>0){
   for (j=0;j<=memo[i]-1;j++){
     data[pos]=i;
     pos++;
     }
   }
}
Dengan array memo adalah array untuk menghitung,array data adalah data yang ingin diurutkan,dan n adalah banyaknya data (looping pertama hanya sampai n-1 karena indeks array pada C/C++ dimulai dari 0)

Kompleksitasnya adalah O(n+k),dimana n adalah banyak data dan k adalah maksrange-minrange.
Untuk soal di atas, (kasarnya) kita hanya butuh 20.032.767 operasi saja,ini (seharusnya) masih jauh dari TLE.

Sekian,
CMIIW

1 komentar:

-Mohon untuk tidak spam di komentar-