Java/Collections Data Structure/Sort Search
Содержание
- 1 A binary search implementation.
- 2 Animation for quick sort
- 3 A quick sort demonstration algorithm
- 4 A simple applet class to demonstrate a sort algorithm
- 5 Binary Search
- 6 Binary search routines
- 7 Bubble sort
- 8 Combine Quick Sort Insertion Sort
- 9 Fast Merge Sort
- 10 FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows, using the comparator.
- 11 Fast Quick Sort
- 12 Heap sort
- 13 Insert sort
- 14 Insert Sort for objects
- 15 Linear search
- 16 Merge sort
- 17 Performing Binary Search on Java byte Array Example
- 18 Performing Binary Search on Java char Array Example
- 19 Performing Binary Search on Java double Array Example
- 20 Performing Binary Search on Java float Array Example
- 21 Performing Binary Search on Java int Array Example
- 22 Performing Binary Search on Java long Array Example
- 23 Performing Binary Search on Java short Array
- 24 Quick Sort Implementation with median-of-three partitioning and cutoff for small arrays
- 25 Quick sort with median-of-three partitioning
- 26 Recursive Binary Search Implementation in Java
- 27 Selection sort
- 28 Shell sort
- 29 Simple Sort Demo
- 30 Simple version of quick sort
- 31 Sort an array of objects
- 32 Sort a String array
- 33 Sorting an array of Strings
- 34 Sort items of an array
- 35 Sort Numbers
- 36 Sort string array with Collator
- 37 Topological sorting
A binary search implementation.
/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
*
* The contents of this file are subject to the terms of either the GNU
* General Public License Version 2 only ("GPL") or the Common Development
* and Distribution License("CDDL") (collectively, the "License"). You
* may not use this file except in compliance with the License. You can obtain
* a copy of the License at https://glassfish.dev.java.net/public/CDDL+GPL.html
* or glassfish/bootstrap/legal/LICENSE.txt. See the License for the specific
* language governing permissions and limitations under the License.
*
* When distributing the software, include this License Header Notice in each
* file and include the License file at glassfish/bootstrap/legal/LICENSE.txt.
* Sun designates this particular file as subject to the "Classpath" exception
* as provided by Sun in the GPL Version 2 section of the License file that
* accompanied this code. If applicable, add the following below the License
* Header, with the fields enclosed by brackets [] replaced by your own
* identifying information: "Portions Copyrighted [year]
* [name of copyright owner]"
*
* Contributor(s):
*
* If you wish your version of this file to be governed by only the CDDL or
* only the GPL Version 2, indicate your decision by adding "[Contributor]
* elects to include this software in this distribution under the [CDDL or GPL
* Version 2] license." If you don"t indicate a single choice of license, a
* recipient has the option to distribute your version of this file under
* either the CDDL, the GPL Version 2 or to extend the choice of license to
* its licensees as provided above. However, if you add GPL Version 2 code
* and therefore, elected the GPL Version 2 license, then the option applies
* only if the new code is made subject to such option by the copyright
* holder.
*/
// ----------------------------------------------------------------------------
/**
* A binary search implementation.
*/
public class BinarySearch {
public int find(final int[] data, final int key) {
int low = 0, high = data.length - 1;
while (low <= high) {
final int i = (low + high) >> 1;
final int v = data[i];
if (v == key)
return i; // this line does not get covered unless there is a match
else if (v < key)
low = i + 1;
else
// v > key
high = i - 1;
}
return -1;
}
}
Animation for quick sort
import java.awt.BorderLayout;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Rectangle2D;
import java.util.Arrays;
import java.util.Collections;
import java.util.ruparator;
import javax.swing.JComponent;
import javax.swing.JFrame;
public class AnimationTester {
public static void main(String[] args) {
JFrame frame = new JFrame();
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
ArrayComponent panel = new ArrayComponent();
frame.add(panel, BorderLayout.CENTER);
frame.setSize(800, 300);
frame.setVisible(true);
Double[] values = new Double[100];
for (int i = 0; i < values.length; i++)
values[i] = Math.random() * panel.getHeight();
final Sorter sorter = new Sorter(values, panel);
Thread sorterThread = new Thread(sorter);
sorterThread.start();
}
}
class ArrayComponent extends JComponent {
private Double marked1;
private Double marked2;
private Double[] values;
public synchronized void paintComponent(Graphics g) {
if (values == null)
return;
Graphics2D g2 = (Graphics2D) g;
int width = getWidth() / values.length;
for (int i = 0; i < values.length; i++) {
Double v = values[i];
Rectangle2D bar = new Rectangle2D.Double(width * i, 0, width, v);
if (v == marked1 || v == marked2)
g2.fill(bar);
else
g2.draw(bar);
}
}
public synchronized void setValues(Double[] values, Double marked1, Double marked2) {
this.values = (Double[]) values.clone();
this.marked1 = marked1;
this.marked2 = marked2;
repaint();
}
}
class Sorter implements Runnable {
private Double[] values;
private ArrayComponent panel;
public Sorter(Double[] values, ArrayComponent panel) {
this.values = values;
this.panel = panel;
}
public void run() {
Comparator<Double> comp = new Comparator<Double>() {
public int compare(Double d1, Double d2) {
try {
Thread.sleep(100);
} catch (Exception exception) {
System.out.println(exception);
}
panel.setValues(values, d1, d2);
return d1.rupareTo(d2);
}
};
Collections.sort(Arrays.asList(values), comp);
panel.setValues(values, null, null);
}
}
A quick sort demonstration algorithm
/*
* The remainder of this file is borrowed from: @(#)QSortAlgorithm.java 1.3 29
* Feb 1996 James Gosling
*
* Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved.
*
* Permission to use, copy, modify, and distribute this software and its
* documentation for NON-COMMERCIAL or COMMERCIAL purposes and without fee is
* hereby granted. Please refer to the file
* http://www.javasoft.ru/copy_trademarks.html for further important copyright
* and trademark information and to http://www.javasoft.ru/licensing.html for
* further important licensing information for the Java (tm) Technology.
*
* SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
* SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE IMPLIED
* WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR
* NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY
* LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
* DERIVATIVES.
*
* THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
* CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE PERFORMANCE,
* SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT NAVIGATION OR
* COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE SUPPORT MACHINES, OR
* WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE SOFTWARE COULD LEAD DIRECTLY TO
* DEATH, PERSONAL INJURY, OR SEVERE PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH
* RISK ACTIVITIES"). SUN SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY
* OF FITNESS FOR HIGH RISK ACTIVITIES.
*/
/**
* A quick sort demonstration algorithm SortAlgorithm.java
*
* @author James Gosling
* @author Kevin A. Smith
* @version @(#)QSortAlgorithm.java 1.3, 29 Feb 1996
*/
/**
* This is a generic version of C.A.R Hoare"s Quick Sort algorithm. This will
* handle arrays that are already sorted, and arrays with duplicate keys. <BR>
*
* If you think of a one dimensional array as going from the lowest index on the
* left to the highest index on the right then the parameters to this function
* are lowest index or left and highest index or right. The first time you call
* this function it will be with the parameters 0, a.length - 1.
*
* @param a
* a string array
* @param lo0
* left boundary of array partition
* @param hi0
* right boundary of array partition
*/
public class Sort {
void QuickSort(String a[], int lo0, int hi0) {
int lo = lo0;
int hi = hi0;
String mid;
if (hi0 > lo0) {
/*
* Arbitrarily establishing partition element as the midpoint of the
* array.
*/
mid = a[(lo0 + hi0) / 2];
// loop through the array until indices cross
while (lo <= hi) {
/*
* find the first element that is greater than or equal to the
* partition element starting from the left Index.
*/
while ((lo < hi0) && (a[lo].rupareTo(mid) < 0))
++lo;
/*
* find an element that is smaller than or equal to the
* partition element starting from the right Index.
*/
while ((hi > lo0) && (a[hi].rupareTo(mid) > 0))
--hi;
// if the indexes have not crossed, swap
if (lo <= hi) {
String t = a[hi];
a[hi] = a[lo];
a[lo] = t;
++lo;
--hi;
}
}
/*
* If the right index has not reached the left side of array must
* now sort the left partition.
*/
if (lo0 < hi)
QuickSort(a, lo0, hi);
/*
* If the left index has not reached the right side of array must
* now sort the right partition.
*/
if (lo < hi0)
QuickSort(a, lo, hi0);
}
}
}
A simple applet class to demonstrate a sort algorithm
/* From http://java.sun.ru/docs/books/tutorial/index.html */
/*
* @(#)SortItem.java 1.17f 95/04/10 James Gosling
*
* Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.
*
* Permission to use, copy, modify, and distribute this software
* and its documentation for NON-COMMERCIAL purposes and without
* fee is hereby granted provided that this copyright notice
* appears in all copies. Please refer to the file "copyright.html"
* for further important copyright and licensing information.
*
* SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
* THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
* TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
* PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
*/
import java.awt.Color;
import java.awt.Graphics;
/**
* A simple applet class to demonstrate a sort algorithm. You can specify a
* sorting algorithm using the "alg" attribyte. When you click on the applet, a
* thread is forked which animates the sorting algorithm.
*
* @author James Gosling
* @version 1.17f, 10 Apr 1995
*/
public class SortItem extends java.applet.Applet implements Runnable {
/**
* The thread that is sorting (or null).
*/
private Thread kicker;
/**
* The array that is being sorted.
*/
int[] arr;
/**
* The high water mark.
*/
int h1 = -1;
/**
* The low water mark.
*/
int h2 = -1;
/**
* The name of the algorithm.
*/
String algName;
/**
* The sorting algorithm (or null).
*/
SortAlgorithm algorithm;
/**
* Fill the array with random numbers from 0..n-1.
*/
void scramble() {
int[] a = new int[size().height / 2];
double f = size().width / (double) a.length;
for (int i = a.length; --i >= 0;) {
a[i] = (int) (i * f);
}
for (int i = a.length; --i >= 0;) {
int j = (int) (i * Math.random());
int t = a[i];
a[i] = a[j];
a[j] = t;
}
arr = a;
}
/**
* Pause a while.
*
* @see SortAlgorithm
*/
void pause() {
pause(-1, -1);
}
/**
* Pause a while, and draw the high water mark.
*
* @see SortAlgorithm
*/
void pause(int H1) {
pause(H1, -1);
}
/**
* Pause a while, and draw the low&high water marks.
*
* @see SortAlgorithm
*/
void pause(int H1, int H2) {
h1 = H1;
h2 = H2;
if (kicker != null) {
repaint();
}
try {
Thread.sleep(20);
} catch (InterruptedException e) {
}
}
/**
* Initialize the applet.
*/
public void init() {
String at = getParameter("alg");
if (at == null) {
at = "BubbleSort";
}
algName = at + "Algorithm";
scramble();
setBackground(Color.white);
resize(100, 100);
}
/**
* Paint the array of numbers as a list of horizontal lines of varying
* lenghts.
*/
public void paint(Graphics g) {
int[] a = arr;
int y = size().height - 1;
// Erase old lines
g.setColor(Color.lightGray);
for (int i = a.length; --i >= 0; y -= 2) {
g.drawLine(arr[i], y, size().width, y);
}
// Draw new lines
g.setColor(Color.black);
y = size().height - 1;
for (int i = a.length; --i >= 0; y -= 2) {
g.drawLine(0, y, arr[i], y);
}
if (h1 >= 0) {
g.setColor(Color.red);
y = h1 * 2 + 1;
g.drawLine(0, y, size().width, y);
}
if (h2 >= 0) {
g.setColor(Color.blue);
y = h2 * 2 + 1;
g.drawLine(0, y, size().width, y);
}
}
/**
* Update without erasing the background.
*/
public void update(Graphics g) {
paint(g);
}
/**
* Run the sorting algorithm. This method is called by class Thread once the
* sorting algorithm is started.
*
* @see java.lang.Thread#run
* @see SortItem#mouseUp
*/
public void run() {
try {
if (algorithm == null) {
algorithm = (SortAlgorithm) Class.forName(algName)
.newInstance();
algorithm.setParent(this);
}
algorithm.init();
algorithm.sort(arr);
} catch (Exception e) {
}
}
/**
* Stop the applet. Kill any sorting algorithm that is still sorting.
*/
public synchronized void stop() {
if (kicker != null) {
try {
kicker.stop();
} catch (IllegalThreadStateException e) {
// ignore this exception
}
kicker = null;
}
if (algorithm != null) {
try {
algorithm.stop();
} catch (IllegalThreadStateException e) {
// ignore this exception
}
}
}
/**
* For a Thread to actually do the sorting. This routine makes sure we do
* not simultaneously start several sorts if the user repeatedly clicks on
* the sort item. It needs to be synchronoized with the stop() method
* because they both manipulate the common kicker variable.
*/
private synchronized void startSort() {
if (kicker == null || !kicker.isAlive()) {
scramble();
repaint();
kicker = new Thread(this);
kicker.start();
}
}
/**
* The user clicked in the applet. Start the clock!
*/
public boolean mouseUp(java.awt.Event evt, int x, int y) {
startSort();
return true;
}
}
/*
* @(#)BidirectionalBubbleSortAlgorithm.java 1.6f 95/01/31 James Gosling
*
* Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.
*
* Permission to use, copy, modify, and distribute this software and its
* documentation for NON-COMMERCIAL purposes and without fee is hereby granted
* provided that this copyright notice appears in all copies. Please refer to
* the file "copyright.html" for further important copyright and licensing
* information.
*
* SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
* SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE IMPLIED
* WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR
* NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY
* LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
* DERIVATIVES.
*/
/**
* A bi-directional bubble sort demonstration algorithm SortAlgorithm.java, Thu
* Oct 27 10:32:35 1994
*
* @author James Gosling
* @version 1.6f, 31 Jan 1995
*/
class BidirectionalBubbleSortAlgorithm extends SortAlgorithm {
void sort(int[] a) throws Exception {
int j;
int limit = a.length;
int st = -1;
while (st < limit) {
boolean flipped = false;
st++;
limit--;
for (j = st; j < limit; j++) {
if (stopRequested) {
return;
}
if (a[j] > a[j + 1]) {
int T = a[j];
a[j] = a[j + 1];
a[j + 1] = T;
flipped = true;
pause(st, limit);
}
}
if (!flipped) {
return;
}
for (j = limit; --j >= st;) {
if (stopRequested) {
return;
}
if (a[j] > a[j + 1]) {
int T = a[j];
a[j] = a[j + 1];
a[j + 1] = T;
flipped = true;
pause(st, limit);
}
}
if (!flipped) {
return;
}
}
pause(st, limit);
}
}
/*
* @(#)SortAlgorithm.java 1.6f 95/01/31 James Gosling
*
* Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.
*
* Permission to use, copy, modify, and distribute this software and its
* documentation for NON-COMMERCIAL purposes and without fee is hereby granted
* provided that this copyright notice appears in all copies. Please refer to
* the file "copyright.html" for further important copyright and licensing
* information.
*
* SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
* SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE IMPLIED
* WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR
* NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY
* LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
* DERIVATIVES.
*/
/**
* A generic sort demonstration algorithm SortAlgorithm.java, Thu Oct 27
* 10:32:35 1994
*
* @author James Gosling
* @version 1.6f, 31 Jan 1995
*/
class SortAlgorithm {
/**
* The sort item.
*/
private SortItem parent;
/**
* When true stop sorting.
*/
protected boolean stopRequested = false;
/**
* Set the parent.
*/
public void setParent(SortItem p) {
parent = p;
}
/**
* Pause for a while.
*/
protected void pause() throws Exception {
if (stopRequested) {
throw new Exception("Sort Algorithm");
}
parent.pause(parent.h1, parent.h2);
}
/**
* Pause for a while and mark item 1.
*/
protected void pause(int H1) throws Exception {
if (stopRequested) {
throw new Exception("Sort Algorithm");
}
parent.pause(H1, parent.h2);
}
/**
* Pause for a while and mark item 1 & 2.
*/
protected void pause(int H1, int H2) throws Exception {
if (stopRequested) {
throw new Exception("Sort Algorithm");
}
parent.pause(H1, H2);
}
/**
* Stop sorting.
*/
public void stop() {
stopRequested = true;
}
/**
* Initialize
*/
public void init() {
stopRequested = false;
}
/**
* This method will be called to sort an array of integers.
*/
void sort(int[] a) throws Exception {
}
}
/*
* @(#)QSortAlgorithm.java 1.6f 95/01/31 James Gosling
*
* Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.
*
* Permission to use, copy, modify, and distribute this software
* and its documentation for NON-COMMERCIAL purposes and without
* fee is hereby granted provided that this copyright notice
* appears in all copies. Please refer to the file "copyright.html"
* for further important copyright and licensing information.
*
* SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
* THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
* TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
* PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
*/
/**
* A quick sort demonstration algorithm
* SortAlgorithm.java, Thu Oct 27 10:32:35 1994
*
* @author James Gosling
* @version 1.6f, 31 Jan 1995
*/
class QSortAlgorithm extends SortAlgorithm {
void sort(int[] a, int lo0, int hi0) throws Exception {
int lo = lo0;
int hi = hi0;
pause(lo, hi);
if (lo >= hi) {
return;
}
int mid = a[(lo + hi) / 2];
while (lo < hi) {
while (lo<hi && a[lo] < mid) {
lo++;
}
while (lo<hi && a[hi] > mid) {
hi--;
}
if (lo < hi) {
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
lo++;
hi--;
pause();
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
sort(a, lo0, lo);
sort(a, lo == lo0 ? lo+1 : lo, hi0);
}
void sort(int[] a) throws Exception {
sort(a, 0, a.length-1);
}
}
/*
* @(#)BubbleSortAlgorithm.java 1.6f 95/01/31 James Gosling
*
* Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.
*
* Permission to use, copy, modify, and distribute this software
* and its documentation for NON-COMMERCIAL purposes and without
* fee is hereby granted provided that this copyright notice
* appears in all copies. Please refer to the file "copyright.html"
* for further important copyright and licensing information.
*
* SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
* THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
* TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
* PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
*/
/**
* A bubble sort demonstration algorithm
* SortAlgorithm.java, Thu Oct 27 10:32:35 1994
*
* @author James Gosling
* @version 1.6f, 31 Jan 1995
*/
class BubbleSortAlgorithm extends SortAlgorithm {
void sort(int[] a) throws Exception {
for (int i = a.length; --i>=0; )
for (int j = 0; j<i; j++) {
if (stopRequested) {
return;
}
if (a[j] > a[j+1]) {
int T = a[j];
a[j] = a[j+1];
a[j+1] = T;
}
pause(i,j);
}
}
}
Binary Search
public class BinarySearchArray {
private long[] a;
private int nElems;
public BinarySearchArray(int max) {
a = new long[max]; // create array
nElems = 0;
}
public int size() {
return nElems;
}
public int find(long searchKey) {
return recFind(searchKey, 0, nElems - 1);
}
private int recFind(long searchKey, int lowerBound, int upperBound) {
int curIn;
curIn = (lowerBound + upperBound) / 2;
if (a[curIn] == searchKey)
return curIn; // found it
else if (lowerBound > upperBound)
return nElems; // can"t find it
else // divide range
{
if (a[curIn] < searchKey) // in upper half
return recFind(searchKey, curIn + 1, upperBound);
else
// in lower half
return recFind(searchKey, lowerBound, curIn - 1);
}
}
public void insert(long value) {
int j;
for (j = 0; j < nElems; j++)
// find where it goes
if (a[j] > value) // (linear search)
break;
for (int k = nElems; k > j; k--)
// move bigger ones up
a[k] = a[k - 1];
a[j] = value; // insert it
nElems++; // increment size
}
public void display() {
for (int j = 0; j < nElems; j++)
System.out.print(a[j] + " ");
System.out.println("");
}
public static void main(String[] args) {
int maxSize = 100;
BinarySearchArray arr = new BinarySearchArray(maxSize);
arr.insert(12);
arr.insert(20);
arr.insert(35);
arr.insert(426);
arr.insert(54);
arr.insert(69);
arr.insert(744);
arr.insert(87);
arr.insert(895);
arr.insert(89);
arr.insert(8);
arr.insert(208);
arr.insert(4);
arr.insert(617);
arr.insert(83);
arr.insert(96);
arr.display(); // display array
int searchKey = 27; // search for item
if (arr.find(searchKey) != arr.size())
System.out.println("Found " + searchKey);
else
System.out.println("Can"t find " + searchKey);
}
}
Binary search routines
/*
* Copyright (c) 1998-2002 Carnegie Mellon University. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS"" AND
* ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
* NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*/
/**
* Binary search routines.
*/
public abstract class BinarySearch {
/**
* Search a sorted array of integers.
* @param array Array of integers
* @param offset Starting offset of subarray to search
* @param length Length of subarray to search
* @param x Value to search for
* @return largest index i in subarray (offset <= i <= offset+length)
* such that all elements below i in the subarray are strictly less
* than x. If x is found in the subarray, then array[i] == x (and i is
* the first occurence of x in the subarray). If x is not found,
* then array[i] is where x should be inserted in the sort order.
*/
public static int search (int[] array, int offset, int length, int x) {
// handle 0-length subarray case right away
if (length <= 0)
return offset;
int low = offset;
int high = offset+length-1;
// since length > 0, array[low] and array[high] are valid indices
if (x <= array[low])
return low;
if (x > array[high])
return high+1;
while (low+1 < high) {
// loop invariant: array[low] < x <= array[high],
// offset <= low < high < offset+length
int mid = (low + high)/2;
if (x <= array[mid])
high = mid;
else
low = mid;
}
// now we have array[low] < x <= array[high]
// && (low+1 == high || low == high)
// implies low+1 == high
//debug.assertion (low+1 == high);
return high;
}
}
Bubble sort
public class BubbleSort {
private long[] a;
private int nElems;
public BubbleSort(int max) {
a = new long[max];
nElems = 0;
}
// put element into array
public void insert(long value) {
a[nElems] = value;
nElems++;
}
// displays array contents
public void display() {
for (int j = 0; j < nElems; j++)
System.out.print(a[j] + " ");
System.out.println("");
}
public void bubbleSort() {
int out, in;
for (out = nElems - 1; out > 1; out--)
// outer loop (backward)
for (in = 0; in < out; in++)
// inner loop (forward)
if (a[in] > a[in + 1]) // out of order?
swap(in, in + 1); // swap them
}
private void swap(int one, int two) {
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
public static void main(String[] args) {
int maxSize = 100; // array size
BubbleSort arr; // reference to array
arr = new BubbleSort(maxSize);
arr.insert(77); // insert 10 items
arr.insert(66);
arr.insert(44);
arr.insert(34);
arr.insert(22);
arr.insert(88);
arr.insert(12);
arr.insert(00);
arr.insert(55);
arr.insert(33);
arr.display();
arr.bubbleSort();
arr.display();
}
}
Combine Quick Sort Insertion Sort
public class CombineQuickSortInsertionSort {
private long[] data;
private int len;
public CombineQuickSortInsertionSort(int max) {
data = new long[max];
len = 0;
}
public void insert(long value) {
data[len] = value;
len++;
}
public void display() {
System.out.print("Data:");
for (int j = 0; j < len; j++)
System.out.print(data[j] + " ");
System.out.println("");
}
public void quickSort() {
recQuickSort(0, len - 1);
}
public void recQuickSort(int left, int right) {
int size = right - left + 1;
if (size < 10) // insertion sort if small
insertionSort(left, right);
else // quicksort if large
{
long median = medianOf3(left, right);
int partition = partitionIt(left, right, median);
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
public long medianOf3(int left, int right) {
int center = (left + right) / 2;
// order left & center
if (data[left] > data[center])
swap(left, center);
// order left & right
if (data[left] > data[right])
swap(left, right);
// order center & right
if (data[center] > data[right])
swap(center, right);
swap(center, right - 1);
return data[right - 1];
}
public void swap(int d1, int d2) {
long temp = data[d1];
data[d1] = data[d2];
data[d2] = temp;
}
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left; // right of first elem
int rightPtr = right - 1; // left of pivot
while (true) {
//find bigger
while (data[++leftPtr] < pivot)
;
//find smaller
while (data[--rightPtr] > pivot)
;
if (leftPtr >= rightPtr) // if pointers cross, partition done
break;
else
swap(leftPtr, rightPtr);
}
swap(leftPtr, right - 1); // restore pivot
return leftPtr; // return pivot location
}
public void insertionSort(int left, int right) {
int in, out;
// sorted on left of out
for (out = left + 1; out <= right; out++) {
long temp = data[out]; // remove marked item
in = out; // start shifts at out
// until one is smaller,
while (in > left && data[in - 1] >= temp) {
data[in] = data[in - 1]; // shift item to right
--in; // go left one position
}
data[in] = temp; // insert marked item
}
}
public static void main(String[] args) {
int maxSize = 16;
CombineQuickSortInsertionSort arr = new CombineQuickSortInsertionSort(maxSize);
for (int j = 0; j < maxSize; j++)
{
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
arr.display();
arr.quickSort();
arr.display();
}
}
Fast Merge Sort
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.util.ruparator;
/**
* Faster merge sort. When original JDK routine runs 5s for sorting 1 million
* objects this one runs for 3.5s.
* <p>
* reference: Arrays.mergeSort (private method).
*/
public class FastMergeSort {
@SuppressWarnings( { "unchecked" })
private static void mergeSort(Object src[], Object dest[], int low, int high, int off,
Comparator c) {
int length = high - low;
// use insertion sort on smallest arrays
if (length < 7) {
for (int i = low; i < high; i++) {
for (int j = i; j > low && c.rupare(dest[j - 1], dest[j]) > 0; j--) {
Object temp = dest[j];
dest[j] = dest[j - 1];
dest[j - 1] = temp;
}
}
return;
}
// recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >> 1;
mergeSort(dest, src, low, mid, -off, c);
mergeSort(dest, src, mid, high, -off, c);
// is list already sorted?
if (c.rupare(src[mid - 1], src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
// merge sorted halves from src into dest
for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && c.rupare(src[p], src[q]) <= 0) {
dest[i] = src[p++];
} else {
dest[i] = src[q++];
}
}
}
public void sort(Object[] a, Comparator c) {
Object aux[] = a.clone();
mergeSort(aux, a, 0, a.length, 0, c);
}
public void sort(Comparable[] a) {
Object aux[] = a.clone();
mergeSort(aux, a, 0, a.length, 0, ComparableComparator.INSTANCE);
}
// ---------------------------------------------------------------- static
public static void doSort(Object[] a, Comparator c) {
Object aux[] = a.clone();
mergeSort(aux, a, 0, a.length, 0, c);
}
public static void doSort(Comparable[] a) {
Object aux[] = a.clone();
mergeSort(aux, a, 0, a.length, 0, ComparableComparator.INSTANCE);
}
}
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
/**
* Comparator that adapts <code>Comparables</code> to the
* <code>Comparator</code> interface.
*/
class ComparableComparator<T extends Comparable<T>> implements Comparator<T> {
/**
* Cached instance.
*/
public static final ComparableComparator INSTANCE = new ComparableComparator();
public int compare(T o1, T o2) {
return o1.rupareTo(o2);
}
}
FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows, using the comparator.
/* Copyright (c) 1995-2000, The Hypersonic SQL Group.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the Hypersonic SQL Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* This software consists of voluntary contributions made by many individuals
* on behalf of the Hypersonic SQL Group.
*
*
* For work added by the HSQL Development Group:
*
* Copyright (c) 2001-2009, The HSQL Development Group
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the HSQL Development Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/**
* FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows,
* using the comparator.
*
* Modified from the original method in Hypersonic with the addition of the
* comparator. (fredt@users)
*
* @author Thomas Mueller (Hypersonic SQL Group)
* @version 1.7.2
* @since 1.7.2
*/
public class Sort {
public static final void sort(Object[] w, ObjectComparator comparator, int l, int r) {
int i;
int j;
Object p;
if (l > r) {
return;
}
while (r - l > 10) {
i = (r + l) >>> 1;
if (comparator.rupare(w[l], w[r]) > 0) {
swap(w, l, r);
}
if (comparator.rupare(w[i], w[l]) < 0) {
swap(w, l, i);
} else if (comparator.rupare(w[i], w[r]) > 0) {
swap(w, i, r);
}
j = r - 1;
swap(w, i, j);
p = w[j];
i = l;
while (true) {
while (comparator.rupare(w[++i], p) < 0) {
;
}
while (comparator.rupare(w[--j], p) > 0) {
;
}
if (i >= j) {
break;
}
swap(w, i, j);
}
swap(w, i, r - 1);
sort(w, comparator, l, i - 1);
l = i + 1;
}
for (i = l + 1; i <= r; i++) {
Object t = w[i];
for (j = i - 1; j >= l && comparator.rupare(w[j], t) > 0; j--) {
w[j + 1] = w[j];
}
w[j + 1] = t;
}
}
/**
* Swaps the a"th and b"th elements of the specified Row array.
*/
private static void swap(Object[] w, int a, int b) {
Object t = w[a];
w[a] = w[b];
w[b] = t;
}
}
interface ObjectComparator {
int compare(Object a, Object b);
}
Fast Quick Sort
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.util.ruparator;
/**
* Maybe the fastest implementation of famous Quick-Sort
* algorithm. It is even faster than Denisa Ahrensa implementation that
* performs 7.5s for sorting million objects, this implementation
* sorts for 6.8s. However, {@link FastMergeSort} is much faster.
*/
public class FastQuickSort {
@SuppressWarnings({"unchecked"})
public static void qsort(Object[] c, Comparator comparator) {
int i, j, left = 0, right = c.length - 1, stack_pointer = -1;
int[] stack = new int[128];
Object swap, temp;
while (true) {
if (right - left <= 7) {
for (j = left + 1; j <= right; j++) {
swap = c[j];
i = j - 1;
while (i >= left && comparator.rupare(c[i], swap) > 0) {
c[i + 1] = c[i--];
}
c[i + 1] = swap;
}
if (stack_pointer == -1) {
break;
}
right = stack[stack_pointer--];
left = stack[stack_pointer--];
} else {
int median = (left + right) >> 1;
i = left + 1;
j = right;
swap = c[median]; c[median] = c[i]; c[i] = swap;
if (comparator.rupare(c[left], c[right]) > 0) {
swap = c[left]; c[left] = c[right]; c[right] = swap;
}
if (comparator.rupare(c[i], c[right]) > 0) {
swap = c[i]; c[i] = c[right]; c[right] = swap;
}
if (comparator.rupare(c[left], c[i]) > 0) {
swap = c[left]; c[left] = c[i]; c[i] = swap;
}
temp = c[i];
while (true) {
//noinspection ControlFlowStatementWithoutBraces,StatementWithEmptyBody
while (comparator.rupare(c[++i], temp) < 0);
//noinspection ControlFlowStatementWithoutBraces,StatementWithEmptyBody
while (comparator.rupare(c[--j], temp) > 0);
if (j < i) {
break;
}
swap = c[i]; c[i] = c[j]; c[j] = swap;
}
c[left + 1] = c[j];
c[j] = temp;
if (right - i + 1 >= j - left) {
stack[++stack_pointer] = i;
stack[++stack_pointer] = right;
right = j - 1;
} else {
stack[++stack_pointer] = left;
stack[++stack_pointer] = j - 1;
left = i;
}
}
}
}
public void sort(Object a[], Comparator comparator) {
qsort(a, comparator);
}
public void sort(Comparable a[]) {
qsort(a, new ComparableComparator());
}
// ---------------------------------------------------------------- static
public static void doSort(Object a[], Comparator comparator) {
qsort(a, comparator);
}
public static void doSort(Comparable a[]) {
qsort(a, ComparableComparator.INSTANCE);
}
}
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
/**
* Comparator that adapts <code>Comparables</code> to the
* <code>Comparator</code> interface.
*/
class ComparableComparator<T extends Comparable<T>> implements Comparator<T> {
/**
* Cached instance.
*/
public static final ComparableComparator INSTANCE = new ComparableComparator();
public int compare(T o1, T o2) {
return o1.rupareTo(o2);
}
}
Heap sort
import java.io.IOException;
class MyNode {
private int iData;
public MyNode(int key) {
iData = key;
}
public int getKey() {
return iData;
}
}
public class Heap {
private MyNode[] heapArray;
private int maxSize;
private int currentSize; // number of items in array
public Heap(int mx) {
maxSize = mx;
currentSize = 0;
heapArray = new MyNode[maxSize];
}
public MyNode remove()
{
MyNode root = heapArray[0];
heapArray[0] = heapArray[--currentSize];
trickleDown(0);
return root;
}
public void trickleDown(int index) {
int largerChild;
MyNode top = heapArray[index];
while (index < currentSize / 2)
{
int leftChild = 2 * index + 1;
int rightChild = leftChild + 1;
// find larger child
if (rightChild < currentSize
&&
heapArray[leftChild].getKey() < heapArray[rightChild]
.getKey())
largerChild = rightChild;
else
largerChild = leftChild;
if (top.getKey() >= heapArray[largerChild].getKey())
break;
heapArray[index] = heapArray[largerChild];
index = largerChild;
}
heapArray[index] = top;
}
public void displayHeap() {
int nBlanks = 32;
int itemsPerRow = 1;
int column = 0;
int currentIndex = 0;
while (currentSize > 0)
{
if (column == 0)
for (int k = 0; k < nBlanks; k++)
System.out.print(" ");
System.out.print(heapArray[currentIndex].getKey());
if (++currentIndex == currentSize) // done?
break;
if (++column == itemsPerRow) // end of row?
{
nBlanks /= 2;
itemsPerRow *= 2;
column = 0;
System.out.println();
} else
for (int k = 0; k < nBlanks * 2 - 2; k++)
System.out.print(" "); // interim blanks
}
}
public void displayArray() {
for (int j = 0; j < maxSize; j++)
System.out.print(heapArray[j].getKey() + " ");
System.out.println("");
}
public void insertAt(int index, MyNode newNode) {
heapArray[index] = newNode;
}
public void incrementSize() {
currentSize++;
}
public static void main(String[] args) throws IOException {
int size, i;
size = 100;
Heap theHeap = new Heap(size);
for (i = 0; i < size; i++) {
int random = (int) (java.lang.Math.random() * 100);
MyNode newNode = new MyNode(random);
theHeap.insertAt(i, newNode);
theHeap.incrementSize();
}
System.out.print("Random: ");
theHeap.displayArray();
for (i = size / 2 - 1; i >= 0; i--)
theHeap.trickleDown(i);
System.out.print("Heap: ");
theHeap.displayArray();
theHeap.displayHeap();
for (i = size - 1; i >= 0; i--) {
MyNode biggestNode = theHeap.remove();
theHeap.insertAt(i, biggestNode);
}
System.out.print("Sorted: ");
theHeap.displayArray();
}
}
Insert sort
public class InsertSort {
private long[] number;
private int nElems;
public InsertSort(int max) {
number = new long[max];
nElems = 0;
}
public void insert(long value) {
number[nElems] = value;
nElems++;
}
public void display() {
for (int j = 0; j < nElems; j++)
System.out.print(number[j] + " ");
System.out.println("");
}
public void insertionSort() {
int in, out;
// out is dividing line
for (out = 1; out < nElems; out++) {
long temp = number[out]; // remove marked item
in = out; // start shifts at out
while (in > 0 && number[in - 1] >= temp) // until one is smaller,
{
number[in] = number[in - 1]; // shift item to right
--in; // go left one position
}
number[in] = temp; // insert marked item
}
}
public static void main(String[] args) {
int maxSize = 100; // array size
InsertSort arr; // reference to array
arr = new InsertSort(maxSize); // create the array
arr.insert(47);
arr.insert(99);
arr.insert(44);
arr.insert(35);
arr.insert(22);
arr.insert(88);
arr.insert(41);
arr.insert(00);
arr.insert(16);
arr.insert(33);
arr.display();
arr.insertionSort();
arr.display();
}
}
Insert Sort for objects
public class ObjectInsertSort {
private Person[] a;
private int nElems;
public ObjectInsertSort(int max) {
a = new Person[max];
nElems = 0;
}
// put person into array
public void insert(String last, String first, int age) {
a[nElems] = new Person(last, first, age);
nElems++;
}
public void display() {
for (int j = 0; j < nElems; j++)
a[j].displayPerson();
}
public void insertionSort() {
int in, out;
for (out = 1; out < nElems; out++) {
Person temp = a[out]; // out is dividing line
in = out; // start shifting at out
while (in > 0 && // until smaller one found,
a[in - 1].getLast().rupareTo(temp.getLast()) > 0) {
a[in] = a[in - 1]; // shift item to the right
--in; // go left one position
}
a[in] = temp; // insert marked item
}
}
public static void main(String[] args) {
int maxSize = 100; // array size
ObjectInsertSort arr;
arr = new ObjectInsertSort(maxSize); // create the array
arr.insert("Jo", "Yin", 24);
arr.insert("Pengzhou", "Yin", 59);
arr.insert("James", "Chen", 37);
arr.insert("Chirs", "Paul", 37);
arr.insert("Rob", "Tom", 43);
arr.insert("Carlo", "Sato", 21);
arr.insert("Al", "Henry", 29);
arr.insert("Nancy", "Jose", 72);
arr.insert("Vang", "Minh", 22);
System.out.println("Before sorting:");
arr.display(); // display items
arr.insertionSort(); // insertion-sort them
System.out.println("After sorting:");
arr.display(); // display them again
}
}
class Person {
private String lastName;
private String firstName;
private int age;
public Person(String last, String first, int a) {
lastName = last;
firstName = first;
age = a;
}
public void displayPerson() {
System.out.print(" Last name: " + lastName);
System.out.print(", First name: " + firstName);
System.out.println(", Age: " + age);
}
public String getLast() {
return lastName;
}
}
Linear search
public class LinearSearch
{
public int find (final int [] data, final int key)
{
for (int i = 0; i < data.length; ++ i)
{
if (data [i] > key)
return -1;
else if (data [i] == key)
return i;
}
return -1;
}
}
Merge sort
public class MergeSortArray {
private long[] theArray;
private int nElems;
public MergeSortArray(int max) {
theArray = new long[max];
nElems = 0;
}
public void insert(long value) {
theArray[nElems] = value; // insert it
nElems++; // increment size
}
public void display() {
for (int j = 0; j < nElems; j++)
System.out.print(theArray[j] + " ");
System.out.println("");
}
public void mergeSort() {
long[] workSpace = new long[nElems];
recMergeSort(workSpace, 0, nElems - 1);
}
private void recMergeSort(long[] workSpace, int lowerBound, int upperBound) {
if (lowerBound == upperBound) // if range is 1,
return; // no use sorting
else { // find midpoint
int mid = (lowerBound + upperBound) / 2;
// sort low half
recMergeSort(workSpace, lowerBound, mid);
// sort high half
recMergeSort(workSpace, mid + 1, upperBound);
// merge them
merge(workSpace, lowerBound, mid + 1, upperBound);
}
}
private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound) {
int j = 0; // workspace index
int lowerBound = lowPtr;
int mid = highPtr - 1;
int n = upperBound - lowerBound + 1; // # of items
while (lowPtr <= mid && highPtr <= upperBound)
if (theArray[lowPtr] < theArray[highPtr])
workSpace[j++] = theArray[lowPtr++];
else
workSpace[j++] = theArray[highPtr++];
while (lowPtr <= mid)
workSpace[j++] = theArray[lowPtr++];
while (highPtr <= upperBound)
workSpace[j++] = theArray[highPtr++];
for (j = 0; j < n; j++)
theArray[lowerBound + j] = workSpace[j];
}
public static void main(String[] args) {
int maxSize = 100; // array size
MergeSortArray arr = new MergeSortArray(maxSize); // create the array
arr.insert(14);
arr.insert(21);
arr.insert(43);
arr.insert(50);
arr.insert(62);
arr.insert(75);
arr.insert(14);
arr.insert(2);
arr.insert(39);
arr.insert(5);
arr.insert(608);
arr.insert(36);
arr.display();
arr.mergeSort();
arr.display();
}
}
Performing Binary Search on Java byte Array Example
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
byte bArray[] = { 1, 2, 4, 5 };
Arrays.sort(bArray);
byte searchValue = 2;
int intResult = Arrays.binarySearch(bArray, searchValue);
System.out.println("Result of binary search of 2 is : " + intResult);
searchValue = 7;
intResult = Arrays.binarySearch(bArray, searchValue);
System.out.println("Result of binary search of 3 is : " + intResult);
}
}
Performing Binary Search on Java char Array Example
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
char charArray[] = { "a", "b", "d", "e" };
Arrays.sort(charArray);
char searchValue = "b";
System.out.println(Arrays.binarySearch(charArray, searchValue));
searchValue = "z";
System.out.println(Arrays.binarySearch(charArray, searchValue));
}
}
Performing Binary Search on Java double Array Example
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
double doubleArray[] = { 1.3, 2.1, 4.7, 5.3 };
Arrays.sort(doubleArray);
double searchValue = 4.7;
System.out.println(Arrays.binarySearch(doubleArray, searchValue));
searchValue = 3.33;
System.out.println(Arrays.binarySearch(doubleArray, searchValue));
}
}
Performing Binary Search on Java float Array Example
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
float floatArray[] = { 1.2f, 2.1f, 4.7f, 5.3f };
Arrays.sort(floatArray);
float searchValue = 4.7f;
System.out.println(Arrays.binarySearch(floatArray, searchValue));
searchValue = 3.3f;
System.out.println(Arrays.binarySearch(floatArray, searchValue));
}
}
Performing Binary Search on Java int Array Example
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int intArray[] = { 1, 2, 4, 5 };
Arrays.sort(intArray);
int searchValue = 2;
System.out.println(Arrays.binarySearch(intArray, searchValue));
searchValue = 3;
System.out.println(Arrays.binarySearch(intArray, searchValue));
}
}
Performing Binary Search on Java long Array Example
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
long longArray[] = { 1L, 2L, 4L, 5L };
Arrays.sort(longArray);
long searchValue = 2L;
System.out.println(Arrays.binarySearch(longArray, searchValue));
searchValue = 3;
System.out.println(Arrays.binarySearch(longArray, searchValue));
}
}
Performing Binary Search on Java short Array
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
short shortArray[] = { 1, 2, 4, 5 };
Arrays.sort(shortArray);
short searchValue = 2;
System.out.println(Arrays.binarySearch(shortArray, searchValue));
searchValue = 3;
System.out.println(Arrays.binarySearch(shortArray, searchValue));
}
}
Quick Sort Implementation with median-of-three partitioning and cutoff for small arrays
public class Main {
public static void main(String args[]) {
}
public static void quicksort(Comparable[] a) {
quicksort(a, 0, a.length - 1);
}
static void quicksort(Comparable[] a, int low, int high) {
int CUTOFF = 10;
if (low + CUTOFF > high)
insertionSort(a, low, high);
else {
int middle = (low + high) / 2;
if (a[middle].rupareTo(a[low]) < 0)
swapReferences(a, low, middle);
if (a[high].rupareTo(a[low]) < 0)
swapReferences(a, low, high);
if (a[high].rupareTo(a[middle]) < 0)
swapReferences(a, middle, high);
swapReferences(a, middle, high - 1);
Comparable pivot = a[high - 1];
int i, j;
for (i = low, j = high - 1;;) {
while (a[++i].rupareTo(pivot) < 0)
;
while (pivot.rupareTo(a[--j]) < 0)
;
if (i >= j)
break;
swapReferences(a, i, j);
}
swapReferences(a, i, high - 1);
quicksort(a, low, i - 1);
quicksort(a, i + 1, high);
}
}
public static final void swapReferences(Object[] a, int index1, int index2) {
Object tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
private static void insertionSort(Comparable[] a, int low, int high) {
for (int p = low + 1; p <= high; p++) {
Comparable tmp = a[p];
int j;
for (j = p; j > low && tmp.rupareTo(a[j - 1]) < 0; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
}
Quick sort with median-of-three partitioning
public class AnotherQuickSort {
private long[] data;
private int len;
public AnotherQuickSort(int max) {
data = new long[max];
len = 0;
}
public void insert(long value) {
data[len] = value; // insert and increment size
len++;
}
public void display() {
System.out.print("Data:");
for (int j = 0; j < len; j++)
System.out.print(data[j] + " ");
System.out.println("");
}
public void quickSort() {
recQuickSort(0, len - 1);
}
public void recQuickSort(int left, int right) {
int size = right - left + 1;
if (size <= 3) // manual sort if small
manualSort(left, right);
else // quicksort if large
{
long median = medianOf3(left, right);
int partition = partitionIt(left, right, median);
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
public long medianOf3(int left, int right) {
int center = (left + right) / 2;
// order left & center
if (data[left] > data[center])
swap(left, center);
// order left & right
if (data[left] > data[right])
swap(left, right);
// order center & right
if (data[center] > data[right])
swap(center, right);
swap(center, right - 1); // put pivot on right
return data[right - 1]; // return median value
}
public void swap(int dex1, int dex2) {
long temp = data[dex1];
data[dex1] = data[dex2];
data[dex2] = temp;
}
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left; // right of first elem
int rightPtr = right - 1; // left of pivot
while (true) {
// find bigger
while (data[++leftPtr] < pivot)
;
// find smaller
while (data[--rightPtr] > pivot)
;
if (leftPtr >= rightPtr) // if pointers cross, partition done
break;
else
// not crossed, so
swap(leftPtr, rightPtr); // swap elements
}
swap(leftPtr, right - 1); // restore pivot
return leftPtr; // return pivot location
}
public void manualSort(int left, int right) {
int size = right - left + 1;
if (size <= 1)
return; // no sort necessary
if (size == 2) { // 2-sort left and right
if (data[left] > data[right])
swap(left, right);
return;
} else // size is 3
{ // 3-sort left, center, & right
if (data[left] > data[right - 1])
swap(left, right - 1); // left, center
if (data[left] > data[right])
swap(left, right); // left, right
if (data[right - 1] > data[right])
swap(right - 1, right); // center, right
}
}
public static void main(String[] args) {
int maxSize = 16;
AnotherQuickSort arr = new AnotherQuickSort(maxSize);
for (int j = 0; j < maxSize; j++) { // random numbers
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
arr.display();
arr.quickSort();
arr.display();
}
}
Recursive Binary Search Implementation in Java
public class Main {
public static final int NOT_FOUND = -1;
public static int binarySearch(Comparable[] a, Comparable x) {
return binarySearch(a, x, 0, a.length - 1);
}
private static int binarySearch(Comparable[] a, Comparable x, int low, int high) {
if (low > high)
return NOT_FOUND;
int mid = (low + high) / 2;
if (a[mid].rupareTo(x) < 0)
return binarySearch(a, x, mid + 1, high);
else if (a[mid].rupareTo(x) > 0)
return binarySearch(a, x, low, mid - 1);
else
return mid;
}
public static void main(String[] args) {
int SIZE = 8;
Comparable[] a = new Integer[SIZE];
for (int i = 0; i < SIZE; i++)
a[i] = new Integer(i * 2);
for (int i = 0; i < SIZE * 2; i++)
System.out.println("Found " + i + " at " + binarySearch(a, new Integer(i)));
}
}
Selection sort
public class SelectionSort {
private long[] a;
private int nElems;
public SelectionSort(int max) {
a = new long[max];
nElems = 0;
}
public void insert(long value) {
a[nElems] = value;
nElems++;
}
public void display() {
for (int j = 0; j < nElems; j++)
System.out.print(a[j] + " ");
System.out.println("");
}
public void selectionSort() {
int out, in, min;
for (out = 0; out < nElems - 1; out++) // outer loop
{
min = out; // minimum
for (in = out + 1; in < nElems; in++)
// inner loop
if (a[in] < a[min]) // if min greater,
min = in; // a new min
swap(out, min); // swap them
}
}
private void swap(int one, int two) {
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
public static void main(String[] args) {
int maxSize = 100;
SelectionSort arr; // reference to array
arr = new SelectionSort(maxSize); // create the array
arr.insert(17); // insert 10 items
arr.insert(29);
arr.insert(34);
arr.insert(45);
arr.insert(52);
arr.insert(68);
arr.insert(71);
arr.insert(80);
arr.insert(96);
arr.insert(33);
arr.display();
arr.selectionSort();
arr.display();
}
}
Shell sort
public class ShellSort {
private long[] data;
private int len;
public ShellSort(int max) {
data = new long[max];
len = 0;
}
public void insert(long value){
data[len] = value;
len++;
}
public void display() {
System.out.print("Data:");
for (int j = 0; j < len; j++)
System.out.print(data[j] + " ");
System.out.println("");
}
public void shellSort() {
int inner, outer;
long temp;
//find initial value of h
int h = 1;
while (h <= len / 3)
h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)
while (h > 0) // decreasing h, until h=1
{
// h-sort the file
for (outer = h; outer < len; outer++) {
temp = data[outer];
inner = outer;
// one subpass (eg 0, 4, 8)
while (inner > h - 1 && data[inner - h] >= temp) {
data[inner] = data[inner - h];
inner -= h;
}
data[inner] = temp;
}
h = (h - 1) / 3; // decrease h
}
}
public static void main(String[] args) {
int maxSize = 10;
ShellSort arr = new ShellSort(maxSize);
for (int j = 0; j < maxSize; j++) {
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
arr.display();
arr.shellSort();
arr.display();
}
}
Simple Sort Demo
/*
* Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* -Redistribution of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* -Redistribution in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of Sun Microsystems, Inc. or the names of contributors may
* be used to endorse or promote products derived from this software without
* specific prior written permission.
*
* This software is provided "AS IS," without a warranty of any kind. ALL
* EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING
* ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE
* OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN MIDROSYSTEMS, INC. ("SUN")
* AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE
* AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
* DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST
* REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL,
* INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY
* OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE,
* EVEN IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
*
* You acknowledge that this software is not designed, licensed or intended
* for use in the design, construction, operation or maintenance of any
* nuclear facility.
*/
public class SortDemo {
public static void main(String[] args) {
int[] arrayOfInts = { 32, 87, 3, 589, 12, 1076,
2000, 8, 622, 127 };
for (int i = arrayOfInts.length; --i >= 0; ) {
for (int j = 0; j < i; j++) {
if (arrayOfInts[j] > arrayOfInts[j+1]) {
int temp = arrayOfInts[j];
arrayOfInts[j] = arrayOfInts[j+1];
arrayOfInts[j+1] = temp;
}
}
}
for (int i = 0; i < arrayOfInts.length; i++) {
System.out.print(arrayOfInts[i] + " ");
}
System.out.println();
}
}
Simple version of quick sort
public class QuickSortSimpleVersion {
private long[] data;
private int len;
public QuickSortSimpleVersion(int max) {
data = new long[max];
len = 0;
}
public void insert(long value) {
data[len] = value;
len++;
}
public void display() {
System.out.print("Data");
for (int j = 0; j < len; j++)
System.out.print(data[j] + " ");
System.out.println("");
}
public void quickSort() {
recQuickSort(0, len - 1);
}
public void recQuickSort(int left, int right) {
if (right - left <= 0) // if size <= 1 already sorted
return;
else // size is 2 or larger
{
long pivot = data[right]; // rightmost item
// partition range
int partition = partitionData(left, right, pivot);
recQuickSort(left, partition - 1); // sort left side
recQuickSort(partition + 1, right); // sort right side
}
}
public int partitionData(int left, int right, long pivot) {
int leftPtr = left - 1; // left (after ++)
int rightPtr = right; // right-1 (after --)
while (true) { // find bigger item
while (data[++leftPtr] < pivot)
;
// find smaller item
while (rightPtr > 0 && data[--rightPtr] > pivot)
;
if (leftPtr >= rightPtr) // if pointers cross, partition done
break;
else
swap(leftPtr, rightPtr);
}
swap(leftPtr, right); // restore pivot and return pivot location
return leftPtr;
}
public void swap(int d1, int d2) {
long temp = data[d1];
data[d1] = data[d2];
data[d2] = temp;
}
public static void main(String[] args) {
int maxSize = 16; // array size
QuickSortSimpleVersion arr = new QuickSortSimpleVersion(maxSize); // create array
for (int j = 0; j < maxSize; j++) // fill array with random numbers
{
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
arr.display();
arr.quickSort();
arr.display();
}
}
Sort an array of objects
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
String names[] = { "W", "M", "N", "K" };
Arrays.sort(names);
for (int i = 0; i < names.length; i++) {
String name = names[i];
System.out.print("name = " + name + "; ");
}
Person persons[] = new Person[4];
persons[0] = new Person("W");
persons[1] = new Person("M");
persons[2] = new Person("N");
persons[3] = new Person("K");
Arrays.sort(persons);
for (int i = 0; i < persons.length; i++) {
Person person = persons[i];
System.out.println("person = " + person);
}
}
}
class Person implements Comparable {
private String name;
public Person(String name) {
this.name = name;
}
public int compareTo(Object o) {
Person p = (Person) o;
return this.name.rupareTo(p.name);
}
public String toString() {
return name;
}
}
Sort a String array
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.Arrays;
public class Main {
public static void main(String args[]) throws Exception {
String[] words = { "é", "e", "a", "c" };
Writer w = new BufferedWriter(new OutputStreamWriter(System.out, "Cp850"));
for (int i = 0; i < 4; i++) {
w.write(words[i] + " ");
}
Arrays.sort(words);
for (int i = 0; i < 4; i++) {
w.write(words[i] + " ");
}
w.flush();
w.close();
}
}
Sorting an array of Strings
// : c11:StringSorting.java
// Sorting an array of Strings.
// From "Thinking in Java, 3rd ed." (c) Bruce Eckel 2002
// www.BruceEckel.ru. See copyright notice in CopyRight.txt.
import java.util.Arrays;
public class StringSorting {
public static void main(String[] args) {
String[] sa = new String[] { "d", "e", "a", "c", "g" };
System.out.println("Before sorting: " + Arrays.asList(sa));
Arrays.sort(sa);
System.out.println("After sorting: " + Arrays.asList(sa));
}
} ///:~
Sort items of an array
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int numbers[] = { 3, 1, 8, 34, 1, 2, 13, 89, 5, 21, 55 };
System.out.print("Before: ");
for (int i = 0; i < numbers.length; i++) {
int number = numbers[i];
System.out.print(number + "; ");
}
Arrays.sort(numbers);
System.out.print("After: ");
for (int i = 0; i < numbers.length; i++) {
int number = numbers[i];
System.out.print(number + "; ");
}
float money[] = { 1.05f, 99.8f, 3f, 4.55f, 7.23f, 6.50f };
Arrays.sort(money, 3, money.length);
for (int i = 0; i < money.length; i++) {
float v = money[i];
System.out.print(v + "; ");
}
}
}
Sort Numbers
/*
* Copyright (c) 2000 David Flanagan. All rights reserved.
* This code is from the book Java Examples in a Nutshell, 2nd Edition.
* It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
* You may study, use, and modify it for any non-commercial purpose.
* You may distribute it non-commercially as long as you retain this notice.
* For a commercial use license, or to purchase the book (recommended),
* visit http://www.davidflanagan.ru/javaexamples2.
*/
/**
* This class demonstrates how to sort numbers using a simple algorithm
*/
public class SortNumbers {
/**
* This is a very simple sorting algorithm that is not very efficient when
* sorting large numbers of things
*/
public static void sort(double[] nums) {
// Loop through each element of the array, sorting as we go.
// Each time through, find the smallest remaining element, and move it
// to the first unsorted position in the array.
for (int i = 0; i < nums.length; i++) {
int min = i; // holds the index of the smallest element
// find the smallest one between i and the end of the array
for (int j = i; j < nums.length; j++) {
if (nums[j] < nums[min])
min = j;
}
// Now swap the smallest one with element i.
// This leaves all elements between 0 and i sorted.
double tmp;
tmp = nums[i];
nums[i] = nums[min];
nums[min] = tmp;
}
}
/** This is a simple test program for the algorithm above */
public static void main(String[] args) {
double[] nums = new double[10]; // Create an array to hold numbers
for (int i = 0; i < nums.length; i++)
// Generate random numbers
nums[i] = Math.random() * 100;
sort(nums); // Sort them
for (int i = 0; i < nums.length; i++)
// Print them out
System.out.println(nums[i]);
}
}
Sort string array with Collator
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.text.Collator;
public class Main {
public static void main(String args[]) throws Exception {
String[] words = { "é", "e", "a", "c" };
Writer w = new BufferedWriter(new OutputStreamWriter(System.out, "Cp850"));
for (int i = 0; i < 4; i++) {
w.write(words[i] + " ");
}
sortArray(Collator.getInstance(), words);
for (int i = 0; i < 4; i++) {
w.write(words[i] + " ");
}
w.flush();
w.close();
}
public static void sortArray(Collator collator, String[] strArray) {
String tmp;
if (strArray.length == 1)
return;
for (int i = 0; i < strArray.length; i++) {
for (int j = i + 1; j < strArray.length; j++) {
if (collator.rupare(strArray[i], strArray[j]) > 0) {
tmp = strArray[i];
strArray[i] = strArray[j];
strArray[j] = tmp;
}
}
}
}
}
Topological sorting
class Vertex {
public char label;
public Vertex(char lab) {
label = lab;
}
}
public class GraphTS {
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // list of vertices
private int matrix[][]; // adjacency matrix
private int numVerts; // current number of vertices
private char sortedArray[];
public GraphTS() {
vertexList = new Vertex[MAX_VERTS];
matrix = new int[MAX_VERTS][MAX_VERTS];
numVerts = 0;
for (int i = 0; i < MAX_VERTS; i++)
for (int k = 0; k < MAX_VERTS; k++)
matrix[i][k] = 0;
sortedArray = new char[MAX_VERTS]; // sorted vert labels
}
public void addVertex(char lab) {
vertexList[numVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end) {
matrix[start][end] = 1;
}
public void displayVertex(int v) {
System.out.print(vertexList[v].label);
}
public void topo() // toplogical sort
{
int orig_nVerts = numVerts;
while (numVerts > 0) // while vertices remain,
{
// get a vertex with no successors, or -1
int currentVertex = noSuccessors();
if (currentVertex == -1) // must be a cycle
{
System.out.println("ERROR: Graph has cycles");
return;
}
// insert vertex label in sorted array (start at end)
sortedArray[numVerts - 1] = vertexList[currentVertex].label;
deleteVertex(currentVertex); // delete vertex
}
// vertices all gone; display sortedArray
System.out.print("Topologically sorted order: ");
for (int j = 0; j < orig_nVerts; j++)
System.out.print(sortedArray[j]);
System.out.println("");
}
public int noSuccessors() // returns vert with no successors (or -1 if no such verts)
{
boolean isEdge; // edge from row to column in adjMat
for (int row = 0; row < numVerts; row++) {
isEdge = false; // check edges
for (int col = 0; col < numVerts; col++) {
if (matrix[row][col] > 0) // if edge to another,
{
isEdge = true;
break; // this vertex has a successor try another
}
}
if (!isEdge) // if no edges, has no successors
return row;
}
return -1; // no
}
public void deleteVertex(int delVert) {
if (delVert != numVerts - 1) // if not last vertex, delete from vertexList
{
for (int j = delVert; j < numVerts - 1; j++)
vertexList[j] = vertexList[j + 1];
for (int row = delVert; row < numVerts - 1; row++)
moveRowUp(row, numVerts);
for (int col = delVert; col < numVerts - 1; col++)
moveColLeft(col, numVerts - 1);
}
numVerts--; // one less vertex
}
private void moveRowUp(int row, int length) {
for (int col = 0; col < length; col++)
matrix[row][col] = matrix[row + 1][col];
}
private void moveColLeft(int col, int length) {
for (int row = 0; row < length; row++)
matrix[row][col] = matrix[row][col + 1];
}
public static void main(String[] args) {
GraphTS g = new GraphTS();
g.addVertex("A"); // 0
g.addVertex("B"); // 1
g.addVertex("C"); // 2
g.addVertex("D"); // 3
g.addVertex("E"); // 4
g.addVertex("F"); // 5
g.addVertex("G"); // 6
g.addVertex("H"); // 7
g.addEdge(0, 3); // AD
g.addEdge(0, 4); // AE
g.addEdge(1, 4); // BE
g.addEdge(2, 5); // CF
g.addEdge(3, 6); // DG
g.addEdge(4, 6); // EG
g.addEdge(5, 7); // FH
g.addEdge(6, 7); // GH
g.topo(); // do the sort
}
}
