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.
<source lang="java">
/*
* 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; }
}
</source>
Animation for quick sort
<source lang="java">
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); }
}
</source>
A quick sort demonstration algorithm
<source lang="java">
/*
* 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.
* * 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); } }
}
</source>
A simple applet class to demonstrate a sort algorithm
<source lang="java">
/* 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); } }
}
</source>
Binary Search
<source lang="java">
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); }
}
</source>
Binary search routines
<source lang="java">
/*
* 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; }
}
</source>
Bubble sort
<source lang="java">
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(); }
}
</source>
Combine Quick Sort Insertion Sort
<source lang="java">
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(); }
}
</source>
Fast Merge Sort
<source lang="java">
// 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.*
* 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 Comparables
to the
* Comparator
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);
}
}
</source>
FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows, using the comparator.
<source lang="java">
/* 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);
}
</source>
Fast Quick Sort
<source lang="java">
// 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 adaptsComparables
to the *Comparator
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); }
}
</source>
Heap sort
<source lang="java">
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(); }
}
</source>
Insert sort
<source lang="java">
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(); }
}
</source>
Insert Sort for objects
<source lang="java">
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; }
}
</source>
Linear search
<source lang="java">
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; }
}
</source>
Merge sort
<source lang="java">
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(); }
}
</source>
Performing Binary Search on Java byte Array Example
<source lang="java">
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); }
}
</source>
Performing Binary Search on Java char Array Example
<source lang="java">
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)); }
}
</source>
Performing Binary Search on Java double Array Example
<source lang="java">
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)); }
}
</source>
Performing Binary Search on Java float Array Example
<source lang="java">
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)); }
}
</source>
Performing Binary Search on Java int Array Example
<source lang="java">
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)); }
}
</source>
Performing Binary Search on Java long Array Example
<source lang="java">
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)); }
}
</source>
Performing Binary Search on Java short Array
<source lang="java">
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)); }
}
</source>
Quick Sort Implementation with median-of-three partitioning and cutoff for small arrays
<source lang="java">
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; } }
}
</source>
Quick sort with median-of-three partitioning
<source lang="java">
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(); }
}
</source>
Recursive Binary Search Implementation in Java
<source lang="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))); }
}
</source>
Selection sort
<source lang="java">
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(); }
}
</source>
Shell sort
<source lang="java">
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(); }
}
</source>
Simple Sort Demo
<source lang="java">
/*
* 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(); }
}
</source>
Simple version of quick sort
<source lang="java">
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(); }
}
</source>
Sort an array of objects
<source lang="java">
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; }
}
</source>
Sort a String array
<source lang="java">
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(); }
}
</source>
Sorting an array of Strings
<source lang="java">
// : 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)); }
} ///:~
</source>
Sort items of an array
<source lang="java">
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 + "; "); } }
}
</source>
Sort Numbers
<source lang="java">
/*
* 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]); }
}
</source>
Sort string array with Collator
<source lang="java">
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; } } } }
}
</source>
Topological sorting
<source lang="java">
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 }
}
</source>