I have an exercise: do a program that performs an ordered insertion within a vector of integer numbers. The number of elements of the vector is informed by the user (maximum of 30 elements)
Yes it's a homework, and yes, I know it could be easy get the answer. That' not what I want. I want to learn and get better with algorithms in general, I am still uncomfortable with them.
Thanks in advance.
A good approach is to read the description of the sorting algorithm, at Wikipedia. Then go to either google, or YouTube, and watch a graphic, of how the sort proceeds, in slow motion.
Then code it up, and add some print statements inside the loops, along with a sleep() statement, to slow it down, even more.
Then do it by hand, on your desk or table top, with just a few pieces of paper with numbers on them - say 10 numbers, total.
thanks for the answer Adak !Originally Posted by Adak
Sorting is one of those fascinating things in algorithms - and you don't expect that it would be - but it definitely is.
A few notes:
1) Quicksort is the fastest general purpose sorter, but it can be throttled by data that is mostly (or already) sorted. Any effort on your part to partially sort data to speed up sorting by Quicksort, is just shooting yourself in the foot.
2) Although Insertion sort is fairly slow at sorting a large number of items, it *ROCKS* on smaller numbers of items (say, less than 70), and also *ROCKS* on data that is partially sorted (or already sorted).
You can use Insertion sort, to give Quicksort a nice speed up, by calling Insertion sort when the sub-arrays that Quicksort generates (which are partially sorted), are down to less than 70 items.
Insertion sort is frequently used by businesses that continually update (and sort) their data, on-line. Since it is a stable sort (meaning records with equal key values will remain in their original order), and we know it's FAST on data that is already almost sorted, it's a good choice.
3) Shell sort, is a modification of Insertion sort, which allow it to remain very fast, with a larger number of items - say 200k. After that, it bogs down.
4) In studies in actual businesses, data that was already sorted, was re-sorted, rather frequently! XD
5) Computers spend about half their total working time, sorting data.
6) Bucket sort, Heap sort, and Merge sort are some other top choices for sorting.
Heap sort takes just as long to sort data that is already sorted, as it does to sort data that is totally out of order. The order of the data has no effect at all upon it's run-time.
7) Counting sort, doesn't actually sort anything - it just allows you to specify the data, in sorted order. Sorting by pointers to the data, or by a separate integer array of indices, does the same thing, just slower.
Counting sort is the fastest possible "sort" - but frequently can't be used on the data in question.
8) Some sorts, like Radix, do not compare the values that it's sorting.
There are a lot of sorting algorithms. Some, like Bubble sort, seem to have appeal more for their catchy name and intuitive sorting algorithm, than any utilitarian value.
I hope that you were exaggerating in this statement deliberately. Because it's just not true. There are very few instances where an OS or an application will be sorting anything at all. And those that it will are optimised to the best possible optimisation for that data. In fact, most of the time, you don't sort at all - you just use a structure that's "pre-sorted", i.e. by mere insertion or deletion the system sorts itself without ever having to play with the entire list of items (linked-lists, trees, etc.). I think, technically, computers spend more time setting themselves up for various function / interrupt calls than almost anything else on average(e.g. pushing to the stack, popping from the stack, etc.). An idle computer is incredibly unlikely to be doing any sorting, even in the window manager, etc.
That said, I find sorts one of the most mind-numbing of algorithms. If you need something in sorted order, maintain it in that order from its very creation and save yourself an awful lot of hassle. That's where fancy structures like indexable skiplists and various trees come in and are almost always supplied to you because it's so damn easy to mess them up, especially where optimisations occur. You're unlikely to find a "simple" sort outside of programming exercises and C itself supplies only quick-sort.
But if you're learning them (which I reluctantly admit is necessary when you start out, but much less so by the time you're actually writing programs without referring to any other material), yeah - do them yourself on paper or you won't have a CLUE what the program is actually doing. But that much is true of a lot of computer science, from sorting to string-searching, looping to threading.
- Compiler warnings are like "Bridge Out Ahead" warnings. DON'T just ignore them.
- A compiler error is something SO stupid that the compiler genuinely can't carry on with its job. A compiler warning is the compiler saying "Well, that's bloody stupid but if you WANT to ignore me..." and carrying on.
- The best debugging tool in the world is a bunch of printf()'s for everything important around the bits you think might be wrong.
Not exaggerating much (in the 45% range), but the study was conducted a few decades back, (in the 80's), when computers were mostly dog-slow PC's , mainframe's, mini's, and such.
You'd be surprised at how many applications used a poorly chosen algorithm, back then.
I find sorting algorithms interesting, and in some cases, quite elegant indeed.
Last edited by Adak; 03-05-2012 at 09:27 AM.
"5) Computers spend about half their total working time, sorting data"
Yes, I learned this too. Way back in '73. I don't think the teacher meant that literally. He basically meant that computers are most often used for searching and sorting. Which is true in any filing / banking / warehousing context. Maybe a little less so in scientific / math-intensive disciplines.
As processor speeds and algorithms have been optimized over the decades there still is a significant amount of data shuffling going on - "massaging", due to the slower speed of external storage. So a super fast CPU has to wait for physical drives. In the end, most computer time is spent converting data from one form to another - in one order to another. Transposing, convoluting, whatever. So "sorting" still is a pretty good generic way of interpreting what's going on.
Another little factoid is that to estimate the amount of time a program will take to sort a huge file, just write a little test program which reads the file and writes it out backwards. No sorting – just time the thing.
This is remarkably accurate given that in all likelihood, the program will eventually incorporate a good O(N log N) algorithm and that most of the real bottleneck will be the slower data transfer and latencies of the physical storage devices.
Last edited by nonoob; 03-05-2012 at 03:23 PM.
Problem is: I don't know (clearly) how to start.
Are the elements of the vector supposed to be ordered by one by one comparison ? Reading at wikipedia couldn't help that much
Forget about computers.
You have a stack of cards. How do you sort them by hand? Describe the steps clearly.
Despite the name, there is actually no requirement that qsort must be implemented using quicksort.
By comparing elements (or cards) two by two, actually (e.g., is this element less than the other?). With this in mind, take up cyberfish's challenge.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
As a human, you have a fine ability to recognize patterns that repeat themselves. It's a necessary thing over the course of our evolution, since we're not gifted with speed like a cheetah, or strength like a Gorilla or Lion, or able to burrow like a mole.Problem is: I don't know (clearly) how to start.
Are the elements of the vector supposed to be ordered by one by one comparison ? Reading at wikipedia couldn't help that much
So put it to work, solving this problem:
Take 5 playing cards, into your hand, from a shuffled deck. Now, like Cyberfish wisely advised, put them in order.
Take the leftmost card (imagine it as the lowest index value in the array), and put that card into it's proper place, in the hand. Now, how did you do that, in detail?
Take your time, do it it slowly, and repeat it as often as you need to - you WILL see the pattern of actions (and logic), that you used in doing that.
THAT is the inner loop of your insertion sort, right there.
For the outer loop, repeat that action, with all the other cards, until it's no longer needed - everything is in order.
Now re-read the Wikipedia article on insertion sort. You WILL see the pattern eventually there, as well.
Yes, you will be comparing one by one (total of two elements being involved in every comparison).
Last edited by Adak; 03-06-2012 at 12:11 AM.
