Java Shell Sort

Java Shell SortWelcome to my Java Shell Sort tutorial! I really tried to have fun explaining how the Shell Sort works in this tutorial. I show how it works in 4 different ways. We see it graphically, in a presentation format, explained during execution and again in the code itself. Everything can be found after the video.

The Shell Sort is one of the fastest of the easier to understand sorting algorithms. It is similar to the insertion sort, but it has an added feature in which it partially sorts the array before the insertion sort is used. The video and code below will explain everything.

If you like videos like this, it helps to tell Google+

Code From the Video

 Java Shell Sort

import java.util.Arrays;

public class ShellSort {

	public void sort() {

		int inner, outer, temp;

		int interval = 1;
		while (interval <= arraySize / 3){

			// Define an interval sequence

			interval = interval * 3 + 1;

		// Keep looping until the interval is 1
		// Then this becomes an insertion sort

		while (interval > 0) {

			// Continue incrementing outer until the end of the array is reached

			for (outer = interval; outer < arraySize; outer++) {

				// Store the value of the array in temp unless it has to be
				// copied to a space occupied by a bigger number closer to the
				// beginning of the array

				temp = theArray[outer];

				System.out.println("Copy " + theArray[outer] + " into temp");

				// inner is assigned the value of the highest index to check
				// against all values the proceed it. Along the way if a
				// number is greater than temp it will be moved up in the array

				inner = outer;

				System.out.println("Checking if " + theArray[inner - interval]
						+ " in index " + (inner - interval)
						+ " is bigger than " + temp);

				// While there is a number bigger than temp move it further
				// up in the array

				while (inner > interval - 1
						&& theArray[inner - interval] >= temp) {

					System.out.println("In While Checking if "
							+ theArray[inner - interval] + " in index "
							+ (inner - interval) + " is bigger than " + temp);

					printHorzArray(inner, outer, interval);

					// Make room for the smaller temp by moving values in the
					// array
					// up one space if they are greater than temp

					theArray[inner] = theArray[inner - interval];

					System.out.println(theArray[inner - interval]
							+ " moved to index " + inner);

					inner -= interval;

					System.out.println("inner= " + inner);

					printHorzArray(inner, outer, interval);

					System.out.println("outer= " + outer);
					System.out.println("temp= " + temp);
					System.out.println("interval= " + interval);

				}

				// Now that everything has been moved into place put the value
				// stored in temp into the index above the first value smaller
				// than it is

				theArray[inner] = temp;

				System.out.println(temp + " moved to index " + inner);

				printHorzArray(inner, outer, interval);

			}

			// Once we get here we have interval sorted our array
			// so we decrement interval and go again

			interval = (interval - 1) / 3;
		}

	}

	public static void main(String[] args) {

		ShellSort theSort = new ShellSort(10);

		System.out.println(Arrays.toString(theSort.theArray));

		theSort.sort();

		System.out.println(Arrays.toString(theSort.theArray));

	}

	private int[] theArray;

	private int arraySize;

	ShellSort(int arraySize) {

		this.arraySize = arraySize;

		theArray = new int[arraySize];

		generateRandomArray();

	}

	public void generateRandomArray() {

		for (int i = 0; i < arraySize; i++) {

			// Generate a random array with values between
			// 10 and 59

			theArray[i] = (int) (Math.random() * 50) + 10;

		}

	}

	public void printHorzArray(int i, int j, int h) {

		if (i == j)
			i = i - h;

		for (int n = 0; n < 51; n++)
			System.out.print("-");

		System.out.println();

		for (int n = 0; n < arraySize; n++) {

			System.out.print("| " + n + "  ");

		}

		System.out.println("|");

		for (int n = 0; n < 51; n++)
			System.out.print("-");

		System.out.println();

		for (int n = 0; n < arraySize; n++) {

			System.out.print("| " + theArray[n] + " ");

		}

		System.out.println("|");

		for (int n = 0; n < 51; n++)
			System.out.print("-");

		System.out.println();

		if (i != -1) {

			// Number of spaces to put before the F

			int spacesBeforeFront = 5 * i + 1;

			for (int k = 0; k < spacesBeforeFront; k++)
				System.out.print(" ");

			System.out.print("I");

			// Number of spaces to put before the R

			int spacesBeforeRear = (5 * j + 1 - 1) - spacesBeforeFront;

			for (int l = 0; l < spacesBeforeRear; l++)
				System.out.print(" ");

			System.out.print("O");

			System.out.println("\n");

		}

	}

}

Java Shell Sort BarExample.java

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Font;
import java.awt.Paint;

import javax.swing.JFrame;
import javax.swing.JInternalFrame;
import javax.swing.JLabel;

import org.jfree.chart.ChartFactory;
import org.jfree.chart.ChartPanel;
import org.jfree.chart.JFreeChart;
import org.jfree.chart.plot.CategoryPlot;
import org.jfree.chart.plot.PlotOrientation;
import org.jfree.chart.renderer.category.BarRenderer;
import org.jfree.chart.renderer.category.CategoryItemRenderer;
import org.jfree.data.category.DefaultCategoryDataset;

public class BarExample {

	private int[] theArray;

	private int arraySize;

	ChartPanel chartPanel;

	JLabel intervalLabel;

	DefaultCategoryDataset dataset;

	public BarExample(int arraySize) {

		this.arraySize = arraySize;

		theArray = new int[arraySize];

		JFrame theFrame = new JFrame();

		theFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

		JInternalFrame theInnerFrame = new JInternalFrame("Chart", true, true,
				true, true);

		dataset = new DefaultCategoryDataset();

		generateRandomArray(dataset);

		JFreeChart chart = ChartFactory.createBarChart("Shell Sort",
				"Random Values", "Values", dataset, PlotOrientation.VERTICAL,
				false, true, false);

		chart.setBackgroundPaint(Color.white);
		chart.getTitle().setPaint(Color.black);

		CategoryPlot p = chart.getCategoryPlot();

		CategoryItemRenderer renderer = new DifferenceBarRenderer();

		p.setRenderer(renderer);

		p.setRangeGridlinePaint(Color.blue);

		chartPanel = new ChartPanel(chart);

		theInnerFrame.add(chartPanel);

		intervalLabel = new JLabel("Hello");

		intervalLabel.setFont(new Font("SansSerif", Font.PLAIN, 30));

		intervalLabel.setHorizontalAlignment(JLabel.CENTER);

		theInnerFrame.pack();

		theInnerFrame.setVisible(true);

		chartPanel.setSize(1500, 800);

		theFrame.add(theInnerFrame, BorderLayout.CENTER);

		theFrame.add(intervalLabel, BorderLayout.NORTH);

		theFrame.setSize(1920, 1080);

		theFrame.setLocationRelativeTo(null);

		theFrame.setVisible(true);

		sort();
	}

	public void generateRandomArray(DefaultCategoryDataset dataset) {

		for (int i = 0; i < arraySize; i++) {

			// Generate a random array with values between
			// 10 and 59

			theArray[i] = (int) (Math.random() * 50) + 10;

			dataset.setValue((int) (Math.random() * 50) + 10, "Value",
					Integer.toString(i));

		}

	}

	public void updateTheBarChart(DefaultCategoryDataset dataset) {

		for (int i = 0; i < arraySize; i++) {

			dataset.setValue(theArray[i], "Value", Integer.toString(i));

		}

		chartPanel.repaint();

	}

	public void sort() {

		int inner, outer, temp;

		int interval = 1;

		try {
			Thread.sleep(1500);
		} catch (InterruptedException e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		}

		while (interval <= arraySize / 3)

			// Define an interval sequence

			interval = interval * 3 + 1;

		// Keep looping until the interval is 1
		// Then this becomes an insertion sort

		while (interval > 0) {

			// Continue incrementing outer until the end of the array is reached

			for (outer = interval; outer < arraySize; outer++) {

				// Store the value of the array in temp unless it has to be
				// copied to a space occupied by a bigger number closer to the
				// beginning of the array

				temp = theArray[outer];

				// inner is assigned the value of the highest index to check
				// against all values the proceed it. Along the way if a
				// number is greater than temp it will be moved up in the array

				inner = outer;

				// While there is a number bigger than temp move it further
				// up in the array

				while (inner > interval - 1
						&& theArray[inner - interval] >= temp) {

					// Make room for the smaller temp by moving values in the
					// array
					// up one space if they are greater than temp

					theArray[inner] = theArray[inner - interval];

					inner -= interval;

				}

				// Now that everything has been moved into place put the value
				// stored in temp into the index above the first value smaller
				// than it is

				theArray[inner] = temp;

				updateTheBarChart(dataset);

				try {

					intervalLabel.setText("INTERVAL : " + interval);

					Thread.sleep(500);
				} catch (InterruptedException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}

			}
			interval = (interval - 1) / 3;
		}

	}

	public static void main(String[] args) {

		new BarExample(50);

	}

}

class DifferenceBarRenderer extends BarRenderer {
	public DifferenceBarRenderer() {
		super();
	}

	public Paint getItemPaint(int x_row, int x_col) {
		return Color.blue;
	}
}

10 Responses to “Java Shell Sort”

  1. zahra says:

    hey derek, there’s suppose to be a closing bracket at line 014 ???

    010 while (interval <= arraySize / 3){
    011
    012// Define an interval sequence
    013
    014 interval = interval * 3 + 1;

  2. Ido says:

    after following the coding in this tutorial i’m getting a program that runs infinitely.

    i think it has something to do with the interval advancement – but wasn’t able to really put my finger on where the problem is.

    and even after the array id perfectly sorted the program keeps on running.

  3. Jack Zhang says:

    Hi Derek,
    When I first ran your code , it kept repeating inside the first while loop. So I changed the first while loop’s condition into “interval > 0” and it solved the problem. I think after the interval is decremented to 0, we can’t jump out of the first while loop if the condition is “interval <= arraySize/3", because 0 is always less than "arraySize/3". I don't know if my change makes sense.
    Thanks!

    Jack

  4. zahra says:

    i said to put the closing bracket at line 014 for the same reason. the loop has to define the interval of 4 only once
    010 while (interval 0) {…
    and then turning to a insertion sort

    this solves the problem, otherwise the program keeps running infinitely.

  5. sanket says:

    Hi Derek,

    while (interval <= arraySize / 3)
    // Define an interval sequence
    interval = interval * 3 + 1;

    this is the change i made it is working fine

  6. sanket says:

    Derek,

    your tutorial are always excellent , i have one small request can you post multithreading tutorial with concurrency ,it will help us yo clear this concept with your tutorial

Leave a Reply

Your email address will not be published.

Google+