I am trying to sort the arrays using different algorithms. When I run the application with small number of arrays, it works and produces the results. When the arrays are larger than: 131072, it stops responding.
What can be the reason? Is there anything wrong with this code?
This is my function:
boolean runTest(String[] text, int[] number, String url, String out, Sort sort) {
PrintWriter filename;
boolean tobeReturned = true;
String beforeSorting = "";
String afterSorting = "";
long startTime;
double timeTaken;
try {
filename = createWriter(out);
for(File directory : new File(url).listFiles()){
File[] listOfFiles = directory.listFiles();
filename.println("Number of Records: \t" + directory.getName());
for (File file : listOfFiles) {
text = loadStrings(file);
number = int(text);
if (isSorted(number)) { beforeSorting = "Sorted";} else { beforeSorting = "NOT Sorted"; };
startTime = startTime();
sort.sortInteger(number);
timeTaken = stopTime(startTime);
if (isSorted(number)) { afterSorting = "Sorted"; } else { afterSorting = "NOT Sorted"; };
filename.println("File Set " + file.getName() + ": \t\t" + beforeSorting + ": \t" + afterSorting + ": \t" + timeTaken);
timeTaken = 0;
}
filename.println("\n");
}
filename.flush();
filename.close();
}
catch (Exception e) {
tobeReturned = false;
}
return tobeReturned;
}
Interface:
interface Sort{
public int[] sortInteger(int[] input);
}
One of the sorting class (Insertion)
class Insertion implements Sort{
Insertion() {
}
int[] sortInteger(int[] input) {
int i, j, tobeSorted;
for (i = 1; i < input.length; i++) {
tobeSorted = input[i];
j = i;
while (j > 0 && input[j - 1] > tobeSorted) {
input[j] = input[j - 1];
j--;
}
input[j] = tobeSorted;
}
//println(input);
return input;
}
}
Numbers folders:
Files:
Records:
Result of insertion sort:
Result of merge sort:
******UPDATE******
Full Simplified Processing Code
import java.util.*;
long a = 9; // total loop, 9 means = 65536, 10 means = 131072 ...
long b = 2; // multiplier, 2 means = 512,1024,2048...
long c = 512; // starting number
long d = 5; // times random text file
String url;
Insertion insertion;
Merge merge;
Bubble bubble;
Shell shell;
QuickSort quickSort;
void setup() {
url = sketchPath("_numbers/");
insertion = new Insertion();
merge = new Merge();
bubble = new Bubble();
shell = new Shell();
quickSort = new QuickSort();
generateFiles(a,b,c,d);
boolean runSortTest = false;
runSortTest = runTest(url, "_results/a_insertion.txt", insertion);
runSortTest = runTest(url, "_results/b_merge.txt", merge);
runSortTest = runTest(url, "_results/c_bubble.txt", bubble);
runSortTest = runTest(url, "_results/d_shell.txt", shell);
runSortTest = runTest(url, "_results/e_quickSort.txt", quickSort);
if(runSortTest){
println("Done");
}else{
println("Error");
}
}
boolean generateFiles(long totalLoop, long multiplier, long power, long fileNumber){
PrintWriter pw;
//int orderCount = 1;
int count = 1;
//boolean tobeReturned = true;
try {
for (int i = 1; i < totalLoop; i = i+1) {
for (int j = 1; j < fileNumber+1; j = j+1) {
pw = createWriter("/_numbers/" + power + "/" + count + ".txt");
for (int k = 0; k < power; k = k+1) {
pw.println(randomNumber(0, power));
//pw.write(int(randomNumber(0, power)) + "\t");
}
count++;
pw.flush(); // Writes the remaining data to the file
pw.close(); // Finishes the file
}
count = 1;
//orderCount++;
power *= multiplier;
}
//orderCount = 1;
return true;
} catch (Exception e) {
return false;
}
}
long randomNumber(long min, long max){
long randomN = (long)random(min,(max + 1));
return randomN;
}
//####################################################################################################
//## Runs the test and produces a log file for each algorithms
//####################################################################################################
boolean runTest(String url, String out, Sort sort) {
PrintWriter filename;
boolean tobeReturned = true;
String beforeSorting = "";
String afterSorting = "";
long startTime;
double timeTaken;
try {
filename = createWriter(out);
for(File directory : new File(url).listFiles()){
File[] listOfFiles = directory.listFiles();
filename.println("Number of Records: \t" + directory.getName());
for (File file : listOfFiles) {
String[] text; int[] number;
text = loadStrings(file);
number = int(text);
if (isSorted(number)) { beforeSorting = "Sorted";} else { beforeSorting = "NOT Sorted"; };
startTime = startTime();
sort.sortInteger(number);
timeTaken = stopTime(startTime);
if (isSorted(number)) { afterSorting = "Sorted"; } else { afterSorting = "NOT Sorted"; };
filename.println("File Set " + file.getName() + ": \t\t" + beforeSorting + ": \t" + afterSorting + ": \t" + timeTaken);
timeTaken = 0;
Arrays.fill(text, null);
number = null;
}
filename.println("\n");
}
filename.flush();
filename.close();
}
catch (Exception e) {
e.printStackTrace();
tobeReturned = false;
}
return tobeReturned;
}
boolean isSorted(int[] array) {
for (int i = 0; i < array.length-1; i ++) {
if (array[i] > array[i+1]) {
return false;
}
}
return true;
}
//####################################################################################################
//## Time comparison
//####################################################################################################
long startTime() {
return System.nanoTime();
}
double stopTime(long startTime) {
double finalTime = (System.nanoTime() - startTime)/1000000000.0;
return finalTime;
}
/*
Interface
# Last update: 20 October 2015
*/
interface Sort{
public int[] sortInteger(int[] input);
}
/*
Insertion class, implements Sort interface
# Last update: 25 October 2015
*/
class Insertion implements Sort{
Insertion() {
}
int[] sortInteger(int[] input) {
int i, j, tobeSorted;
for (i = 1; i < input.length; i++) {
tobeSorted = input[i];
j = i;
while (j > 0 && input[j - 1] > tobeSorted) {
input[j] = input[j - 1];
j--;
}
input[j] = tobeSorted;
}
//println(input);
return input;
}
}
/*
Merge class, implements Sort interface
# Last update: 25 October 2015
*/
class Merge implements Sort{
Merge() {
}
int[] sortInteger(int[] input) {
if (input.length > 1) {
// split array into two halves
int[] left = leftHalf(input);
int[] right = rightHalf(input);
// recursively sort the two halves
sortInteger(left);
sortInteger(right);
// merge the sorted halves into a sorted whole
merge(input, left, right);
}
return input;
}
// Returns the first half of the given array.
int[] leftHalf(int[] array) {
int size1 = array.length / 2;
int[] left = new int[size1];
for (int i = 0; i < size1; i++) {
left[i] = array[i];
}
return left;
}
// Returns the second half of the given array.
int[] rightHalf(int[] array) {
int size1 = array.length / 2;
int size2 = array.length - size1;
int[] right = new int[size2];
for (int i = 0; i < size2; i++) {
right[i] = array[i + size1];
}
return right;
}
void merge(int[] result, int[] left, int[] right) {
int i1 = 0; // index into left array
int i2 = 0; // index into right array
for (int i = 0; i < result.length; i++) {
if (i2 >= right.length || (i1 < left.length &&
left[i1] <= right[i2])) {
result[i] = left[i1]; // take from left
i1++;
} else {
result[i] = right[i2]; // take from right
i2++;
}
}
}
}
/*
Bubble class, implements Sort interface
# Last update: 25 October 2015
*/
class Bubble implements Sort {
Bubble() {
}
int[] sortInteger(int[] input) {
boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < input.length - j; i++) {
if (input[i] > input[i + 1]) {
tmp = input[i];
input[i] = input[i + 1];
input[i + 1] = tmp;
swapped = true;
}
}
}
return input;
}
}
/*
Shell class, implements Sort interface
# Last update: 25 October 2015
*/
class Shell implements Sort {
Shell() {
}
int[] sequence = {59724292, 26544130, 11797391, 5243258, 2330349, 1035711, 460316, 204585, 90927, 40412, 17961, 7983, 3548, 1577, 701, 301, 132, 57, 23, 10, 4, 1};
/*
int number = 701;
for(int i=0; i<15; i++){
int newN = int(number*2.25);
println(number);
number = newN;
}
*/
int[] sortInteger (int[] input) {
int size = input.length;
int i, j, temp;
for ( int s : sequence ) {
i = s;
while ( i < size ) {
temp = input[i];
j = i-s;
while ( j >= 0 && input[j] > temp ) {
input[j + s] = input[j];
j -= s;
}
input[j + s] = temp;
i ++;
}
}
return input;
}
}
/*
QuickSort class, implements Sort interface
# Last update: 26 October 2015
*/
class QuickSort implements Sort {
QuickSort() {
}
int[] sortInteger(int[] input) {
quickSort(input, 0, input.length-1) ;
return input;
}
public void quickSort(int arr[], int low, int high)
{
int i = low, j = high;
int temp;
int pivot = arr[(low + high) / 2];
/** partition **/
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
/** swap **/
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
/** recursively sort lower half **/
if (low < j)
quickSort(arr, low, j);
/** recursively sort upper half **/
if (i < high)
quickSort(arr, i, high);
}
}
LinkedListwould not be a good choice here (in fact, it's very rarely a good choice).LinkedListis not thread-safe either.tophow your machine behaves during the execution of this program. The temporal complexity is huge (d * f * 2n * sorting, wheredis the number of directories,fthe number of files,nthe element in each file,2because you checked twice if the array is sorted and this can only be linear - I guess). Also I have concern about spatial complexity: try to settextandnumbertonullafter the innerforto clean up some memory. Anyway, withtopyou will see how your system resources react to the program.