Auf Thema antworten

Hallo zusammen, soweit so gut, habe jetzt alles aufgeräumt, jetzt bleibt nur noch eine Sache uebrig, Quicksort..


Ich wuerde folgenden gerne wie in diesem Code schnipsel welches ich auf stackoverflow gefunden habe implementieren.


Einer der hiesigen User war so nett und hat mir ohne Nachfrage einen funktionierenden Quicksort geschickt.


Allerdings wuerde ich in "Version 1" noch gerne den Quicksort in einer Methode haben und erst beim zweiten Anlauf mit GUI alles "richtigerweise" Objektorientiert machen..



Wo ich jetzt noch einen Denkanstoß bräuchte, wie macht man das nun mit Buchstaben?


Original von StackOverflow

[CODE=java]class Quicksort {




    @FunctionalInterface


    public interface Func {


        void call(int[] arr, int i, int j);


    }




     void Quicksortzahlen (String[] args) {




        System.out.println("Unsorted array: " + Arrays.toString(numbers));




        // store swap function as a lambda to avoid code duplication


        Func swap = (int[] arr, int i, int j) -> {


            int temp = arr[i];


            arr[i] = arr[j];


            arr[j] = temp;


        };




        Stack<Integer> stack = new Stack<>();


        stack.push(0);


        stack.push(numbers.length);




        while (!stack.isEmpty()) {


            int end = stack.pop();


            int start = stack.pop();


            if (end - start < 2) {


                continue;


            }




            // partitioning part


            int position = start + ((end - start) / 2);


            int low = start;


            int high = end - 2;


            int piv = numbers[position];


            swap.call(numbers, position, end - 1);


            while (low < high) {


                if (numbers[low] < piv) {


                    low++;


                } else if (numbers[high] >= piv) {


                    high--;


                } else {


                    swap.call(numbers, low, high);


                }


            }


            position = high;


            if (numbers[high] < piv) {


                position++;


            }


            swap.call(numbers, end - 1, position);


            // end partitioning part




            stack.push(position + 1);


            stack.push(end);


            stack.push(start);


            stack.push(position);


        }




        System.out.println("Sorted array: " + Arrays.toString(numbers));


    }





}  [/CODE]




Mein Versuch

[CODE=java]

import java.util.ArrayList;

import java.util.Stack;


class Quicksort {

    ArrayList<Integer> array01Zahlen = new ArrayList<>();


    @FunctionalInterface

    public interface Func {

        void call(ArrayList<Integer> arr, int i, int j);

    }


     void Quicksortzahlen (ArrayList<Integer> array01Zahlen) {


         // store swap function as a lambda to avoid code duplication

        Func swap = (ArrayList<Integer> arr, int i, int j) -> {

            int temp = arr.get(i);

            arr.set(i, arr.get(j));

            arr.set(j, temp);

        };


        Stack<Integer> stack = new Stack<>();

        stack.push(0);

        stack.push(array01Zahlen.size());


        while (!stack.isEmpty()) {

            int end = stack.pop();

            int start = stack.pop();

            if (end - start < 2) {

                continue;

            }


            // partitioning part

            int position = start + ((end - start) / 2);

            int low = start;

            int high = end - 2;

            int piv = array01Zahlen.get(position);

            swap.call(array01Zahlen, position, end - 1);

            while (low < high) {

                if (array01Zahlen.get(low) < piv) {

                    low++;

                } else if (array01Zahlen.get(high) >= piv) {

                    high--;

                } else {

                    swap.call(array01Zahlen, low, high);

                }

            }

            position = high;

            if (array01Zahlen.get(high) < piv) {

                position++;

            }

            swap.call(array01Zahlen, end - 1, position);

            // end partitioning part


            stack.push(position + 1);

            stack.push(end);

            stack.push(start);

            stack.push(position);

        }


            }

 [/CODE]



 geht sogar :D !

[ATTACH=full]12278[/ATTACH]



Oben