About insertion sort and especially why it's said that copy is much faster than swap?

Posted by Software Engeneering Learner on Programmers See other posts from Programmers or by Software Engeneering Learner
Published on 2012-11-14T14:01:44Z Indexed on 2012/11/14 17:29 UTC
Read the original article Hit count: 318

Filed under:

java

|

learning

|

algorithms

|

sorting

From Lafore's "Data Structures and Algorithms in Java": (about insertion sort (which uses copy + shift instead of swap (used in bubble and selection sort)))

However, a copy isn’t as time-consuming as a swap, so for random data this algo- rithm runs twice as fast as the bubble sort and faster than the selectionsort.

Also author doesn't mention how time consuming shift is.

From my POV copy is the simplest pointer assignment operation. While swap is 3x pointer assignment operations. Which doesn't take much time. Also shift of N elemtns is Nx pointer assignment operations.

Please correct me if I'm wrong.

Please explain, why what author says is true? I don't understand.

© Programmers or respective owner

Related posts about java

Tomcat 6: Access Control Exception?

as seen on Server Fault - Search for 'Server Fault'
I'm trying to setup a tomcat6 server, and I'm trying to match another setup someone else established. However, my deployment (default Ubuntu install) uses a policy.d/ directory structure, and the established server just uses a catalina.policy file. I've tried setting every entry in policy.d to match… >>> More
Problem in creation MDB Queue connection at Jboss StartUp

as seen on Stack Overflow - Search for 'Stack Overflow'
I am not able to create a Queue connection in JBOSS4.2.3GA Version & Java1.5, as I am using MDB as per the below details. I am putting this MDB in a jar file(named utsJar.jar) and copied it in deploy folder of JBOSS, In the test env. this MDB works well but in another env. [ env settings and… >>> More
failing to establish connection between Postgres db and gwt

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I am using Postgres and gwt 2.0 for one of my applications. I am facing problem connecting to the database. When I try to connect it gives "ClassNotFoundException". Here is what I get when I try to connect to database: java.lang.ClassNotFoundException: org.postgresql.Driver at java.net… >>> More
failing to establish connection between postgre db and gwt

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, For i am using postgre and gwt 2.0 for one of my applications. I am facing problem connecting to the database. When i try to connect it gives "ClassNotFoundException". Here is what i get when i try to connect to database: java.lang.ClassNotFoundException: org.postgresql.Driver at java.net… >>> More
Migration and deployement problems JBoss 4.2.2.GA to JBoss 6.0.0.M2

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I'm trying to migrate an application running on JBoss 4.2.2.GA to JBoss 6.0.0.M2 I give you some log to explain my problem : boot.log : 2010-03-16 09:59:29,406 ERROR [org.jboss.system.server.profileservice.ProfileServiceBootstrap] (Thread-2) Failed to load profile: Summary of incomplete deployments… >>> More

Related posts about learning

Machine learning challenge: diagnosing program in java/groovy (datamining, machine learning)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi All! I'm planning to develop program in Java which will provide diagnosis. The data set is divided into two parts one for training and the other for testing. My program should learn to classify from the training data (BTW which contain answer for 30 questions each in new column, each record in… >>> More
what's a good language for learning machine learning?

as seen on Stack Overflow - Search for 'Stack Overflow'
I've been thrust into a situation where I need to know something about Machine Learning. Is there a language or perhaps a reasonable tutorial that breaks this subject matter in gently? I'm not a math guy, so it's got to start from a pretty basic level. >>> More
Learning WPF and MVVM - best approach for learning from scratch

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I've got about three years c# experience. I'd like to learn some WPF and the MVVM pattern. There are a lot of links to articles on this site but I'm getting a little overwhelmed. Would a sensible approach for a begginer to be forget mvvm for a while and just quickly learn a bit a of WPF, then… >>> More
What are the advantages of Ceylon over Java?

as seen on Programmers - Search for 'Programmers'
Looking for the recent and powerful upcoming programming languages over net, I came across Ceylon. I dropped in at ceylon-lang.org and it says: Ceylon is deeply influenced by Java. You see, we're fans of Java, but we know its limitations inside out. Ceylon keeps the best bits of Java but improves… >>> More
understanding evaluation function

as seen on Programmers - Search for 'Programmers'
I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the… >>> More