Izpitno vprašanje RAČ2PRA 12700

Iz MaFiRaWiki

Dana je tabela neničelnih celih števil. Uredi jo tako, da bodo najprej soda negativna števila, nato soda pozitivna, nato liha negativna števila in še liha pozitivna števila. Uporabi vsaj dva različna algoritma in analiziraj časovno zahtevnost svojega algoritma!

  1. public class Uredi{
  2.  
  3. public static void urejanje(int[] a){
  4. //v tabeli NI nicelnih elementov!
  5. int levi = 0;
  6. int desni = a.length - 1;
  7.  
  8. //preuredimo tako, da je prvi del tabele sod in drugi lih
  9. while (levi < desni){
  10. //dokler smo se v levem delu in so elti sodi
  11. while (levi < desni && (a[levi]%2 == 0))
  12. levi++;
  13. //dokler smo se v desnem delu in so elti lihi
  14. while (levi < desni && (a[desni]%2 != 0))
  15. desni--;
  16. //zamenjamo
  17. int t = a[levi];
  18. a[levi] = a[desni];
  19. a[desni] = t;
  20. }
  21. int del = levi; // do kje so sodi elementi
  22. levi = 0; // zacetek sodih
  23. desni = levi; // konec sodih
  24.  
  25. //preuredimo na negativne / pozitivne
  26. while (levi < desni){
  27. //dokler smo se v levem delu in so elti negat.
  28. while (levi < desni && a[levi] < 0)
  29. levi++;
  30. //dokler smo se v desnem delu in so elti pozitivni
  31. while (levi < desni && a[desni] > 0)
  32. desni--;
  33. // zamenjamo
  34. int t = a[levi];
  35. a[levi] = a[desni];
  36. a[desni] = t;
  37. }
  38. levi = del + 1; //kje se zacnejo lihi
  39. desni = a.length - 1; //kje se koncajo lihi
  40. while (levi < desni){
  41. while (levi < desni && a[levi] < 0)
  42. levi++;
  43. while (levi < desni && a[desni] > 0)
  44. desni--;
  45. //zamenjamo
  46. int t = a[levi];
  47. a[levi] = a[desni];
  48. a[desni] = t;
  49. }
  50. }
  51. }

ČASOVNA ZAHTEVNOST: Prva glavna zanka (preurejanje sodi/lihi) preteče vse elemente tabele. Pri tem opravimo n primerjav elementov. V tej zanki v najboljšem primeru opravimo 2 zamenjavi in v najslabšem n zamenjav.

Osebna orodja