C ++ is the fastest way to add an element to a sorted array

Question

I have a database with approximately 200,000 items, which is sorted by username. Now, when I add an element to the end of the array and call the quick sort function to sort this array, it takes about a second to sort, which is unacceptable. Of course, there are certain optimizations that can be done. For example, if I consistently compare each line from n-1 to 0, and then move the elements, then the performance is much greater.

Another idea is that I could do a binary search from 0 to n-1, well, not distort the search, but something similar to using my already sorted array. However, I was not able to write the correct function, which will return the index into which my new element should be placed.

void quick_sort(int left, int right) { int i = left, j = right; if (left >= right) return; char pivotC[128]; DataEntry *tmp; strcpy_a(pivotC, sizeof pivotC, User[(left + right) / 2]->username); while (i <= j) { while (StringCompare(User[i]->username, pivotC)) i++; while (StringCompare(pivotC, User[j]->username)) j--; if (i <= j) { tmp = User[i]; User[i] = User[j]; User[j] = tmp; i++; j--; } } if (left < j) quick_sort(left, j); if (i < right) quick_sort(i, right); } 

Any help is greatly appreciated.

Answer 1

the solution is to rewrite your code to use stl, I do not understand why people write C code in C ++.

You need a user vector

 std::vector<User> users; //then you can keep it ordered at each insertion auto it = upper_bound(users.begin(), users.end(), user_to_insert, [](auto& lhs, auto& rhs ) { /* implementation left to the reader */}); users.insert(it, user_to_insert); 

Now you have the same functionality that is much better and more understandable.

Answer 2

Rethinking the wheel is great if you want to learn how to encode a binary search, otherwise reuse is better.

std::lower_bound performs a binary search in the sorted range [first, last) , returning an iterator to the element x , if it is already present; otherwise, the iterator will point to the first element greater than x . Since the standard containers displaying insert will be inserted before the iterator, this iterator can be used as-is. Here is a simple example.

 #include <algorithm> #include <iostream> #include <iterator> #include <vector> int main() { std::list<int> data = { 1, 5, 7, 8, 12, 34, 52 }; auto loc = std::lower_bound(data.begin(), data.end(), 10); // you may insert 10 here using loc std::cout << *loc << '\n'; loc = std::lower_bound(data.begin(), data.end(), 12); // you may skip inserting 12 since it is in the list (OR) // insert it if you need to; it'd go before the current 12 std::cout << *loc << '\n'; } 

12

12

Answer 3

Binary search will have limited interest, since you still have to embed it, and this will remain time consuming (O (N)). So, your first linear search idea followed by an insert is good enough; You can combine in one reverse cycle. (This is a StraightInsertionSort step.)

Truly effective ways to handle dynamic sorted lists are by maintaining a balanced tree or using a hash table.

Answer 4

A simple, direct method calls binary search too mainstream. Just need a few lines:

 int where_to_add(int array[], int element) { int i; for (i = length; i >= 0 && array[i-1] > element; i--); return i; } 

Let me know if this is the answer you were looking for

Answer 5

You can do a binary search this way. Here you can assume that if val is a string type, then compare it using the string comparison function, and int AR [] is given as a string, or you can match them with an integer. As you sort the array, I think binary search will give you better performance.

 int bsearch(int AR[], int N, int VAL) { int Mid,Lbound=0,Ubound=N-1; while(Lbound<=Ubound) { Mid=(Lbound+Ubound)/2; if(VAL>AR[Mid]) Lbound=Mid+1; else if(VAL<AR[Mid]) Ubound=Mid-1; else return Mid; } return 0; } 

Answer 6

From what I see, you are using the C array to store your records, which means a big penalty in performance with a huge number of records when you try to insert a new record, because you may need to move a lot of records in the array.

If you plan on storing a C array and not using some ordered stl containers (mostly thinking of std :: map, though), you can try splitting your C array into two arrays. One of them will be the first array containing your key and index for the element of the second array. You still need to sort the first array, but its element is only two words (one for the key, one for the index) instead of a large block, including the key and some values) and should be faster. When you insert an element, you select at the end of the second array and force the index to insert it as a pair with a key inside the first array. If you plan on deleting an item dynamically, you may be a little smarter, but your question does not seem to cover it.

But even in this case, it may be too slow, so you should really consider std :: map or some algorithms such as a binary tree using AVL, Red Black tree, Splay tree, etc., where you do not need to physically move element,

Answer 7

If you are sorting a sorted list with only a few new inappropriate details, then you should take advantage of the rare case where insertion sorting really works efficiently. Embedding sorting in a sorted list with a few other place values ​​can sort in O (n) time. You simply insert your few non-local values ​​into place, while quicksort selects a fulcrum and goes through the entire quicksort process. In addition, if you do not include any effective process for choosing a pivot chart in your quick view and go to the “middle of the first three elements” approach in the already sorted list, which you are going to sort in O (n ^ 2).

Answer 8

 int add(Container c, int r, int l, Unit t) { if(c[r]>t) return r; if(c[l]<t) return l+1; if(c[r]==c[l]) { if(c[r]==t) return -1; return -1; } int m=(r+l)/2; if(c[m]==t) return -1; if(c[m]>t) return add(c,m,l,t); if(c[m]<t) return add(c,r,m,t); } 

It will probably give you an index that you need to add ... I hope it can help. It assumes that you do not need to add when it is already located.