Thread: Sorting

  1. #1
    Village id10t
    Join Date
    May 2008
    Posts
    57

    Sorting

    What sorting method is the easiest to implement? and which is most effiecent?

  2. #2
    Banned
    Join Date
    Nov 2007
    Posts
    678
    easiest could be Bubble Sort.
    Quick Sort or Merge Sort are quite efficient.

    what you need to do?

  3. #3
    Village id10t
    Join Date
    May 2008
    Posts
    57
    input from 2 differnt files (both containing random numbers) into vectors. I need to sort the vector in ascending order

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    #include <algorithm> and use std::sort, e.g.,
    Code:
    std::vector<int> vec;
    // ...
    std::sort(vec.begin(), vec.end());
    Of course, if this is an exercise to learn about sorting then this solution would not be appropriate.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Village id10t
    Join Date
    May 2008
    Posts
    57
    yes, i trying to use my own function to do the sorting so this isn't really appropriate, but thanks for the tip

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Search the Web for "sorting". It is a well studied area of computer science, so you will find alot of information on it, from Java applets to example code to graphs comparing efficiency.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Village id10t
    Join Date
    May 2008
    Posts
    57
    im going to ask a really newbie question, but can i use merge sort with vectors. This one site speaks of using it with arrays. are the principles still the same?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    but can i use merge sort with vectors. This one site speaks of using it with arrays. are the principles still the same?
    Yes. A vector is like an array for this purpose.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by MarlonDean View Post
    What sorting method is the easiest to implement? and which is most effiecent?
    That's like asking what the fastest vehicle is. Anyone can quote high-powered machines back at you but we don't know if you're asking about acceleration or top speed, whether on-road or off-road...? Motorbike, jetboat, car, plane or even space shuttle...?

    There are a few easy ones to implement, but it depends on the data structure. For example Bubble Sort is easy for an array, but it is quite tricky for a linked list. Some algorithms are easy for one data structure but are basically impossible for other data structures.
    Some algorithms may not suit because they don't respect the existing ordering of items that have the same key value, i.e algorithms that are not stable. E.g. Quicksort is typically fast, but is not stable.
    Some algorithms can be efficient time-wise, and reasonably easy to implement, but take too much RAM.
    Even the shape of the distribution of the values, the number of duplicates, and the initial ordering (number of inversions) play an important part in how long the sorting takes.

    If you want to overall easiest to implement I'd say Insertion Sort (works on more data structures). If you want the fastest algorithm for a huge number of items it's probably Pigeonhole Sort. If you want the fastest algorithm for a small number of items then its definitely something else entirely. In practice you usually shouldn't or often even cant, use either of those for what you're sorting, depending on the data type or item count.

    I fully realise that you couldn't know what to ask when you don't know any of the above about sorting. However you've now been made aware that there is no real answer to the general question about sorting speed. Here's some of what we need to know to give you the best answer:
    • What type of data structure - array/list/doubly-linked-list etc?
    • How many items could there be?
    • Will they usually be mostly sorted already?
    • What is the data type?
    • Could there be duplicates?


    Okay you did mention you're sorting a vector later on so that's the first question answered. In case you cant wait for another reply though, Shell Sort and Comb Sort are fairly easy to implement, perform quite well for any number of items, and take no extra memory at all.
    Last edited by iMalc; 05-16-2008 at 01:53 AM.

  10. #10
    Banned
    Join Date
    Nov 2007
    Posts
    678
    just ask iMac, he is an expert at sorting algorithms

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 05:50 PM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM
  5. selection sorting
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-13-2001, 08:05 PM