digrach

Sorting and searching

Apr 1st, 2014
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.04 KB | None | 0 0
  1. public class BubbleSortDemo {
  2.  
  3.     public static void main(String[] args) {
  4.  
  5.         System.out.println();
  6.         System.out.println("* * * * * * * * * * * * * * * * * * * * * ");
  7.         System.out.println("******************************************");
  8.         System.out.println("********* Sorting and searching **********");
  9.         System.out.println("*********** THE FUN NEVER ENDS ***********");
  10.         System.out.println("******************************************");
  11.         System.out.println("* * * * * * * * * * * * * * * * * * * * * ");
  12.         System.out.println();
  13.  
  14.         // Arrays are in parallel with each other - this means that
  15.         // the first top score in topScores belongs to the first username in userNames.
  16.  
  17.         // Array of top scores.
  18.         int topScores[] = {100000, 34987, 55876, 45264, 41345, 88900, 87667, 67467, 75449, 71989};
  19.         // Array of usernames.
  20.         String userNames[] = {"straven", "kiddthunda", "boingboing", "tunzapun", "soonami", "straven", "kiddthunda", "slasher", "kiddthunda", "shanus"};
  21.  
  22.  
  23.         print(topScores, "Print *UNSORTED* topScores array");
  24.  
  25.         bubbleSort(topScores, userNames);
  26.  
  27.         print(topScores, "Print *SORTED* topScores array");
  28.  
  29.         boolean ss1 = sequentialSearch(topScores, 87667);
  30.         System.out.println("87667 found = " + ss1);
  31.         boolean ss2 = sequentialSearch(topScores, 41345);
  32.         System.out.println("41345 found = " + ss1);
  33.         boolean ss3 = sequentialSearch(topScores, 50000);
  34.         System.out.println("50000 found = " + ss1);
  35.  
  36.         boolean bs1 = binarySearch(topScores, 87667);
  37.         System.out.println("87667 found = " + bs1);
  38.         boolean bs2 = binarySearch(topScores, 41345);
  39.         System.out.println("41345 found = " + bs1);
  40.         boolean bs3 = binarySearch(topScores, 50000);
  41.         System.out.println("50000 found = " + bs1);
  42.  
  43.         print(topScores, userNames, "Final *SORTED* data");
  44.  
  45.  
  46.         System.out.println();
  47.         System.out.println("* * * * * * * * * * * * * * * * * * * * * ");
  48.         System.out.println("******************************************");
  49.         System.out.println("**************** KTHXBAI *****************");
  50.         System.out.println("******************************************");
  51.         System.out.println("* * * * * * * * * * * * * * * * * * * * * ");
  52.         System.out.println();
  53.  
  54.  
  55.  
  56.     }
  57.  
  58.     public static void bubbleSort(int a[], String s[]) {
  59.  
  60.         System.out.println();
  61.         System.out.println("*************************************");
  62.         System.out.println("**** Bubble sorting right now!! *****");
  63.         System.out.println("*************************************");
  64.         System.out.println();
  65.  
  66.         // Bubble sort the top scores from greatest to lowest.
  67.         // The usernames are also sorted but only after a topscore sort happens.
  68.         // The outer loop compares gets the current score
  69.         // In the loop primer, we subtract 1 from the length of the array.
  70.         // This is because we need not check the last number against the next number
  71.         // because there is no next number!
  72.         for (int outerLoop = 0; outerLoop < a.length - 1 ; outerLoop ++) {
  73.             // The inner loops compares the score in the outer loop
  74.             // to each score in the inner loop.
  75.             for (int innerLoop = 0; innerLoop < a.length - 1; innerLoop ++) {
  76.                 // If the current topscore is less than the next topscore, do the swap.
  77.                 if (a[innerLoop] > a[innerLoop + 1]) {
  78.                     int tempTopScore = a[innerLoop]; // Store current index value in a temp variable.
  79.                     a[innerLoop] = a[innerLoop + 1]; // Assign the next index value to the current index.
  80.                     a[innerLoop + 1] = tempTopScore; // Assign temp to the next index.
  81.                     // Keep the String array in parallel with the int array.
  82.                     if (s != null) {
  83.                         String tempUserName = s[innerLoop];
  84.                         s[innerLoop] = s[innerLoop + 1];
  85.                         s[innerLoop + 1] = tempUserName;
  86.                     }
  87.                 }
  88.             }
  89.         }
  90.     }
  91.  
  92.     public static boolean binarySearch(int[] a, int target) {
  93.  
  94.         int first = 0;
  95.         int last = a.length - 1;
  96.  
  97.         System.out.println();
  98.         System.out.println("*************************************");
  99.         System.out.println("***** Binary search for " + target);
  100.         System.out.println();
  101.  
  102.         int countSearchLoops = 1;
  103.  
  104.         while (first <= last) {
  105.  
  106.             int middle = (first + last) / 2;
  107.  
  108.             System.out.println("   first index: " + first);
  109.             System.out.println("   last index: " + last);
  110.             System.out.println("   middle index: " + middle);
  111.             System.out.println("   middle value: " + a[middle]);
  112.             System.out.println("   Comparing " + target + " to " + a[middle]);
  113.  
  114.             if (target == a[middle]) {
  115.                 System.out.println();
  116.                 System.out.println("   FOUND " + target + " at index " + middle);
  117.                 System.out.println("   ***** Total search loop count: " + countSearchLoops);
  118.                 return true;
  119.             } else if (target < a[middle]) {
  120.                 System.out.println("   " + target + " is less than " + a[middle]);
  121.                 last = middle - 1;
  122.                 System.out.println("   < changing last index to " + last);
  123.             } else if (target > a[middle]) {
  124.                 System.out.println("   " + target + " is greater than " + a[middle]);
  125.                 first = middle + 1;
  126.                 System.out.println("   > changing first index to " + first);
  127.             }
  128.  
  129.             countSearchLoops ++;
  130.  
  131.             System.out.println();
  132.  
  133.         }
  134.  
  135.             return false;
  136.  
  137.     }
  138.  
  139.     public static boolean sequentialSearch(int a[], int target) {
  140.  
  141.         System.out.println();
  142.         System.out.println("*************************************");
  143.         System.out.println("***** Sequential search for " + target);
  144.         System.out.println();
  145.  
  146.         for (int x = 0; x < a.length; x++) {
  147.             if (a[x] == target) {
  148.                 System.out.println("   " + target + " found at index " + x);
  149.                 System.out.println("   ***** Total search loop count: " + (x + 1));
  150.                 return true;
  151.             }
  152.         }
  153.  
  154.         return false;
  155.     }
  156.  
  157.     public static void print(int[] a, String header) {
  158.  
  159.         System.out.println();
  160.         System.out.println("********** " + header + " **********");
  161.  
  162.         for (int x = 0; x < a.length; x ++ ) {
  163.             System.out.print(a[x] + ", ");
  164.         }
  165.  
  166.         System.out.println();
  167.  
  168.     }
  169.  
  170.     public static void print(int[] a, String[] s, String header) {
  171.  
  172.         System.out.println();
  173.         System.out.println("********** " + header + " **********");
  174.  
  175.         for (int x = 0; x < a.length; x ++ ) {
  176.             System.out.println(s[x] + "'s score " + a[x]);
  177.         }
  178.  
  179.         System.out.println();
  180.  
  181.     }
  182.  
  183. }
Advertisement
Add Comment
Please, Sign In to add comment