Make your own free website on Tripod.com

Project#1 : Quick Sort in Java Programming

 

*** ҡբͼԴҴ س駡Ѻ¤Ѻ еͧ͢ͺس ʹѺʹع Source Code 鹩Ѻ ¤Ѻ

*** Update : 06/09/2002 07:30:00

 

import java.io.*;

import java.util.*;

 

public class qsort

{

 

        /*

         * My print out data to screen

         *

         */

        public static void PrintData(int array[], int elements)

        {

                int Counter,Line,SkipLine,i;

                Counter=0;

                Line=1;

                SkipLine=10;

                System.out.print("Line #");

                System.out.print(Line);

                System.out.print(".: ");

 

                for (i=0; i<elements; i++)

                {

                   if(Counter<SkipLine)

                   {

                        Counter++;

                   }

                   else

                   {

                        Counter=1;

                        Line++;

                        System.out.println();

                        System.out.print("Line #");

                        System.out.print(Line);

                        System.out.print(".: ");

                   }

                   System.out.print(array[i]+" ");

                }

                System.out.println();

        }

        /*

         * Ein einfaches, zweiteiliges QuickSort

         */

        public void Quick(int array[], int elements)

        {

                q_sort(array, 0, elements-1);

        }

        private void q_sort(int array[], int links, int rechts)

        {

                int tmp, i, j, x;

                x = array[(links+rechts)/2];

                i = links;

                j = rechts;

 

                do

                {

                        while (array[i]<x) i++;

                        while (array[j]>x) j--;

 

                        if (i<j)

                        { // SWAP

                                tmp = array[i];

                                array[i] = array[j];

                                array[j] = tmp;

                        }

 

                        if (i<=j)

                        {

                                i++;

                                j--;

                        }

                }

                while (i<=j);

 

                if (links<j)  q_sort(array, links, j);

                if (i<rechts) q_sort(array, i, rechts);

        }

 

        /*

         * nochmal QuickSort in leicht angeaenderter Form

         */

        public void Quick2(int array[], int left, int right)

        {

                int i, j, tmp;

                if (right>left)

                {

                        i = left-1;

                        j = right;

                        do

                        {

                                do i++; while (array[i]<array[right]);

                                do j--; while (array[j]>array[right] && j>0);

 

                                { // SWAP

                                        tmp = array[i];

                                        array[i] = array[j];

                                        array[j] = tmp;

                                }

                        }

                        while (j>i);

 

                        array[j] = array[i];

                        array[i] = array[right];

                        array[right] = tmp;

                        Quick2(array, left, i-1);

                        Quick2(array, i+1, right);

                }

        }

 

        /*

         * Ein iteratives QuickSort

         *

         * TODO: habe ich die obere Schranke fuer die Groesse des Stack

         * richtig bestimmt?

         */

        public void iQuick(int array[], int elements)

        {

                int left=0, right=elements-1, top=0;

                int sSize = (int)Math.ceil(Math.log(elements)/Math.log(2));

                int lStack[] = new int[sSize];

                int rStack[] = new int[sSize];

                int tmp;

                int i, j, x;

 

                lStack[top] = left; rStack[top] = right;

 

                while (top >= 0)

                {

                        left = lStack[top];

                        right = rStack[top];

                        top--;

 

                        while (left < right)

                        {

                                i = left;

                                j = right;

                                x = array[(left+right)/2];

 

                                while (i <= j)

                                {

                                        while (array[i] < x) i++;

                                        while (array[j] > x) j--;

 

                                        if (i<=j)

                                        {

                                                { // SWAP

                                                        tmp = array[i];

                                                        array[i] = array[j];

                                                        array[j] = tmp;

                                                }

                                                i++;

                                                j--;

                                        }

                                }

 

                                if (j-left < right-i)

                                {

                                        if (i < right)

                                        {

                                                top++;

                                                lStack[top] = i;

                                                rStack[top] = right;

                                        }

                                        right = j;

                                }

                                else

                                {

                                        if (left < j)

                                        {

                                                top++;

                                                lStack[top] = left;

                                                rStack[top] = j;

                                        }

                                        left = i;

                                }

                        }

                }

        }

 

 

    /*

     * Main Program

     * By : Mr.Somkieat Sontiwattrakul

     * Create Date : 02/09/2002

     * Update Date : 04/09/2002

     */

        public static void main(String[] Args)

        {

 

    //

    // Input value [1-1000] from keyboard

    //

    int i,MaxValue=0;

    char c;

    InputStreamReader is = new InputStreamReader( System.in );

 

    // Wrap input with a BufferReader to get

    // the readln() method to read a whole line at once.

    BufferedReader br = new BufferedReader( is );

 

    // String Tokenizer will split string using white space

    // as the tokens.

    StringTokenizer st;

 

    System.out.println( "<-------------------------------------------->");

    System.out.println( "< Project#1 : Quick Sort in Java Programming >");

    System.out.println( "<-------------------------------------------->");

    System.out.print( "Input value [1-1000] : ");

    try {

      String s = br.readLine(); // Read the whole line

      st = new StringTokenizer(s);

      // With tokenizer nextToken() method we can ignore

      // any beginning and trailing white space.

      //System.out.println("Read Line:["+s+"]");

      int len=s.length();

      //System.out.println(len);

      if(len>0)

      {

      //System.out.println("Transger :["+st+"]");

      MaxValue=Integer.parseInt(st.nextToken());//Convert string to int

      //System.out.println( "got value: " + MaxValue );

      }

 

    } catch (IOException ioe) {

               System.out.println( "IO error:" + ioe );

    }

    //

    // Check range of Number to be 1 - 1000

    //

        String msg;

        if(MaxValue==0)

         {

         msg="Good bye.";

         System.out.println(msg);

         }

        else if(MaxValue<1)

         {

         msg="Number is less than 1. Try again";

         System.out.println(msg);

         }

        else if(MaxValue>1000)

         {

         msg="Number is more than 1000. Try again";

         System.out.println(msg);

         }

        else

         {

         msg="Number is correct.";       

    //

    //

    //

                int SortierFeld[] = new int[MaxValue];

                int sel=0;

                qsort S = new qsort();

                Random rand = new Random(System.currentTimeMillis());

 

                System.out.println("---> Before : Sort");

 

                for (i=0; i<SortierFeld.length; i++)

                        SortierFeld[i] = Math.abs(rand.nextInt()) % 256;

    //

    // Print all data before Sort.

    //

                PrintData(SortierFeld,SortierFeld.length);

                System.out.print("---> Press [Enter] to contiunous: ");

   //

   // Wait for press Enter key to continous

   //

                try {

                  sel=System.in.read();

                } catch(Exception e)

                {System.out.println("Error");}

 

                System.out.println("---> Sorting !!! Option #1");

   //

   // Begin Sorting -> Select option of QuickSort

   //

                S.Quick(SortierFeld,SortierFeld.length);

                //S.Quick2(SortierFeld,0,SortierFeld.length-1);

                //S.iQuick(SortierFeld,SortierFeld.length);

    //

    // Print all data after Sort.

    //

                System.out.println("---> After  : Sort");

                PrintData(SortierFeld,SortierFeld.length);

    //

    // Finish.

    //

                System.out.println("---> Finish.");

        }

        }

}

 

 

Ѻ Click Mouse Save Target As Ѻ  qsort.java

 

˹Ҩ͵ҧ