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

Printable View

- 05-16-2008MarlonDeanSorting
What sorting method is the easiest to implement? and which is most effiecent?

- 05-16-2008manav
easiest could be Bubble Sort.

Quick Sort or Merge Sort are quite efficient.

what you need to do? - 05-16-2008MarlonDean
input from 2 differnt files (both containing random numbers) into vectors. I need to sort the vector in ascending order

- 05-16-2008laserlight
#include <algorithm> and use std::sort, e.g.,

Code:`std::vector<int> vec;`

// ...

std::sort(vec.begin(), vec.end());

- 05-16-2008MarlonDean
yes, i trying to use my own function to do the sorting so this isn't really appropriate, but thanks for the tip

- 05-16-2008laserlight
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.

- 05-16-2008MarlonDean
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?

- 05-16-2008laserlightQuote:

but can i use merge sort with vectors. This one site speaks of using it with arrays. are the principles still the same?

- 05-16-2008iMalc
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. - 05-16-2008manav
just ask iMac, he is an expert at sorting algorithms :D