selection sort?

This is a discussion on selection sort? within the C Programming forums, part of the General Programming Boards category; I can't tell if this sort I made would still be concidered an insertion sort or some weird bubble sort. ...

  1. #1
    Registered User dharh's Avatar
    Join Date
    Jan 2002
    Posts
    51

    selection sort?

    I can't tell if this sort I made would still be concidered an insertion sort or some weird bubble sort. What would you guys call it?

    Code:
      for(i = 1; i < size; ++i) {
        temp = array[i];
        for(j = i - 1; (j >= 0) && (array[j] > temp); j--) {
          swap(&(array[j]), &(array[j+1]));
        }
        printArray(array, size);
      }
    Last edited by dharh; 03-16-2002 at 04:38 PM.

  2. #2
    Registered User Dave Jay's Avatar
    Join Date
    Mar 2002
    Posts
    33

    insertion sort

    You're doing an insertion sort with extra swapping.

    I'd do this:

    for(i = 1; i < size; ++i) {
    temp = array[i];
    for(j = i; temp > array[j-1] && j > 0; j--) array[j] = array[j-1];
    array[j] = temp;
    }

  3. #3
    Registered User dharh's Avatar
    Join Date
    Jan 2002
    Posts
    51
    I don't see the swap difference between your sort and mine, though I will note that yours sorts in reverse order, you need to switch the temp > array[j-1] to temp < array[j-1].

    like:

    Code:
    for(i = 1; i < size; ++i) { 
      temp = array[i]; 
      for(j = i; temp < array[j-1] && j > 0; j--) array[j] = array[j-1]; 
      array[j] = temp; 
    }

  4. #4
    Registered User Dave Jay's Avatar
    Join Date
    Mar 2002
    Posts
    33
    "I don't see the swap difference between your sort and mine, though I will note that yours sorts in reverse order, you need to switch the temp > array[j-1] to temp < array[j-1]."

    Yes, switch the ">"

    In your algorithm, whenever the element which needs to be inserted has to be compared more than once, you do unnecessary swapping. The algorithm I suggested only swaps at the end.


    With big lists, this will be noticable. Try 10,000 random integers.
    (not saying that this is an optimal sort, just relatively speaking, but good for small lists)

    Dave

  5. #5
    Registered User dharh's Avatar
    Join Date
    Jan 2002
    Posts
    51
    I think I understand now, your not realy ever swaping in an insertion sort. Your just coping elements over eachother. Which only requires temping the to be inserted element, while swaping requires all the elements to be temped during the swap.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Insertion and selection sort
    By Dashing Boy in forum C Programming
    Replies: 4
    Last Post: 08-29-2006, 05:42 PM
  2. Selection Sort problem #2
    By Twigstar in forum C++ Programming
    Replies: 7
    Last Post: 07-11-2005, 08:27 PM
  3. Selection Sort help
    By Twigstar in forum C++ Programming
    Replies: 5
    Last Post: 06-26-2005, 09:39 PM
  4. Selection Sort
    By Bleueyes515 in forum C++ Programming
    Replies: 3
    Last Post: 09-30-2002, 09:33 PM
  5. selection sort records of chars
    By hew in forum C++ Programming
    Replies: 8
    Last Post: 04-23-2002, 04:49 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21