-
data structure usage
I have some basic doubts with data structure usage.
Please confirm if my below understanding is correct.?
Link List can be used to frequently need to add and remove elements from the middle of a list, and you will not read it very frequently
Queue will be frequently adding and removing items from front and back of a list
Array will be used when you have a list will never change size and you will swap items within it frequently
HashMap is used when you will be looking for specific unique items frequently
A list is sorted except for one item which is in wrong place.
Bubble sort is used here.
-
When one item in the list is in wrong place, should I use Merge sort or Bubble sort considering the time complexity of sort algo?
-
Well it barely counts as a 'sort' since you only ever do one pass to move/insert the item in the correct place.
Plus you stop when you find the place where the item is supposed to go.
-
do you mean to say that we should not use sort algo in this case? If so, how can we solve this?
-
One pass through the outer loop of a bubble sort looks remarkably similar to the linear search through a linked list.
Try looking at the code for both side by side.
-
You say that one item is in the wrong place. Is that known? In other words, are you trying to solve a problem that guarantees that exactly one item is in the wrong place? Because that is different than just "which sort algorithm would perform better when given a list that has only one item out of place?"
If you are trying to solve a single-insert problem, write a single-insert function. For example, if you are maintaining a list in sorted order, and trying to implement an insert operation by calling append() and then sort(), you should just bite the bullet and write a dedicated insert().
On the other hand, if you're wondering about sort performance in a special case, walk through the code. The performance for moving a "front" item from the back of the list is likely to be different than the performance for moving a "back" item from the front of the list.
-
do you mean to say that we should not use sort algo in this case? If so, how can we solve this? The issue here is that there is a list which is sorted already, except for one item which is in wrong place.