CODEWITHSUNDEEP
javasortinginsertion-sortshellsort
ReezaCoriza
ReezaCoriza

Reputation: 143

Insertion Sort vs. Shell Sort Program. Shell sort only works some of the time

Ok, so this is for a data structures class. The assignment was to write a program that takes a list of 100 integers from a txt file, take 2 different sets of 4 intervals for shell sort, and then sort the 100 numbers, 1) by insertion sort, 2) by shell sort with first 4 numbers as intervals, 3) shell sort by second 100 as intervals, output the sorted list to a txt file, print the amount of assignment operations that take place in each sort(haven't done this part yet).

When I compile and run one of the shell sorts usually doesn't fully work, although it has partially sorted. The shell sort that doesn't fully sort could be either sort, so i'm assuming that the program works with certain intervals but not others, which isn't good :). Can anyone help

/**
 * @(#)Savit5.java
 *
 * Savit5 application
 *
 * @author
 * @version 1.00 2011/12/8
 */
 import java.util.*;
 import java.lang.*;
 import java.io.*;

public class Savit5 {

public static void main(String[] args) {

try {
    Scanner keyboardScanner = new Scanner(System.in);
    System.out.println("Please input the input file location:");
    String filePath = keyboardScanner.nextLine();
    Scanner scanner = new Scanner(new File(filePath));
    System.out.println("Please input 4 increment values for the first Shell Sort:");
    String shellOne = keyboardScanner.nextLine();
    System.out.println("Please input 4 increment values for the Second Shell Sort:");
    String shellTwo = keyboardScanner.nextLine();
    Scanner scanOne = new Scanner(shellOne);
    Scanner scanTwo = new Scanner(shellTwo);
    System.out.println("Please input the output file location:");
    String out = keyboardScanner.nextLine();
    int[] inc1 = new int[4];
        int q = 0;
        while (scanOne.hasNextInt()){
            inc1[q++] = scanOne.nextInt();
        }

    int[] inc2 = new int[4];
        int r = 0;
        while (scanTwo.hasNextInt()){
            inc2[r++] = scanTwo.nextInt();
        }

        int [] anArray = new int [100];
        int z = 0;
            while(scanner.hasNextInt()){
                anArray[z++] = scanner.nextInt();
            }
    int[] anArray2 = (int[])anArray.clone();
    int[] anArray3 = (int[])anArray.clone();
    int[] count = {0, 0, 0};
    int cnt=0;

    insertionSort(anArray, count, cnt);
    System.out.println("Assignment count:" + count[cnt]);
    cnt=1;
    shellSort(anArray2, inc1, count, cnt);
    System.out.println("Assignment count:" + count[cnt]);

    FileWriter output = new FileWriter(out);
    PrintWriter out2 = new PrintWriter(output);
    out2.println("Insertion Sort:");

    for (int i =0; i<anArray.length; i++) {
        out2.println(anArray[i]);
    }


    out2.println("Shell Sort 1:");
    for (int i =0; i<anArray2.length; i++) {
        out2.println(anArray2[i]);
    }

    out2.println("Shell Sort 2:");
    for (int i =0; i<anArray3.length; i++) {
        out2.println(anArray3[i]);
    }
    out2.close();
}
catch (IOException e)
{
    System.out.println (e);
}
}

public static void insertionSort(int[] a, int[] count, int cnt) {
    for (int i=1, j; i < a.length; i++) {
        int tmp = a[i];
        count[cnt] += 1;
        for (j = i - 1; j >= 0; j--) {
            if (a[j] <= tmp) break;
            a[j + 1] = a[j];
            count[cnt] += 1;
        }
        a[j + 1] = tmp;
        count[cnt] += 1;
    }
}


public static void shellSort(int[] a, int[] inc, int[] count, int cnt) {
for (int k =0; k<inc.length; k++) {
for (int i= inc[k], j; i < a.length; i+=inc[k]) {
    int tmp = a[i];
    count[cnt] +=1;
    for (j = i - inc[k]; j >= 0; j -= inc[k]) {
        if (a[j] <= tmp) break;
        a[j + inc[k]] = a[j];
        count[cnt] +=1;
    }
    a[j + inc[k]] = tmp;
    count[cnt] +=1;
   }
}
}


}

Upvotes: 1

Views: 1159

Answers (1)

Alejandro Diaz
Alejandro Diaz

Reputation: 431

I think the problem is that the "inc" (like inc1) vector might not always end in 1. This step is required by the algorithm because the last iteration should be like a normal insertion sort (but much quicker since several of the elements will be already sorted).

If that's the case, you can add an additional check in the code. If not, please provide an example.

Upvotes: 1

Related Questions