// BQM.java SJ import java.util.*; class BQM { public static void main(String[] args) { // ensimmäinen komentoriviparametri: alkioiden määrä int N = 10; if (args.length > 0) N = Integer.valueOf(args[0]); // toinen parametri: tulostetaanko vai ei, >1 = tulosta boolean tulosta = false; if (args.length > 1 && (Integer.valueOf(args[1]) > 0)) tulosta = true; // kolmas parametri: järjesteyksessä vai ei // -1 : laskeva järjestys, 1 = kasvava järjestys, 0 = satunnainen int J = 0; if (args.length > 2) J = Integer.valueOf(args[2]); // neljäs parametri: k ksort -lajittelulle int K = (int)java.lang.Math.sqrt((double)N); if (args.length > 3) K = Integer.valueOf(args[3]); Integer[] taulu; long start; // Kuplalajittelu if (N <= 20000) { taulu = satunnainenTaulu(N, J, 1); if (tulosta) for (int i = 0; i < N; i++) System.out.print(taulu[i] + " "); System.out.println(); System.out.println("Kuplalajittelu alkaa"); start = (new Date()).getTime(); bubbleSort(taulu); System.out.println(" " + ((new Date()).getTime()-start) + " ms"); if (tulosta) for (int i = 0; i < N; i++) System.out.print(taulu[i] + " "); System.out.println(); } // Pikalajittelu if (!( J!= 0 && N >= 20000)) { taulu = satunnainenTaulu(N, J, 1); System.out.println("Pikalajittelu alkaa"); start = (new Date()).getTime(); quicksort(taulu, 0, N-1); System.out.println(" " + ((new Date()).getTime()-start) + " ms"); if (tulosta) for (int i = 0; i < N; i++) System.out.print(taulu[i] + " "); System.out.println(); } // Pikalajittelu2 if (!( J!= 0 && N >= 20000)) { taulu = satunnainenTaulu(N, J, 1); System.out.println("Pikalajittelu mediaanilla alkaa"); start = (new Date()).getTime(); quicksort2(taulu, 0, N-1); System.out.println(" " + ((new Date()).getTime()-start) + " ms"); if (tulosta) for (int i = 0; i < N; i++) System.out.print(taulu[i] + " "); System.out.println(); } // Lomituslajittelu taulu = satunnainenTaulu(N, J, 1); System.out.println("Mergesort alkaa"); start = (new Date()).getTime(); mergesort(taulu, 0, N-1); System.out.println(" " + ((new Date()).getTime()-start) + " ms"); if (tulosta) for (int i = 0; i < N; i++) System.out.print(taulu[i] + " "); System.out.println(); // Pikavalinta if (N <= 2000) { System.out.println("Pikavalinta alkaa"); start = (new Date()).getTime(); for (int i = 1; i <= N; i++) { taulu = satunnainenTaulu(N, J, 1); if (tulosta) for (int o = 0; o < N; o++) System.out.print(taulu[o] + " "); /* System.out.println(); */ Comparable qs = quickselect(taulu, 0, N-1, i); if (tulosta) System.out.println(i + ":nneksi pienin = " + qs); } System.out.println(" " + ((new Date()).getTime()-start) + " ms"); System.out.println(); } } // main() public static Integer[] satunnainenTaulu(int N, int J, int seed) { Integer[] taulu = new Integer[N]; Random r = new Random(seed); for (int i = 0; i < N; i++) { if (J == 0) taulu[i] = new Integer(r.nextInt(N*2)); else if (J > 0) taulu[i] = new Integer(i); else taulu[i] = new Integer(N-i); } return taulu; } // satunnainenTaulu() public static void bubbleSort(Comparable A[]) { for (int i = 0; i < A.length-1; i++) { for (int j = A.length-1; j > i; j--) { if (A[j-1].compareTo(A[j]) > 0) { Comparable tmp = A[j-1]; A[j-1] = A[j]; A[j] = tmp; } } } } // bubbleSort() public static void bubbleSort(Comparable A[], int alku, int loppu) { for (int i = alku; i < loppu; i++) { for (int j = loppu; j > i; j--) { if (A[j-1].compareTo(A[j]) > 0) { Comparable tmp = A[j-1]; A[j-1] = A[j]; A[j] = tmp; } } } } // bubbleSort() public static void quicksort(Comparable A[], int i, int j) { if (i < j) { int k = partition(A, i, j); quicksort(A, i, k-1); quicksort(A, k+1, j); } } // quicksort() public static void quicksort2(Comparable A[], int i, int j) { if (i < j) { int k = partition2(A, i, j); quicksort2(A, i, k-1); quicksort2(A, k+1, j); } } // quicksort2() public static int partition(Comparable A[], int i, int j) { Comparable jakoalkio = A[i]; // toistetaan kunnes i ja j törmäävät while (i < j) { // etsitään lopusta jakoalkiota pienempi while ((i < j) && (jakoalkio.compareTo(A[j]) < 0)) j--; A[i] = A[j]; // etsitään alusta jakoalkiota suurempi tai yhtäsuuri while ((i < j) && (jakoalkio.compareTo(A[i]) >= 0)) i++; A[j] = A[i]; } // while // jakoalkio paikalleen ja palautetaan sijainti A[i] = jakoalkio; return i; } // partition() // valitsee 3 satunnaista indeksi� v�lilt� i..j, // palauttaa sen indeksin jolle A[] on mediaani public static int med3(Comparable A[], int i, int j) { int[] ind = new int[2]; Random r = new Random(i+j); ind[0] = r.nextInt(j-i+1)+i; int l = r.nextInt(j-i+1)+i; if (A[l].compareTo(A[ind[0]]) < 0) { ind[1] = ind[0]; ind[0] = l; } else ind[1] = l; l = r.nextInt(j-i+1)+i; if (A[l].compareTo(A[ind[0]]) < 0) return ind[0]; else if (A[l].compareTo(A[ind[1]]) < 0) return l; else return ind[1]; } // med3 public static int partition2(Comparable A[], int i, int j) { int jakoind = med3(A, i, j); Comparable jakoalkio = A[jakoind]; A[jakoind] = A[i]; // toistetaan kunnes i ja j t�rm��v�t while (i < j) { // etsit��n lopusta jakoalkiota pienempi while ((i < j) && (jakoalkio.compareTo(A[j]) < 0)) j--; A[i] = A[j]; // etsit��n alusta jakoalkiota suurempi tai yht�suuri while ((i < j) && (jakoalkio.compareTo(A[i]) >= 0)) i++; A[j] = A[i]; } // while // jakoalkio paikalleen ja palautetaan sijainti A[i] = jakoalkio; return i; } // partition2() public static Comparable quickselect(Comparable A[], int i, int j, int k) { if (i < j) { int jako = partition(A, i, j); /* System.out.println("qs i" + i + " j" + j + " k" + k + " ja" + jako); */ if (jako < k-1) return quickselect(A, jako+1, j, k); else if (jako > k-1) return quickselect(A, i, jako-1, k); else return A[jako]; } else return A[i]; } // quickselect() public static void mergesort(Comparable A[], int alku, int loppu) { if (alku < loppu) { int k = (alku + loppu) / 2; mergesort(A, alku, k); mergesort(A, k+1, loppu); merge(A, alku, k, loppu); } } // mergesort() public static void merge(Comparable A[], int i, int k, int j) { // alku talteen int alkupit = k-i+1; Comparable [] apu = new Comparable[alkupit]; for (int a = 0; a < alkupit; a++) apu[a] = A[a+i]; // lomitetaan apu[0..alkupit-1] ja A[k+1..l] int a = 0; int l = k+1; int p = i; /* while (a < alkupit || l <= j) { if (a >= alkupit) A[p++] = A[l++]; else if (l > j) A[p++] = apu[a++]; else if (apu[a].compareTo(A[l]) < 0) A[p++] = apu[a++]; else A[p++] = A[l++]; } */ while (a < alkupit) { if ((l > j) || apu[a].compareTo(A[l]) < 0) A[p++] = apu[a++]; else A[p++] = A[l++]; } } // merge } // BQM class ReverseComparator implements Comparator{ public int compare(T a1, T a2) { return - ((Comparable)a1).compareTo(a2); } } // class ReverseComparator ============================================================================================ // h7_t3.java SJ import java.util.Random; import java.util.Comparator; import java.util.PriorityQueue; class h7_t3 { public static void main(String[] args) { // ensimmäinen komentoriviparametri: alkioiden määrä int N = 10; if (args.length > 0) N = Integer.valueOf(args[0]); // toinen parametri: k valintaan ja osaittaislajitteluun int K = N/2; if (args.length > 1) K = Integer.valueOf(args[1]); if (K > N) K = N; // kolmas parametri: tulostetaanko vai ei, >1 = tulosta boolean tulosta = false; if (args.length > 2 && (Integer.valueOf(args[2]) > 0)) tulosta = true; // Pikavalinta Integer[] taulu = satunnainenTaulu(N, N, N); if (tulosta) { for (int i = 0; i < N; i++) System.out.print(taulu[i] + " "); System.out.println(); } System.out.println("Pikavalinta " + K + " " + quickselect(taulu, K)); // k alkiota lopusta System.out.println("Lajittelu k=" + K); taulu = satunnainenTaulu(N, K, N); if (tulosta) for (int i = 0; i < N; i++) System.out.print(taulu[i] + " "); System.out.println(); lajittelu38(taulu, K); if (tulosta) for (int i = 0; i < N; i++) System.out.print(taulu[i] + " "); System.out.println(); } // main() // tekee satunnaisen N-alkioisen taulukon jossa K alkiota lopussa epäjärjestyksessä public static Integer[] satunnainenTaulu(int N, int K, int seed) { Integer[] taulu = new Integer[N]; Random r = new Random(seed); for (int i = 0; i < N; i++) { taulu[i] = new Integer(r.nextInt(N*5)); } java.util.Arrays.sort(taulu, 0, N-K); return taulu; } // satunnainenTaulu() public static void lajittelu38(Comparable A[], int k) { // loppuosa prioriteettijonoon, suurimmat keulaan PriorityQueue P = new PriorityQueue(k, new ReverseComparator()); /* PriorityQueue P = new PriorityQueue(k); */ int pos = A.length-1; int last = pos; for (int i = 0; i < k; i++) P.add(A[last--]); // lomitetaan lopusta alkaen P ja taulukko while (!P.isEmpty()) { if (last < 0 || P.peek().compareTo(A[last]) > 0) A[pos--] = P.poll(); else A[pos--] = A[last--]; } } public static Comparable quickselect(Comparable A[], int k) { return quickselect(A, 0, A.length-1, k); } public static Comparable quickselect(Comparable A[], int i, int j, int k) { if (i < j) { int jako = partition(A, i, j); // System.out.println("qs i" + i + " j" + j + " k" + k + " ja" + jako); if (jako < k-1) return quickselect(A, jako+1, j, k); else if (jako > k-1) return quickselect(A, i, jako-1, k); else return A[jako]; } else return A[i]; } public static void quicksort(Comparable A[], int i, int j) { if (i < j) { int k = partition(A, i, j); quicksort(A, i, k-1); quicksort(A, k+1, j); } } // quicksort() public static int partition(Comparable A[], int i, int j) { // jakoalkioksi ensimmäinen // NÄIN SAA TEHDÄ VAIN OPETUSTARKOITUKSESSA, EI KOSKAAN // OIKEASSA OHJELMASSA // Harjoitustehtävänä 3-mediaani Comparable jakoalkio = A[i]; // toistetaan kunnes i ja j törmäävät while (i < j) { // etsitään lopusta jakoalkiota pienempi while ((i < j) && (jakoalkio.compareTo(A[j]) < 0)) j--; A[i] = A[j]; // etsitään alusta jakoalkiota suurempi tai yhtäsuuri while ((i < j) && (jakoalkio.compareTo(A[i]) >= 0)) i++; A[j] = A[i]; } // while // jakoalkio paikalleen ja palautetaan sijainti A[i] = jakoalkio; return i; } // partition() } // class h7_t3 class ReverseComparator implements Comparator{ public int compare(T a1, T a2) { return - ((Comparable)a1).compareTo(a2); } } // class ReverseComparator