Programming Help

Web Development



What's Here?

  • Members: 137,271
  • Replies: 481,724
  • Topics: 75,094
  • Snippets: 2,568
  • Tutorials: 677
  • Total Online: 1,448
  • Members: 88
  • Guests: 1,360

Welcome to Dream.In.Code
Become a C++ Expert!

Join 137,271 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 1,448 people online right now. Registration is fast and FREE... Join Now!




Need help with using memmove for insertionsort

 
 Reply to this topicStart new topic

Need help with using memmove for insertionsort, I'm a newie to this and I can't figure it out.
adp
30 Nov, 2006 - 06:15 PM
Post #1

New D.I.C Head
*

Joined: 30 Nov, 2006
Posts: 1


My Contributions
This is the code I have:
CODE

template <class T>
void insertionSort(T* a, int size)
{
  for (int i = 1; i < size; i++)
  if (a[i] < a[i - 1])
  {
    T temp = a[i];
    int j = i;
    do
    {
      a[j] = a[j - 1];
      --j;
    } while (j > 0 && temp < a[j - 1]);
    a[j] = temp;
  }    
}

I need to use memmove to shift values in a single call per outer loop cycle rather than performing multiple assignments in its inner loop.

Any Suggestions? I'm desperate.
User is offlineProfile CardPM
+Quote Post

Videege
RE: Need Help With Using Memmove For Insertionsort
30 Nov, 2006 - 07:24 PM
Post #2

rêvant.toujours
Group Icon

Joined: 25 Mar, 2003
Posts: 1,406


Dream Kudos: 150
My Contributions
I'm not entirely sure this will work (I'm fried from tests right now biggrin.gif), but try this:

memmove simply copies memory from one area to another, a la

void *memmove(void *dest, const void *src, size_t n);


Instead of reassigning a[j] to a[j-1] in the inner while loop, simply decrement j till the conditions of the loop are met, then copy the memory of the array indice holding temp to a[j] and vice versa.

I must point out that this seems awful C-ish as well as strange, when you could do the same thing and just swap the values normally.
User is offlineProfile CardPM
+Quote Post

msg555
RE: Need Help With Using Memmove For Insertionsort
2 Dec, 2006 - 03:46 AM
Post #3

D.I.C Head
Group Icon

Joined: 4 May, 2006
Posts: 136



Thanked: 2 times
Dream Kudos: 25
My Contributions
Insertion sort can be easily implemented with two for loops to make some pretty sleek code.

CODE
for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++)
        if(a[j] < a[i])
            swap(a[i], a[j]);
User is offlineProfile CardPM
+Quote Post

Xing
RE: Need Help With Using Memmove For Insertionsort
2 Dec, 2006 - 04:09 AM
Post #4

D.I.C Addict
Group Icon

Joined: 22 Jul, 2006
Posts: 723



Thanked: 2 times
Dream Kudos: 1575
My Contributions
@msg555

Are you sure this is Insertion sort?
User is offlineProfile CardPM
+Quote Post

msg555
RE: Need Help With Using Memmove For Insertionsort
2 Dec, 2006 - 08:29 AM
Post #5

D.I.C Head
Group Icon

Joined: 4 May, 2006
Posts: 136



Thanked: 2 times
Dream Kudos: 25
My Contributions
What would you call it then?

At the beggining of the ith iteration of the outer loop the first i elements have been placed in their final positions.
User is offlineProfile CardPM
+Quote Post

Xing
RE: Need Help With Using Memmove For Insertionsort
2 Dec, 2006 - 05:56 PM
Post #6

D.I.C Addict
Group Icon

Joined: 22 Jul, 2006
Posts: 723



Thanked: 2 times
Dream Kudos: 1575
My Contributions
That looks more like bubble sort
See Insertion Sort
User is offlineProfile CardPM
+Quote Post

msg555
RE: Need Help With Using Memmove For Insertionsort
2 Dec, 2006 - 06:15 PM
Post #7

D.I.C Head
Group Icon

Joined: 4 May, 2006
Posts: 136



Thanked: 2 times
Dream Kudos: 25
My Contributions
It's not bubble sort. Just because I did it with two simple for loops doesn't make it bubble sort.

Insertion Sort
CODE
for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++)
        if(a[j] < a[i])
            swap(a[i], a[j]);


Bubble Sort
CODE
for(int i = 0; i < n; i++)
    for(int j = 0; j + 1 < n; j++)
        if(a[j + 1] < a[j])
            swap(a[j], a[j + 1]);
User is offlineProfile CardPM
+Quote Post

Xing
RE: Need Help With Using Memmove For Insertionsort
2 Dec, 2006 - 10:24 PM
Post #8

D.I.C Addict
Group Icon

Joined: 22 Jul, 2006
Posts: 723



Thanked: 2 times
Dream Kudos: 1575
My Contributions
Where is the insertion in your so called insertion sort algorthm?
User is offlineProfile CardPM
+Quote Post

BitByte
RE: Need Help With Using Memmove For Insertionsort
3 Dec, 2006 - 01:34 AM
Post #9

D.I.C Head
**

Joined: 9 Aug, 2006
Posts: 194



Thanked: 2 times
My Contributions
msg55, that is not insertion sort. This is insertion sort:

CODE
for( j = 1; j < arraySize; j++ )
{
    marker = myArray[j];
    
    for( i = j - 1; ( i >= 0 ) && ( myArray[i] < marker ); i-- )
    {
        myArray[i+1] = myArray[i];
    }
    
    myArray[i+1] = marker;  // Insert into correct place.
}


Xing is right, just looks like bubble.
User is offlineProfile CardPM
+Quote Post

msg555
RE: Need Help With Using Memmove For Insertionsort
3 Dec, 2006 - 08:05 AM
Post #10

D.I.C Head
Group Icon

Joined: 4 May, 2006
Posts: 136



Thanked: 2 times
Dream Kudos: 25
My Contributions
Ah, you're right. I guess I need to retake my sorts class. Now that I think about it wouldn't my sort I was calling insertion sort really be selection sort?

Anyway, this is insertion sort right?

CODE
for(int i = 1; i < n; i++)
    for(int j = i; j > 0 && a[j] < a[j - 1]; j--)
        swap(a[j], a[j - 1]);


This post has been edited by msg555: 3 Dec, 2006 - 08:06 AM
User is offlineProfile CardPM
+Quote Post

Reply to this topicStart new topic
Time is now: 12/4/08 07:55PM
Invision Power Board v2.1.7 © 2008  IPS, Inc.
Licensed to: MediaGroup1

Live C++ Help!

C++ Tutorials

Reference Sheets

C++ Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month