Thread: data structure usage

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    222

    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.

  2. #2
    Registered User
    Join Date
    Nov 2008
    Posts
    222
    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?

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Nov 2008
    Posts
    222
    do you mean to say that we should not use sort algo in this case? If so, how can we solve this?

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Apr 2021
    Posts
    138
    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.

  7. #7
    Registered User
    Join Date
    Nov 2008
    Posts
    222
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Structure usage from Dennis Ritchie's manual
    By goodluck in forum C Programming
    Replies: 1
    Last Post: 01-10-2012, 11:31 AM
  2. difference between data object and data structure?
    By c_lady in forum C++ Programming
    Replies: 2
    Last Post: 02-22-2011, 12:30 PM
  3. Data structure for storing serial port data in firmware
    By james457 in forum C Programming
    Replies: 4
    Last Post: 06-15-2009, 09:28 AM
  4. string::operand+ usage problem (with WIN32 data types)
    By flashbaz-pi in forum C++ Programming
    Replies: 17
    Last Post: 11-02-2008, 02:41 PM
  5. data structure design for data aggregation
    By George2 in forum C# Programming
    Replies: 0
    Last Post: 05-20-2008, 06:43 AM

Tags for this Thread