Linked List Sorting

This is a discussion on Linked List Sorting within the C Programming forums, part of the General Programming Boards category; Is it more efficient to sort an linked list after the values have been inserted into the list OR to ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Location
    Buea Cameroon
    Posts
    64

    Linked List Sorting

    Is it more efficient to sort an linked list after the values have been inserted into the list OR to sort and item before inserting into the list so as to create an ordered list.
    I am asuming the worst case senario for the items to be sorted.

    And also Please what is the most efficient data Structure to use for Random insertion and searching of unordered Data?
    Last edited by acho.arnold; 05-17-2013 at 02:48 AM.

  2. #2
    Registered User
    Join Date
    May 2012
    Posts
    333
    Quote Originally Posted by acho.arnold View Post
    Is it more efficient to sort an linked list after the values have been inserted into the list OR to sort and item before inserting into the list so as to create an ordered list.
    I am asuming the worst case senario for the items to be sorted.
    This question isn't well posed. If the values are initially stored in an array, it will be easier to sort them first using a highly efficient qsort() provided by your implementation. But a mergesort is O(N log N) and can be implemented for a linked list.

    And also Please what is the most efficient data Structure to use for Random insertion and searching of unordered Data?
    A tree. If we are storing strings (for the sake of argument), we split the strings into two roughly equal groups, A-M on one side, N-Z on the other. You do that recursively until at the leaves you have only one string. So you can quickly find any string, and you can insert data by going to the right leaf and splitting it.
    However the problem is that inserts are seldom truly random, and so trees tend to become unbalanced and the system breaks down as the tree turns into what is effectively a linked list. There are many ways of preventing this, but the question of which is best is a complicated one.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    http://www.malcolmmclean.site11.com/www

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    1,290
    Quote Originally Posted by acho.arnold View Post
    Is it more efficient to sort an linked list after the values have been inserted into the list OR to sort and item before inserting into the list so as to create an ordered list.
    Depends on the size of the data elements and the number of elements. If you're just sorting the data values in the list, you could create an array of pointers to the data values and use that sort the data, with just about any sort algorithm.

    Quote Originally Posted by acho.arnold View Post
    What is the most efficient data Structure to use for Random insertion and searching of unordered Data?
    Again, it depends on the size of the data elements and the number of elements. You could just use a flat array and use memmove to move a portion of the array upwards in order to insert data. If data isn't continously being added and/or removed from the set of data, then you could just wait until all of the data is stored in the array, then sort the array. Doing a binary search on a sorted array is normally the fastest method for searching unless data element size is so small that you can use it as an index.

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,280
    Is it more efficient to sort an linked list after the values have been inserted into the list OR to sort and item before inserting into the list so as to create an ordered list.
    O_o

    You can't search a simple linked list at speed.

    What are you doing that you need the list sorted?

    If it is simple iteration, what are you doing more of: adding elements or iterating over elements?

    If you are doing operations in sufficiently large sets, having two data structures is probably going to be more efficient.

    So, here we are, if you want the "best fit" for your situation, you have to explain your situation and not just tell us what you'd like to use.

    And also Please what is the most efficient data Structure to use for Random insertion and searching of unordered Data?
    O_o

    There really is no such data structure as "most efficient" for both random insertion and searching unordered data.

    The data structures available with particularly efficient searching impose ordering or have a high random insertion cost.

    The tree recommended by Malcom McLean imposes order on the data so that searching can be particularly efficient.

    The array recommended by rcgldr imposes no such order but has poor random insertion performance.

    As before, you'll have to give more information to get intelligent recommendations.

    Soma

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    Inserting each item in order as you go is O(n*n), so to beat that when sorting after items have just been appended in random order, all you need is a sorting algorithm that is better than O(n*n).
    Merge Sort would do it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by iMalc View Post
    Inserting each item in order as you go is O(n*n)
    Err..why would inserting an element in a sorted linked list need quadratic time ?
    Or were you talking about an array ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  7. #7
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,280
    O_o

    The assumption is rather "O(n * m)" where "n" is the number of elements to inspect and "m" is the number of items added.

    Assuming the worst case, you have to inspect every element of the list to figure out where to insert the new item.

    That said, he isn't necessarily correct anyway because we don't know what the original poster is doing.

    The algorithm, as he referenced, is "O(n * m)" which keeps the list sorted as elements are added, but we don't know what is a requirement versus the actual process.

    That's a problem because using Merge Sort as suggested could be "O(m * n * log n)" if the process is naive.

    Soma

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,290
    Quote Originally Posted by phantomotap View Post
    The array recommended by rcgldr imposes no such order but has poor random insertion performance.
    I was suggesting a sorted array, so there is order (to allow binary search), and as you mentioned insertion cost is high, except that memmove that I recommended for insertion is fairly fast and cache will help here.

    Quote Originally Posted by iMalc View Post
    Inserting each item in order as you go is O(n*n)
    Quote Originally Posted by manasij7479 View Post
    Why would inserting an element in a sorted linked list need quadratic time ? Or were you talking about an array ?
    I think this was in reference to my suggestion of using a sorted array and inserting so that the array remains sorted.

    Quote Originally Posted by phantomotap View Post
    we don't know what the original poster is doing.
    This the main issue.
    Last edited by rcgldr; 05-17-2013 at 05:29 PM.

  9. #9
    Registered User
    Join Date
    May 2012
    Posts
    333
    Quote Originally Posted by rcgldr View Post
    I was suggesting a sorted array, so there is order (to allow binary search), and as you mentioned insertion cost is high, except that memmove that I recommended for insertion is fairly fast and cache will help here.

    I think this was in reference to my suggestion of using a sorted array and inserting so that the array remains sorted.

    This the main issue.
    Inserting an element in order into a flat array is O(N). The constant can be pretty low because memmove is usually very efficiently implemented, but you've still go N operations.
    Inserting into a balanced search tree is O(log N). So even when N gets into the billions, it's still only 30 or so operations. Which is why a balanced search tree is the standard answer to this problem. However it's a lot more difficult to implement than the memmove method.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    http://www.malcolmmclean.site11.com/www

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,280
    I was suggesting a sorted array, so there is order (to allow binary search), and as you mentioned insertion cost is high, except that memmove that I recommended for insertion is fairly fast and cache will help here.
    No, in this case `memmove' isn't "fairly fast" because I was referencing complexity.

    The speed of `memmove' isn't relevant if you need to copy 100 elements, then 101, then 102, and so on until you've added every new element.

    Soma

  11. #11
    Registered User
    Join Date
    Apr 2013
    Posts
    1,290
    Quote Originally Posted by Malcolm McLean View Post
    Inserting an element in order into a flat array is O(N). The constant can be pretty low because memmove is usually very efficiently implemented, but you've still go N operations. Inserting into a balanced search tree is O(log N). So even when N gets into the billions, it's still only 30 or so operations. Which is why a balanced search tree is the standard answer to this problem. However it's a lot more difficult to implement than the memmove method.
    The unknown here is the number of insert operations versus the number of search operations. The sorted array would be targeting the case where the program is mostly doing searches, but at this point we don't know what the original poster is trying to implement.

    One interpretation of the original post, is that there is an existing set of data that is to end up as a sorted linked list. In this case, it would be faster to sort the data first, then put it into a sorted linked list. For the linked list part, rather than using the conventional method of appending nodes to a list, an array of nodes could be allocated, and the pointers filled in via iteration.
    Last edited by rcgldr; 05-17-2013 at 06:35 PM.

  12. #12
    Registered User
    Join Date
    May 2012
    Posts
    333
    Quote Originally Posted by phantomotap View Post
    No, in this case `memmove' isn't "fairly fast" because I was referencing complexity.

    The speed of `memmove' isn't relevant if you need to copy 100 elements, then 101, then 102, and so on until you've added every new element.

    Soma
    It's N squared (1 + 2 + 3 + 4 etc equals N^2 / 2 + N/2). N can never go larger than your total memory.
    So if N is 1,000, then that means a million operations, which at say 1 billion operations per second means 1 millisecond, very likely to be acceptable. If N is a million, that means 1000 billion operations, or 1000 seconds, or about 17 minutes, which users will certainly notice. It all depends on N.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    http://www.malcolmmclean.site11.com/www

  13. #13
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,280
    So if N is 1,000, then that means a million operations, which at say 1 billion operations per second means 1 millisecond, very likely to be acceptable. If N is a million, that means 1000 billion operations, or 1000 seconds, or about 17 minutes, which users will certainly notice. It all depends on N.
    O_o

    That's a very foolish way of considering algorithms. The purpose of complexity notations is that they allow us to choose reasonably between algorithms and data structures without considering everything in place. We, of course, should test everything in place, but that isn't a common practice. One does not reach for an array by default when considering randomly inserted values for the same reason we don't reach for a trivial "Quick Sort" when we know our data is already mostly sorted. The primary consideration is of the growth factor versus "n" and not of any specific "n". The problem is that your list of examples lacks a growth factor specific example, but I'll provide one for you using your mathematics: 31623 takes only a second whereas 63246 would take four seconds. Using a balanced tree, and your same trivially applied mathematics, you get: 31623 in one second whereas 63246 takes only a single operation more than needed for 31623.

    The complexity is your primary consideration. You may best concern yourself with refinements to the implementation after an appropriate algorithm is chosen. Let's say you, for example, have a `memmove' which costs a more purposeful eleven ticks per element, you may get your 100,000 element array updated over "n" in about two seconds versus ~93000 in the same time for a sloppy implementation of thirteen ticks per element. (That small improvement is provided by the assumption of a good standard library which I'm sure may be provided.) The growth factor of alternative strategies makes this improvement, the "fairly fast" suggestion of `memmove', meaningless.

    So, no, my comment holds and doesn't depend on "n" in any way.

    Here, let me show you. The approach recommended by rcgldr may be the correct one; he directly referenced the conditions on the size and number of elements. (We don't know, but that's not relevant to this post.) If the suggestion by rcgldr turns out to be appropriate, it will indeed be because the size and number of elements are within "spec" and not because `memmove' is "fairly fast" as the speed of `memmove' can not possible make up the huge difference in growth factor between the array or tree based implementations.

    Soma

  14. #14
    Registered User
    Join Date
    May 2012
    Posts
    333
    Quote Originally Posted by phantomotap View Post
    O_o

    That's a very foolish way of considering algorithms. The purpose of complexity notations is that they allow us to choose reasonably between algorithms and data structures without considering everything in place. We, of course, should test everything in place, but that isn't a common practice. One does not reach for an array by default when considering randomly inserted values for the same reason we don't reach for a trivial "Quick Sort" when we know our data is already mostly sorted. The primary consideration is of the growth factor versus "n" and not of any specific "n". The problem is that your list of examples lacks a growth factor specific example, but I'll provide one for you using your mathematics: 31623 takes only a second whereas 63246 would take four seconds. Using a balanced tree, and your same trivially applied mathematics, you get: 31623 in one second whereas 63246 takes only a single operation more than needed for 31623.

    The complexity is your primary consideration. You may best concern yourself with refinements to the implementation after an appropriate algorithm is chosen. Let's say you, for example, have a `memmove' which costs a more purposeful eleven ticks per element, you may get your 100,000 element array updated over "n" in about two seconds versus ~93000 in the same time for a sloppy implementation of thirteen ticks per element. (That small improvement is provided by the assumption of a good standard library which I'm sure may be provided.) The growth factor of alternative strategies makes this improvement, the "fairly fast" suggestion of `memmove', meaningless.

    So, no, my comment holds and doesn't depend on "n" in any way.

    Here, let me show you. The approach recommended by rcgldr may be the correct one; he directly referenced the conditions on the size and number of elements. (We don't know, but that's not relevant to this post.) If the suggestion by rcgldr turns out to be appropriate, it will indeed be because the size and number of elements are within "spec" and not because `memmove' is "fairly fast" as the speed of `memmove' can not possible make up the huge difference in growth factor between the array or tree based implementations.

    Soma

    The big O notation is the most important part of the picture, but it's not the whole picture. You also need to know N. If N is always tiny, then even O(2^N) isn't going to be much slower than O(log N). You need to know N, the constant, and other factors, such as ease of implementation.
    In the sorted list under random inserts case, a red black tree is O(log N) for an insert and O(log N) for a sort, an array O(N) for an insert. But code complexity is far far greater than for the array solution, and the constant is pretty high. You probably won't see any speed advantage at all until about N = 100. Then up to N = 1000 or so, the O(N^2) method will still come back in under just noticeable time. Sometimes a process which takes a tenth of a millisecond is a thousand times better than one which takes a tenth of a second, sometimes it merely saves a tenth of a second. Which is the case depends on how your function is being used.
    But as N gets big, the naive method becomes increasingly unviable, so we need to abandon simple code and get the big O complexity down.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    http://www.malcolmmclean.site11.com/www

  15. #15
    Registered User
    Join Date
    Apr 2013
    Posts
    1,290
    Quote Originally Posted by phantomotap View Post
    The approach recommended by rcgldr may be the correct one; he directly referenced the conditions on the size and number of elements. (We don't know, but that's not relevant to this post.)
    The other condition for the array to be a good choice, is if the great majority of operations are search operations with relatively few insert operations. The array makes most sense if all the data is available from the start, in which case it's sorted at the start, and afterwards the sorted data is just searched (used like a dictionary or spelling checker). The key issue is we don't know what the original poster needs, so all of this is speculation. Perhaps the original poster just wants a linked list sort as a learning exercise, as opposed to trying to solve a particular problem.

Page 1 of 4 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting a linked list
    By Anass in forum C Programming
    Replies: 7
    Last Post: 10-27-2010, 06:56 AM
  2. Linked List Sorting
    By oddworld in forum C Programming
    Replies: 4
    Last Post: 04-27-2007, 10:42 PM
  3. Sorting a linked list
    By thoseion in forum C Programming
    Replies: 6
    Last Post: 11-13-2006, 09:34 AM
  4. sorting linked list
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-04-2001, 10:08 PM
  5. Sorting a linked list
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 09-18-2001, 04:49 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21