Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Random;
- import java.util.Scanner;
- public class Ld_test {
- public static void firstMethod(int[] a) { //1.metode - uzlabota ieklausanas metode
- long t1 = System.nanoTime();
- int b[] = new int[2 * a.length - 1];
- int l = a.length - 1;
- int r = l;
- b[r] = a[0];
- for (int i = 1; i < a.length; i++) {
- if (b[l] >= a[i]) {
- l--;
- b[l] = a[i];
- } else if
- (b[r] <= a[i]) {
- r++;
- b[r] = a[i];
- }
- else
- {
- int j;
- for (j = l; j <= r; j++) {
- if (a[i] <= b[j])
- break;
- }
- if (j - l < r - j) {
- for (int k = l; k <= j - 1; k++)
- b[k - 1] =b[k];
- l--;
- b[j - 1] = a[i];
- }
- else
- {
- for (int k = r; k >= j; k--)
- b[k + 1] = b[k];
- r++;
- b[j] = a[i];
- }
- }
- }
- for (int i = 0; i < a.length; i++) {
- a[i] = b[l];
- l++;
- }
- long t2 = System.nanoTime();
- long t = t2 - t1;
- System.out.println("t="+t);
- }
- public static void secondMethod(int[] a) { //2.metode - Hoara bez rekursijas
- long startTime = System.nanoTime();
- int left[] = new int[a.length / 2];
- int right[] = new int[a.length / 2];
- short p = 0;
- int stackpos = 1;
- int m = 0, l = 0, r = 0 ,i = 0, j = 0;
- left[0] = 0;
- right[0] = a.length - 1;
- p = 3;
- do {
- switch (p) {
- case 3:
- stackpos -= 1;
- l = left[stackpos];
- r = right[stackpos];
- p = 4;
- break;
- case 4:
- m = (a[l] + a[r]) / 2;
- i = l;
- j = r;
- p = 6;
- break;
- case 6:
- while (a[i] < m) i++;
- while (a[j] > m) j--;
- if (i <= j) {
- int temp = a[i];
- a[i] = a[j];
- a[j] = temp;
- i++;
- j--;
- }
- if (i <= j) {
- p = 6;
- break;
- }
- if (i < r) {
- left[stackpos] = i;
- right[stackpos] = r;
- stackpos += 1;
- }
- r = j;
- if (l < r) {
- p = 4;
- break;
- }
- if (stackpos > 0) {
- p = 3;
- break;
- } else p = 1;
- break;
- }
- } while (p != 1);
- long estimatedTime = System.nanoTime() - startTime;
- System.out.println("t=" + estimatedTime);
- return;
- }
- public static void main(String[] args) { //3.daļa - masīva izvade
- int numurs;
- int metode;
- System.out.println("Anete Brenčuka RDBF0 161RDB155");
- System.out.print("method: ");
- Scanner sc = new Scanner(System.in);
- if (sc.hasNextInt()){
- numurs = sc.nextInt();
- }
- else
- {
- System.out.println("input-output error");
- sc.close();
- return;
- }
- if (numurs != 1 && numurs != 2) {
- System.out.println("input-output error");
- sc.close();
- return;
- }
- System.out.print("count: ");
- if (sc.hasNextInt())
- metode = sc.nextInt();
- else {
- System.out.println("input-output error");
- sc.close();
- return;
- }
- int a[] = new int[metode];
- Random randomNumberGenerator = new Random();
- for (int i = 0; i < a.length; i++) {
- a[i] = randomNumberGenerator.nextInt();
- }
- sc.close();
- switch (numurs) {
- case 1: firstMethod(a);
- break;
- case 2: secondMethod(a);
- break;
- default:
- System.out.println("input-output error");
- return;
- }
- System.out.println("sorted: ");
- for (int i = 0; i < a.length; i++)
- System.out.print(a[i] + " ");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement