Solved

insertion sort

Posted on 2003-11-09
12
193 Views
Last Modified: 2010-03-31
hi i'm looking for the code for an insertion sort.  it only needs to deal with a small array of integers. for example 6, 7, 4, 2, 1 . if i anyone can help i'd greatly appreciate it... thanks!
0
Comment
Question by:mitchweb1
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
  • 2
  • +1
12 Comments
 
LVL 15

Expert Comment

by:JakobA
ID: 9710458
Sorry, that question stink of school homework, If you show the code you have made sofar we may be able to give usefull comments on how to improve it.

regards JakobA
0
 
LVL 5

Expert Comment

by:lwinkenb
ID: 9710685
If you are just looking for a fast way to sort an array, then use the built in quicksort.
int[] myArray = {6,7,4,2,1};
Arrays.sort(myArray);

And if you are writing an insertion sort for homework, then post your code so we can help :)
0
 

Author Comment

by:mitchweb1
ID: 9710876
nah doing some research into the different types of sorts, but not over familiar with the java language.

here is the code i've written, the problem is that it checks if i < i-1 and if so swaps, but then it increments i. i can't find how to compare whether the new value of i-1 is less than the value of i -2. thanks in advance

class insertion
{
  public static void main(String[] args)
  {
    int[] num= {3, 1, 6, 6, 9, 7, 5, 8, 9, 4};
      int i = 1;

      while (i<num.length) {
            int j = num[i];
            int k = num[i-1];

      if (num[i] < num[i-1]) {
            num[i] = k;
            num[i-1] = j;
                              }
            i++;

}

System.out.println(" "+num[0]+num[1]+num[2]+num[3]+num[4]+num[5]+num[6]);

}

}
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 15

Expert Comment

by:jimmack
ID: 9710918
This isn't the way an insertion sort works.

Insertion sort
------------------
"Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted."  - National Institute of Standards and Technology.

In order to achieve this in an array, you'll need to be doing lots of looping:

1) Start at the second int (assuming the first int on it's own is sorted ;-)) call this toBeSorted
2) Initialise a sortedItems count to 1
3) While more ints remain in the array
3.1)  Read the value at the index sortedItems
3.2)  Loop through existing data until an int is found that is less than the current int or the index equals sortedItems
3.3)  Take a temporary copy of the int that has been found (call this toBeMoved)
3.4)  Write toBeSorted into this location
3.5)     While current index < sortedItems count
3.5.1)      Take a temporary copy of the next item
3.5.2)       Write toBeMoved to this location

When the loop (3.5) gets to the end of the sortedItems count, it should overwrite the value that has just been inserted into the array.

Just a quick note:

To display the complete array at the end, replace the System.out.println with:

for (int x = 0; x < num.length; x++)
{
    System.out.print(num[x] + " ");
}
System.out.println();
0
 

Author Comment

by:mitchweb1
ID: 9710956
i may be wrong, but i believe that the insertion sort puts values into the right positions by comparing the new number with the one before it.
i.e
4 2 7 3 9 1 6 would start with second integer so
2 4 7 3 9 1 6 then the third, which is already higher than second, so move onto fourth which is 3 and is so less than 7
2 4 3 7 9 1 6... it is at this point my code doesn't do what i wish it to. it should now compare third with second
2 3 4 7 9 1 6 and so on

so any data before a chosen integer has already been sorted as in your quote

(think i'm more confused than ever)
0
 
LVL 15

Accepted Solution

by:
jimmack earned 100 total points
ID: 9710968
There is another way to do this which is a little like the way you are describing.

"Sorting can be done in place by moving the next item past the end of the sorted items into place by repeatedly swapping it with the preceding item until it is in place - a linear search and move combined."  - NIST

From your sequence, this would mean:

4   2   7   3   9   1   6

sorting 2 (index 1)
2 - 4   7   3   9   1   6

sorting 7 (index 2)
2   4   7   3   9   1   6

sorting 3 (index 3)
2   4   3 - 7   9   1   6
2   3 - 4   7   9   1   6

sorting 9 (index 4)
2   3   4   7   9   1   6

sorting 1 (index 5)
2   3   4   7   1 - 9   6
2   3   4   1 - 7   9   6
2   3   1 - 4   7   9   6
2   1 - 3   4   7   9   6
1 - 2   3   4   7   9   6


sorting 6 (index 6)
1   2   3   4   7   6 - 9
1   2   3   4   6 - 7   9
0
 
LVL 15

Assisted Solution

by:JakobA
JakobA earned 100 total points
ID: 9710994
take care to get your indentation correct and informative.

usually it is better to remember indexes than it is to remember the values those indexes point to.

     while (i<num.length) {
          int temp = num[i];        // value to be inserted
          int k = i-1;                    // index of first value to be compared to
          while ( k >= 0 && temp < num[k] ) {
               num[k+1] = num[k];  // move bigger values up one cell
               k--;                           //
          }
          num[k+1] = temp;      // insert this value in its proper place
          i++                            // and get ready for the next
     }

regards JakobA
0
 
LVL 15

Expert Comment

by:JakobA
ID: 11646720
>> Venabil
    Is there a tool/trick to make those short links to specific entries in the thread? They are nifty.
0

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Problem to Alipay 10 94
Java syntax, or is it Selenium 6 61
Eclipse for Java EE development 2 68
How to fix  socket closed error 11 64
INTRODUCTION Working with files is a moderately common task in Java.  For most projects hard coding the file names, using parameters in configuration files, or using command-line arguments is sufficient.   However, when your application has vi…
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
Suggested Courses

739 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question