Stamenco

АПС - Shaker (cocktail) сортирање

Dec 4th, 2020
595
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Shaker (cocktail) сортирање
  2.  
  3. Дадена е низа со N природни броеви. Треба да се сортира низата со помош на таканареченото shaker (cocktail) сортирање. Ова сортирање е варијација на сортирањето со меурчиња (bubble sort) со тоа што во секоја итерација низата се изминува два пати. Во првото поминување најмалиот елемент се поместува на почетокот на низата, а при второто најголемиот елемент се поместува на крајот. Во првиот ред од влезот даден е бројот на елементи во низата N, а во вториот ред се дадени броевите. На излез треба да се испечати низата по секое изминување во посебен ред.
  4.  
  5. Име на класата: ShakerSort */
  6.  
  7. import java.io.BufferedReader;
  8. import java.io.IOException;
  9. import java.io.InputStreamReader;
  10.  
  11. public class ShakerSort {
  12.  
  13.     static void shakerSort(int[] a, int n) {
  14.         int minCounter = 0;
  15.         int maxCounter = 0;
  16.         boolean done = false;
  17.         for (int j = 0; j < (a.length + 1) / 2; ++j) {
  18.  
  19.             done = true;
  20.  
  21.             for (int i = a.length - 1; i > minCounter; --i) {
  22.                 if (a[i] < a[i - 1]) {
  23.                     int temp = a[i];
  24.                     a[i] = a[i - 1];
  25.                     a[i - 1] = temp;
  26.                     done = false;
  27.                 }
  28.             }
  29.             ++minCounter;
  30.             write(a);
  31.            
  32.             for (int i = maxCounter; i < a.length - 1; ++i) {
  33.                 if (a[i] > a[i + 1]) {
  34.                     int temp = a[i];
  35.                     a[i] = a[i + 1];
  36.                     a[i + 1] = temp;
  37.                     done = false;
  38.                 }
  39.             }
  40.             ++maxCounter;
  41.             write(a);
  42.             if (done)
  43.                 break;
  44.         }
  45.     }
  46.  
  47.     static void write(int[] a) {
  48.         int i;
  49.         for (i = 0; i < a.length; ++i)
  50.             System.out.print(a[i] + " ");
  51.         System.out.println();
  52.     }
  53.  
  54.  
  55.     public static void main(String[] args) throws IOException {
  56.         int i;
  57.         BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
  58.         String s = stdin.readLine();
  59.         int n = Integer.parseInt(s);
  60.  
  61.         s = stdin.readLine();
  62.         String[] pom = s.split(" ");
  63.         int[] a = new int[n];
  64.         for (i = 0; i < n; i++)
  65.             a[i] = Integer.parseInt(pom[i]);
  66.         shakerSort(a, n);
  67.     }
  68. }
  69.  
RAW Paste Data