Thread: Insertion sorting programs

  1. #1
    Registered User
    Join Date
    Apr 2012
    Location
    Florida, Dade County, Homestrad, 33031
    Posts
    40

    Insertion sorting programs

    Hi all,
    My next project in my self-teaching of C++ is sorting programs. I have chosen -- Selection sort -- as my teaching device.

    I've chosen this code for a simple selection sort because I think it will serve me better than what I have.

    Code:
    for(int x=0; x<n; x++)
    
    {
    
        int index_of_min = x;
        for(int y=x; y<n; y++)
        {
            if(array[index_of_min]>array[y])
            {
                index_of_min = y;
            }
        }
    
       int index_of_min = x;
        for(int y=x; y<n; y++)
        {
            if(array[index_of_min]>array[y])
            {
                index_of_min = y;
            }
        }
    I understand that the for loop
    Code:
    for(int x=0; x<n; x++)
    can be both x < n, and x > n, thus going from big to small and from small to big. Thus, I can use the same sorting program to find numbers that have the highest frequency and the lowest.


    Code:
      int index_of_min = x;
        for(int y=x; y<n; y++)
        {
            if(array[index_of_min]>array[y])
            {
                index_of_min = y;
            }
        }
    *int index_of_min = x* is a horse of a different color. I understand that it is an "int" and that x is equal to the index.
    I also think it is a part of an int array. . . beyond that, I know it not. I don't know what it represents.

    *for(int y=x; y<n; y++)* I understand that it is a standard nested for loop, and that y<n can also be y>n.

    Code:
     if(array[index_of_min]>array[y])
    All I know about this is that there are two arrays-- [index_of_min] and [y]
    beyond that I do not know how to use it.

    Code:
    index_of_min = y;
    I know as a simple assignment.

    Can someone please give me an example of how to use it? Let's say that I have a file that contains 5 int elements that needs sorting
    (23, 75, 2, 9, 44) and let's say the file's name is "cow_one." How could I use this to sort this file?

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Firstly, your code is incorrect. You have somehow "doubled up" on the inner loop and left out the swap. So the code should be
    Code:
    for(int x=0; x<n; x++)
    {
        int index_of_min = x;    // start index_of_min at x
        for(int y=x+1; y<n; y++) // start inner loop at element just after x
        {
            if(array[index_of_min]>array[y]) // comparison
            {
                index_of_min = y;
            }
        }
    
        // Swap array[x] and array[index_of_min]
        int temp = array[x]
        array[x] = array[index_of_min];
        array[index_of_min] = temp;
    }
    Note the simple logic of the algorithm. Just keep looking through the array for the smallest number (then the next smallest and so on). When you find it, swap it into its correct position.

    I understand that the for loop
    for(int x=0; x<n; x++)
    can be both x < n, and x > n, thus going from big to small and from small to big.
    Nope. To sort in the opposite manner you leave that loop (and the nested loop) as is. You simply change the sense of the comparision operation (and the name of the variable to index_of_max, although the compiler doesn't care about that) :
    Code:
            if(array[index_of_max]<array[y])
    As for using it, try putting it into a function, making a main, opening your file, reading its contents into an array and calling your sort function.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Take more time to understand how a for loop works.
    This for loop:
    Code:
    for(int x=0; x<n; x++)
    {
        /*Stuff*/
    }
    is equivalent to this while loop:
    Code:
    int x=0;
    while (x<n)
    {
        /*Stuff*/
        ++x;
    }
    (assuming no continues are involved)

    So, how can you think it would make any sense to put x>n in there? In order to even enter the loop, n would have to be negative, since x starts at zero.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Insertion sorting strings.
    By mgracecar in forum C Programming
    Replies: 4
    Last Post: 04-10-2012, 07:36 PM
  2. Replies: 1
    Last Post: 11-09-2009, 07:03 AM
  3. How do i use Insertion for sorting?
    By kenny3b in forum C++ Programming
    Replies: 2
    Last Post: 03-29-2003, 10:48 AM
  4. Sorting words with a fast, effincient sorting method
    By Unregistered in forum C++ Programming
    Replies: 19
    Last Post: 07-12-2002, 04:21 PM
  5. Sorting by Insertion
    By Bada Bing in forum C Programming
    Replies: 3
    Last Post: 11-17-2001, 11:22 AM