Shaker (cocktail) сортирање lab5.2

Shaker (cocktail) сортирање Problem 2 (0 / 0)

Дадена е низа со N природни броеви. Треба да се сортира низата со помош на таканареченото shaker (cocktail) сортирање. Ова сортирање е варијација на сортирањето со меурчиња (bubble sort) со тоа што во секоја итерација низата се изминува два пати. Во првото поминување најмалиот елемент се поместува на почетокот на низата, а при второто најголемиот елемент се поместува на крајот. Во првиот ред од влезот даден е бројот на елементи во низата N, а во вториот ред се дадени броевите. На излез треба да се испечати низата по секое изминување во посебен ред.

Име на класата: ShakerSort


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ShakerSort {

    static void shakerSort(int a[], int n)
    {
        int minCounter = 0;
        int maxCounter = 0;
        boolean done = false;
        for (int j=0; j < (a.length+1)/2; ++j) {

        done = true;

        //bubbleSortMin
        for (int i = a.length-1; i > minCounter; --i) {
                if (a[i] < a[i-1]) {
                    int temp = a[i];
                    a[i] = a[i-1];
                    a[i-1] = temp;
                    done = false;
                }
            }
        ++minCounter;
        write(a);

        //bubbleSortMax
        for (int i= maxCounter; i < a.length -1; ++i ) {
            if (a[i] > a[i+1]) {
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                done = false;
            }
        }
        ++maxCounter;
        write(a);
        if (done)
            break;
        }
    }

    static void write(int [] a) {
        int i;
        for (i=0; i<a.length; ++i)
            System.out.print(a[i] + " ");
        System.out.println();
    }


    public static void main(String[] args) throws IOException{
        int i;
        BufferedReader stdin = new BufferedReader( new InputStreamReader(System.in));
        String s = stdin.readLine();
        int n = Integer.parseInt(s);

        s = stdin.readLine();
        String [] pom = s.split(" ");
        int [] a = new int[n];
        for(i=0;i<n;i++)
            a[i]=Integer.parseInt(pom[i]);
        shakerSort(a,n);
    }
}



Sample input

8
6 10 13 5 8 17 2 5

Sample output

2 6 10 13 5 8 17 5
2 6 10 5 8 13 5 17
2 5 6 10 5 8 13 17
2 5 6 5 8 10 13 17
2 5 5 6 8 10 13 17
2 5 5 6 8 10 13 17
2 5 5 6 8 10 13 17
2 5 5 6 8 10 13 17