Skip to content

Instantly share code, notes, and snippets.

@rjlutz rjlutz/BubbleSort.java
Last active Nov 10, 2017

Embed
What would you like to do?
Sorting and Searching (Chapter 23) -- examples from Liang Intro to Java Comprehensive 10e
public class BubbleSort {
/** Bubble sort method */
public static void bubbleSort(int[] list) {
boolean needNextPass = true;
for (int k = 1; k < list.length && needNextPass; k++) {
// Array may be sorted and next pass not needed
needNextPass = false;
for (int i = 0; i < list.length - k; i++) {
if (list[i] > list[i + 1]) {
// Swap list[i] with list[i + 1]
int temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
needNextPass = true; // Next pass still needed
}
}
}
}
/** A test method */
public static void main(String[] args) {
int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
bubbleSort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
import java.io.*;
public class CreateLargeFile {
public static void main(String[] args) throws Exception {
DataOutputStream output = new DataOutputStream(
new BufferedOutputStream(
new FileOutputStream("largedata.dat")));
for (int i = 0; i < 800004; i++)
output.writeInt((int)(Math.random() * 1000000));
output.close();
// Display first 100 numbers
DataInputStream input =
new DataInputStream(new FileInputStream("largedata.dat"));
for (int i = 0; i < 100; i++)
System.out.print(input.readInt() + " ");
input.close();
}
}
public class Heap<E extends Comparable<E>> {
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
/** Create a default heap */
public Heap() {
}
/** Create a heap from an array of objects */
public Heap(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects[i]);
}
/** Add a new object into the heap */
public void add(E newObject) {
list.add(newObject); // Append to the heap
int currentIndex = list.size() - 1; // The index of the last node
while (currentIndex > 0) {
int parentIndex = (currentIndex - 1) / 2;
// Swap if the current object is greater than its parent
if (list.get(currentIndex).compareTo(
list.get(parentIndex)) > 0) {
E temp = list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex, temp);
}
else
break; // the tree is a heap now
currentIndex = parentIndex;
}
}
/** Remove the root from the heap */
public E remove() {
if (list.size() == 0) return null;
E removedObject = list.get(0);
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);
int currentIndex = 0;
while (currentIndex < list.size()) {
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
// Find the maximum between two children
if (leftChildIndex >= list.size()) break; // The tree is a heap
int maxIndex = leftChildIndex;
if (rightChildIndex < list.size()) {
if (list.get(maxIndex).compareTo(
list.get(rightChildIndex)) < 0) {
maxIndex = rightChildIndex;
}
}
// Swap if the current node is less than the maximum
if (list.get(currentIndex).compareTo(
list.get(maxIndex)) < 0) {
E temp = list.get(maxIndex);
list.set(maxIndex, list.get(currentIndex));
list.set(currentIndex, temp);
currentIndex = maxIndex;
}
else
break; // The tree is a heap
}
return removedObject;
}
/** Get the number of nodes in the tree */
public int getSize() {
return list.size();
}
}
public class HeapSort {
/** Heap sort method */
public static <E extends Comparable<E>> void heapSort(E[] list) {
// Create a Heap of integers
Heap<E> heap = new Heap<E>();
// Add elements to the heap
for (int i = 0; i < list.length; i++)
heap.add(list[i]);
// Remove elements from the heap
for (int i = list.length - 1; i >= 0; i--)
list[i] = heap.remove();
}
/** A test method */
public static void main(String[] args) {
Integer[] list = {-44, -5, -3, 3, 3, 1, -4, 0, 1, 2, 4, 5, 53};
heapSort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
public class InsertionSort {
/** The method for sorting the numbers */
public static void insertionSort(double[] list) {
for (int i = 1; i < list.length; i++) {
/** insert list[i] into a sorted sublist list[0..i-1] so that
list[0..i] is sorted. */
double currentElement = list[i];
int k;
for (k = i - 1; k >= 0 && list[k] > currentElement; k--) {
list[k + 1] = list[k];
}
// Insert the current element into list[k+1]
list[k + 1] = currentElement;
}
}
}
public class MergeSort {
/** The method for sorting the numbers */
public static void mergeSort(int[] list) {
if (list.length > 1) {
// Merge sort the first half
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
// Merge sort the second half
int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2,
secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
// Merge firstHalf with secondHalf into list
merge(firstHalf, secondHalf, list);
}
}
/** Merge two sorted lists */
public static void merge(int[] list1, int[] list2, int[] temp) {
int current1 = 0; // Current index in list1
int current2 = 0; // Current index in list2
int current3 = 0; // Current index in temp
while (current1 < list1.length && current2 < list2.length) {
if (list1[current1] < list2[current2])
temp[current3++] = list1[current1++];
else
temp[current3++] = list2[current2++];
}
while (current1 < list1.length)
temp[current3++] = list1[current1++];
while (current2 < list2.length)
temp[current3++] = list2[current2++];
}
/** A test method */
public static void main(String[] args) {
int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
mergeSort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
public class QuickSort {
public static void quickSort(int[] list) {
quickSort(list, 0, list.length - 1);
}
private static void quickSort(int[] list, int first, int last) {
if (last > first) {
int pivotIndex = partition(list, first, last);
quickSort(list, first, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
}
}
/** Partition the array list[first..last] */
private static int partition(int[] list, int first, int last) {
int pivot = list[first]; // Choose the first element as the pivot
int low = first + 1; // Index for forward search
int high = last; // Index for backward search
while (high > low) {
// Search forward from left
while (low <= high && list[low] <= pivot)
low++;
// Search backward from right
while (low <= high && list[high] > pivot)
high--;
// Swap two elements in the list
if (high > low) {
int temp = list[high];
list[high] = list[low];
list[low] = temp;
}
}
while (high > first && list[high] >= pivot)
high--;
// Swap pivot with list[high]
if (pivot > list[high]) {
list[first] = list[high];
list[high] = pivot;
return high;
}
else {
return first;
}
}
/** A test method */
public static void main(String[] args) {
int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
quickSort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
// note you may want to refactor to process int[] for ITEC2150 (rather than float) benchmarling assignment
public class SelectionSort {
/** The method for sorting the numbers */
public static void selectionSort(double[] list) {
for (int i = 0; i < list.length - 1; i++) {
// Find the minimum in the list[i..list.length-1]
double currentMin = list[i];
int currentMinIndex = i;
for (int j = i + 1; j < list.length; j++) {
if (currentMin > list[j]) {
currentMin = list[j];
currentMinIndex = j;
}
}
// Swap list[i] with list[currentMinIndex] if necessary;
if (currentMinIndex != i) {
list[currentMinIndex] = list[i];
list[i] = currentMin;
}
}
}
}
import java.io.*;
public class SortLargeFile {
public static final int MAX_ARRAY_SIZE = 43;
public static final int BUFFER_SIZE = 100000;
public static void main(String[] args) throws Exception {
// Sort largedata.dat to sortedfile.dat
sort("largedata.dat", "sortedfile.dat");
// Display the first 100 numbers in the sorted file
displayFile("sortedfile.dat");
}
/** Sort data in source file and into target file */
public static void sort(String sourcefile, String targetfile)
throws Exception {
// Implement Phase 1: Create initial segments
int numberOfSegments =
initializeSegments(MAX_ARRAY_SIZE, sourcefile, "f1.dat");
// Implement Phase 2: Merge segments recursively
merge(numberOfSegments, MAX_ARRAY_SIZE,
"f1.dat", "f2.dat", "f3.dat", targetfile);
}
/** Sort original file into sorted segments */
private static int initializeSegments
(int segmentSize, String originalFile, String f1)
throws Exception {
int[] list = new int[segmentSize];
DataInputStream input = new DataInputStream(
new BufferedInputStream(new FileInputStream(originalFile)));
DataOutputStream output = new DataOutputStream(
new BufferedOutputStream(new FileOutputStream(f1)));
int numberOfSegments = 0;
while (input.available() > 0) {
numberOfSegments++;
int i = 0;
for ( ; input.available() > 0 && i < segmentSize; i++) {
list[i] = input.readInt();
}
// Sort an array list[0..i-1]
java.util.Arrays.sort(list, 0, i);
// Write the array to f1.dat
for (int j = 0; j < i; j++) {
output.writeInt(list[j]);
}
}
input.close();
output.close();
return numberOfSegments;
}
private static void merge(int numberOfSegments, int segmentSize,
String f1, String f2, String f3, String targetfile)
throws Exception {
if (numberOfSegments > 1) {
mergeOneStep(numberOfSegments, segmentSize, f1, f2, f3);
merge((numberOfSegments + 1) / 2, segmentSize * 2,
f3, f1, f2, targetfile);
}
else { // Rename f1 as the final sorted file
File sortedFile = new File(targetfile);
if (sortedFile.exists()) sortedFile.delete();
new File(f1).renameTo(sortedFile);
}
}
private static void mergeOneStep(int numberOfSegments,
int segmentSize, String f1, String f2, String f3)
throws Exception {
DataInputStream f1Input = new DataInputStream(
new BufferedInputStream(new FileInputStream(f1), BUFFER_SIZE));
DataOutputStream f2Output = new DataOutputStream(
new BufferedOutputStream(new FileOutputStream(f2), BUFFER_SIZE));
// Copy half number of segments from f1.dat to f2.dat
copyHalfToF2(numberOfSegments, segmentSize, f1Input, f2Output);
f2Output.close();
// Merge remaining segments in f1 with segments in f2 into f3
DataInputStream f2Input = new DataInputStream(
new BufferedInputStream(new FileInputStream(f2), BUFFER_SIZE));
DataOutputStream f3Output = new DataOutputStream(
new BufferedOutputStream(new FileOutputStream(f3), BUFFER_SIZE));
mergeSegments(numberOfSegments / 2,
segmentSize, f1Input, f2Input, f3Output);
f1Input.close();
f2Input.close();
f3Output.close();
}
/** Copy first half number of segments from f1.dat to f2.dat */
private static void copyHalfToF2(int numberOfSegments,
int segmentSize, DataInputStream f1, DataOutputStream f2)
throws Exception {
for (int i = 0; i < (numberOfSegments / 2) * segmentSize; i++) {
f2.writeInt(f1.readInt());
}
}
/** Merge all segments */
private static void mergeSegments(int numberOfSegments,
int segmentSize, DataInputStream f1, DataInputStream f2,
DataOutputStream f3) throws Exception {
for (int i = 0; i < numberOfSegments; i++) {
mergeTwoSegments(segmentSize, f1, f2, f3);
}
// If f1 has one extra segment, copy it to f3
while (f1.available() > 0) {
f3.writeInt(f1.readInt());
}
}
/** Merges two segments */
private static void mergeTwoSegments(int segmentSize,
DataInputStream f1, DataInputStream f2,
DataOutputStream f3) throws Exception {
int intFromF1 = f1.readInt();
int intFromF2 = f2.readInt();
int f1Count = 1;
int f2Count = 1;
while (true) {
if (intFromF1 < intFromF2) {
f3.writeInt(intFromF1);
if (f1.available() == 0 || f1Count++ >= segmentSize) {
f3.writeInt(intFromF2);
break;
}
else {
intFromF1 = f1.readInt();
}
}
else {
f3.writeInt(intFromF2);
if (f2.available() == 0 || f2Count++ >= segmentSize) {
f3.writeInt(intFromF1);
break;
}
else {
intFromF2 = f2.readInt();
}
}
}
while (f1.available() > 0 && f1Count++ < segmentSize) {
f3.writeInt(f1.readInt());
}
while (f2.available() > 0 && f2Count++ < segmentSize) {
f3.writeInt(f2.readInt());
}
}
/** Display the first 100 numbers in the specified file */
public static void displayFile(String filename) {
try {
DataInputStream input =
new DataInputStream(new FileInputStream(filename));
for (int i = 0; i < 100; i++)
System.out.print(input.readInt() + " ");
input.close();
}
catch (IOException ex) {
ex.printStackTrace();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.