1

I need to have sorted array of thousands of records. I put everytime new record on the right place, thus I must change index of the rest of the records in my array. I make in manualy like: 

    db[j]=record;
    cout<<tmp.oName<<endl;
    while (j++!=size-1){
        tmp2=db[j];
        db[j]=tmp;
        tmp=db[j];
    }

And here comes my question: would it be significantly faster to create new array and use copy, or there would be no noticeable computing time and memory usage enhancement beside my current code? I'm quite new to C++, so I'm not sure, how this function internally works.

Includes, I can use:

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
Improve this question
5
  • 2
    You might want a std::(multi)set. It keeps the elements sorted. Commented Mar 28, 2013 at 19:36
  • You might consider if using a sorted container like std::set is possible in your situation. Commented Mar 28, 2013 at 19:37
  • You could also use std::vector::insert to perform this. It will move everything for you. Commented Mar 28, 2013 at 19:39
  • I'd love to, but I'm doing a homework and it's aimed for practicing algorithms, so we are limited on includes.. Commented Mar 28, 2013 at 19:39
  • The reason, why I keep my array sorted is, that the array can be really large and search() will be called much more often than add(), so I need to optimize it for searching the results.. Commented Mar 28, 2013 at 19:49

8 Answers 8

Reset to default
2

If you make a copy of the array then copy to it, it will be slower and use more memory.

Say you have a array with N spots and I is the index where your new item goes. Copying the array means you use N more memory and copy elements N times. If you just shift the records, you use no more memory and perform N-I operations as you only need to shift elements after the new one.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

No it wouldn't be faster to create a new array. It would be faster not to use a bubble sort though. Instead use something like a quick sort. Just google quick sort c++ to see the hundred examples of it out there.

Improve this answer

3 Comments

I know how to implement QS. But I keep my array sorted...I just add 1 record on the right position( i.e. in the middle of my array), thus I need to shift the rest of the array...
@Phil The author needs to maintain a sorted list. Doing qsort everytime you insert an item will cost O(n log n). Shifting all the elements like the author is saying will be O(n).
@OlivierD I understand that. I misunderstood his question originally. His code looked like he was just sorting them again, not adding something to the middle. I should try to read it a little more carefully.
1

It sounds like you are trying to create your own sorted list.

Your current code, which shifts the elements after the insertion, is the best that you can do when inserting into an array. You will only need to create a new array whenever you run out of space in your current array, if you want the capacity of your list to change.

EDIT:

This is one of the costs of using an array based list (as opposed to a linked list) - insertion takes linear time O(N)

Improve this answer

Comments

1

If you need it for real life, use STL qsort (http://www.cplusplus.com/reference/cstdlib/qsort/). If you need it for homework, creating a new array will be costly because of the time to run malloc.

Improve this answer

1 Comment

I don't think this answers the question as asked. He is looking to maintain a sorted list. However, it raises a good poing that inserting in the most efficient way (O(1)), for example at the end, and sorting after will be significantly better performing overall than sorting as you insert.
0

It's better to check out STL data structures in your case.Try heap sort or quick sort, if you can't use STL.

Improve this answer

1 Comment

You better don't use STL. Use Standard C++ Library instead.
0

If you are not allowed to use STL containers and algorithms, you can still put records into vector and then code your own quicksort or merge sort, which is straighforward. Quick sort is more efficient than bubble sort or selection sort.

FYI:

http://www.algolist.net/Algorithms/Sorting/Quicksort

Improve this answer

2 Comments

I can't...look at the comments in my original post.
@Dworza Sorry, did not see your comments when I was writing the answer
0

The code will be much faster if you change your loop to go from the top down to the insertion point instead of from the insertion point up to the top. With that change, you only need to do one copy for each position instead of three.

Improve this answer

Comments

0

As has been mentioned in other posts, inserting within the same array should be faster than copying the whole array everytime.

On the other hand, the way you are describing of inserting is akin to insertion sort. One insert operation will cost you O(n). Using a heap to manage your array will make insertion cost O(log n), but may be slower for small array sizes. See http://en.wikipedia.org/wiki/Binary_heap

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.