Java Shell Sort

[@derekbanas]

Thank you :) I need to get back to algorithms and cover the topics that I skipped soon. I'm happy that you find them interesting.

[@MexterO123]

Never mind, Derek. I ran the code as you said at the end of your video and I figured it out. You rock, man! I think though it would be helpful for many CS students if you would include an output text file on your website so that we could run through the logic before looking at your code.

[@derekbanas]

Sorry I couldn't get to you quicker. Today was my daughters birthday. I'm happy you figured it out. I'll definitely provide output if you think that would help

[@smlasdhaosf7764]

Great work, Derek! I would say, this is by far the best shell sort video on YT only for one reason: the increment sequence you are using! many other videos stick to the floor(length/2) method, or the 'power of two' gap sequence, although it gives you the correct answer(as long as the final pass gap is 1), it is not widely used in real life because of the time complexity(worst case N^2 as insertion sort) Knuth chose 3*i+1 pattern series(1,4,13,40...) for easy demonstration and efficiency in his book(invented by Pratt), which gives a O(N^1.5) time complexity Another popular sequence comes from Sedgewick(Knuth's student): 1,5,19,41... that's O(N^(4/3)) time complexity

[@derekbanas]

Thank you for the nice compliment :) I do my best to explain topics in original ways.

[@derekbanas]

Thank you :) This series isn't very popular, so I'm glad you like it

[@MexterO123]

That would be a blessing, dude. Happy Birthday to your daughter. You don't know how much I appreciate your videos, you should teach. : )

[@derekbanas]

Thank you :) I was trying a whole bunch of new tricks in this video. I'll cover hash maps very soon

[@derekbanas]

Thank you :) mainly it is video editing, but I also use a ton of eclipse shortcuts that I normally edit out so I don't confuse people. I may do a video on eclipse shortcuts. They can save a ton of time

[@derekbanas]

inner is assigned the value of the highest index to check, so we don't want interval to ever be larger then it

[@frogdu]

lol, thanks Derek! every time I got question with java algorithms I would check your channel. Your codes are wonderful tool helping me understand the algorithms in detail. PS, the missing "}" of the first while loop in your code is so interesting.

[@ArmagedonNoise]

I've got an infinite loop , but if I write the first while as a separate loop works fine. (o.O) Thanks for the tutorial is explained very well :)

[@derekbanas]

நான் உங்களுக்கு பிடித்திருக்கிறது என்று சந்தோஷமாக இருக்கிறேன். நான் இந்த வீடியோ புதிய கற்பித்தல் கருத்துக்கள் பரிசோதனை நிறைய செய்தார். நான் ஒரு வழக்கமான அடிப்படையில் வீடியோக்கள் வெளியே என் சிறந்த செய்வேன்.

[@NickTunac]

Thank you for your tutorials Derek! I'll be having my internship this summer, and they said that we'll use java. So I need to watch all your java tutorials :P

[@derekbanas]

I'm incrementing interval in the code. Try putting some code in my code that shows the value of increment. That is the best way to understand what's going on. I have the code in the description. I hope that helps

[@DarrinLin]

This is really convoluted. void shellsort(array a) { for (int i = a.size() / 2; i > 0; i /= 2) { for(int j = i; i < a.size(); ++j) { int temp = a[j]; int k = j; for (; k >= i && temp < a[k-i]; k -= i) { a[k] = a[k-i]; } a[k] = temp; } } }

[@pebble2258]

I think I'll be the first to say that this was harder to implement than quick sort. I don't understand how this is less complicated than quick sort.

[@derekbanas]

மிகவும் நன்றி

[@123japanuser]

ஹலோ பயிற்சியாளர் அன்பே, இந்த கருத்து மிகவும் மகிழ்ச்சி அடைவார். நான் இந்த முறை வெற்றி முடியவில்லை: ( 5 EST மணி புதிய முறை மற்றும் நான் தயார் :) முடியாது மிக்க நன்றி

[@GeloEd]

Try adding "}" in line 15 if you're getting error in line 92 :D

[@derekbanas]

No problem :) I'm happy to help

[@NaturalPro100]

Nicley explained.Great job...

[@derekbanas]

+tarun nahar Thank you :)

[@monome3038]

Very well explained sir! I loved the idea of printing on the consol the comments instead of typing them with the code, it makes it easier to understand! Thank you so much :) Do you have a video about complexity of algorithms?

[@derekbanas]

Thank you :) What do you mean by "complexity of algorithms"?

[@monome3038]

I meant the Big O notation , analysis of algorithms

[@dillon9347]

Love the tutorials Derek they are very helpful. Just a heads up though I think you have a bracket at line 10 by mistake, after the first while loop.

[@derekbanas]

Thank you very much :) Sorry for the error

[@derekbanas]

I use it constantly :)

[@derekbanas]

Thank you :) I do my best

[@Mangoose_ola]

well done Derek Banas. Thanks

[@derekbanas]

Thank you :)

[@derekbanas]

Have fun with it and you'll learn everything. I'll do my best to make it interesting. Feel free to ask questions

[@jasdn93bsad992]

Hello, Derek. First of all, thank you for making such great videos. However, I noticed you set int interval = 1 initially then in the first while loop, it becomes 4. Further down, at the end of the second while loop, interval decreases itself again which equals to 1. I totally understand your logic but it seems setting interval to 4 in the first place is a more straightforward way to do it. Please help me understand if I am missing anything. Thank you so much. :)

[@Vendettaaaa666]

you can try cave of programming for that...he has good tutorials....but I would love to see Dereks' as well

[@kunalsingh-yj7xs]

Great tutorial. It seems that your code is inspired Robert Lafore book.

[@derekbanas]

Thank you :) Yes I combine the best aspects from the best books. He wrote one of the best books on Data Structures and Algorithms.

[@wlieng]

Great Video! Love your tutorials. Do you have any tutorials on hash maps?

[@MexterO123]

Hi Derek, I'm a beginning CS student. I just want to clarify something. So you mean to say that the Shell Sort Algorithm makes it easier for the Insertion Sort algorithm? Are they similar algorithms?

[@jahmes1]

This is really cool stuff

[@NickTunac]

Thank you Derek! My Java master ^_^

[@derekbanas]

You're very welcome :)

[@zoeavo]

You are a great man！

[@BryanPosso]

What if the increment needed is h = 2s-1 so that s = floor[ lgn]. Do we just change the interval to "interval = interval * 2 -1" and at the end "interval = (interval - 1)/2? Thank you!

[@sesharaoparitala144]

It's now working with appropriate closure import java.util.Arrays; public class ShellSort { public void sort() { int inner, outer, temp; int interval = 1; 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(" "); } } }

[@thekingzeroni]

தோல்வி ... உங்கள் வீடியோக்கள் அன்பு, நீங்கள் ஒரு பெரிய வேலை செய்கிறார்கள்.

[@SP-it5qz]

Derek thanks once again. which gap sequence you have have used here?

[@derekbanas]

Thank you :)

[@zachgosteady]

Using the the exact code in your sample link I end up with an infinite loop...please let me know if the same happens for you! Thanks btw for the videos

[@derekbanas]

zachgosteady Your welcome :) If you are using my code you must be inputting data that is causing the infinite loop. What is your input?

[@zachgosteady]

Derek Banas so this is the exact link I am using: www.newthinktank.com/2013/03/java-shell-sort/#viewSource and the input is what is provided in the main function, which is '...new ShellSort(10);' additionally, there is a closing '}' missing around line 92, and I'm not sure where to add it to make the program run correctly!

[@derekbanas]

zachgosteady Sorry, but I'm not getting an infinite loop :(

[@zachgosteady]

Well that's frustrating! This is the exact code I am using from your site: pastebin.com/UqsR6Exx Could you please check the code on your website at www.newthinktank.com/2013/03/java-shell-sort/ for line 92, I think it is missing '}'

[@elizabethcain1058]

I am also getting infinitive loop, this never becomes false interval = interval * 3 + 1; // Keep looping until the interval is 1 // Then this becomes an insertion sort while (interval > 0) {

[@MexterO123]

How does the shell sort end if the outer most while loop never be false? I just realized that. By outer most I mean while(h

[@hai5731]

is it normal for it to take 3 years(long time) just to finish the progran

[@EFT202020]

Love these :D

[@rishiswethan7865]

Hi sir, I owe you a very big thank you for your videos! I'm curious to know how you made those awesome graphs and animations in this video! and can this be used to demonstrate path finding algorithms like A*, etc? If not, kindly suggest me one that I can use for it. I'm a windows user. Thanks!

[@derekbanas]

You are very welcome :) I'm glad I could help. I actually made that program. Here is the code p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Menlo} p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Menlo; min-height: 13.0px} p.p3 {margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Menlo; color: #0433ff} p.p4 {margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Menlo; color: #008f00} span.s1 {font-variant-ligatures: no-common-ligatures; color: #0433ff} span.s2 {font-variant-ligatures: no-common-ligatures} span.s3 {font-variant-ligatures: no-common-ligatures; color: #b4261a} span.s4 {font-variant-ligatures: no-common-ligatures; color: #000000} span.Apple-tab-span {white-space:pre} 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 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; } }

[@azetair1]

i would like to know how and what peices of the code should i alter to have the merger sort reorder the array from low to high instead of high to low.

[@osamaasif9601]

Mr.Derek , what is the name of the software , your using to make the presentation.

[@derekbanas]

+Osama Asif Hi, I record with Camtasia 2 and edit with iMovie.

[@t3kang]

Thanks dude

[@derekbanas]

You're welcome :)

[@MegaVuhung]

line 33: i don't understand why "inner > interval - 1"?What is it effect? can u explain that to me plz!

[@MegaVuhung]

got it! thks man

[@joecoke6925]

I wish you didn't edit out your pauses, especially for difficult concepts that require contemplation. My human brain expects those pauses and your presentation style really makes the learning more difficult. It makes you sound really smart though, so there's that I guess.

[@derekbanas]

Sorry about the speed. I'm recovering algorithms soon with Python and I'm making those tutorials slower

[@totally_not_a_troll]

Isn't quick sort painfully slow ?

[@abdimohamud9951]

no.

[@totally_not_a_troll]

***** I was tongue in cheek, it's a horribly slow sort if you hit it's worse case scenario (O(n2))

[@zkfdsldfjsdjfl1]

The first loop is unnecessary

[@lichaytiram9246]

o(n^3) ins't fast sorting

[@laurynas.k]

At some point when you are typing and explaining really brilliant tutorial, but at another point when you are just saying that all source code are available in link below, then it is really terrible tutorial in a bad way...

[@squirrelbrains2197]

seems fancier than needed.