Sorting 99% ordered list

You can find smallest element in O(1), and you can implement insert/delete in O(logn). Given the limitation of values, you may replace log(n) with appropriate constant and use same estimations.

Yes, you mean heap. But you can't replace insert/delete O(logN) with O(1)

Quote:

---

Originally Posted by vedex

Yes, you mean heap. But you can't replace insert/delete O(logN) with O(1)

---

Who said I'm to?

Quote:

---

Originally Posted by RoboTact

use sorting tree (std::set). You need to delete last element add add new - it would take O(log(n)).

---

of cource just adding and removing an item takes O(logn) but firstly we should make a heap sorted array which takes O(nlogn) then adding and removing items which probabaly takes O(logn)..so because OP should initialy make a sorted array so I think its time is O(nlogn).

You can't sort array in time less then nlogn, so it's useless to discuss this component.

Quote:

---

Originally Posted by RoboTact

You can't sort array in time less then nlogn, so it's useless to discuss this component.

---

Quote:

---

Originally Posted by vedex

I have a question. The author didn't mention what is the range of the values. If it is small a linear time sorting algorithm can be implemented.

---

i don't think so

[Edited Post]

Quote:

---

Originally Posted by RoboTact

use sorting tree (std::set). You need to delete last element add add new - it would take O(log(n)).

---

//not familiar with std::set I just consider a simple array
if we have a sorted tree like this

Code:

---

2
4 6
8 13 16 18
20 22 25 27 30 32 35 37

---

then if we add a new element(for example 23) instead of 37..for keepping the tree sorted again,just a simple percolate is not sufficient,so it doesn't take logn :confused:
I think we should recall the heap-sort function(nlogn). maybe it could be optimized to n but realy can't get how you could get logn?

Take a look at binary heap data structure.

well, I checked that link(I knew them)
if we have this min binary heap(it is sorted)

1
3 5
8 10 14

then if we add a new element for example 2 it becomes

1
3 2
8 10 14 5

well,its clear it takes logn but our min binary heap is not sorted anymore, but we wanted when we add a new element it remains sorted
I hope I could represnt my meaning :o

Just read about that data structure more carefully. It doesn't make sense to just "add" element, violating structure - of course inserting and deleting operations mean adding and deletion of element preserving heap property.