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

หน้าจอตัวอย่าง