Sorting problem, finding the shortest way to sort it

Question

3.00/5 (2 votes)

See more:

Hi,

All right, so first of all, this is not my homework, not a homework at all, I don't want any of you to solve it for me. I am just preparing for a programming competition, and there is this one I can't solve, and I would like some hint.
So the problem is that there are books in a library and I have to put them in order. But I have to find the the best way (definetely not the fastest!) to sort it.

So I have these numbers:

7, 10, 1, 3, 2, 8, 4, 9, 6, 5

I have to put them in order. I tried quicksort, but of course thats the fastest but not the best. Bubble sort is out as well, it has to do many steps.

So I have an answer, which is 7 (the count of the steps I have to do to sort it), but I can't find a way to figure out how to do it...

(I didn't know what tags to write, so since I try to write it in C# I just put that one there)

Thank you

Posted 7-Jan-13 8:49am

velvet7

Updated 7-Jan-13 8:50am

v3

Add a Solution

Comments

PIEBALDconsult 7-Jan-13 15:36pm

More specifics are required.

That reminds me of a job I applied for back in 2002. Among other things they asked me to submit an example of "a function to sort a list of numbers" in the language of my choice -- no other requirements. What sort of list? An array? On the command line? What?
At the time I was just learning C# and considered just using List.Sort but decided against that as it wasn't a C# job. After giving it some thought I decided to read the list from the command line and use a function I had written in C a few years earlier that added integers to an array in a sorted fashion. (I didn't get the job.)

You could also consider using a binary tree. :shrug:

velvet7 7-Jan-13 15:44pm

Uhm, yeah so I have to give the minimum number of steps I have to do to sort it.
Array.sort doesn't return that to me. (and I think it does it in the fastest way, not the most efficient, im not sure though)

Philip Stuyck 7-Jan-13 15:47pm

See the trick with bublesort and quicksort is, ... you keep using the same array.
Which is the whole point. Binary search is good enough if the numbers are being input one at a time, and the list is kept sorted in the process of inputting additional numbers and inserting them in the array or whatever containment you use.

velvet7 7-Jan-13 15:50pm

Right. So the point of my application is not to be better.
Look at it this way. You have a friend, a librarian. He asked you to find a way how he could sort his books numbered from 1 to 10. (above) You have to tell him how many steps he has to do to sort them. :)

PIEBALDconsult 7-Jan-13 16:19pm

Sure, but I don't think he would actually do swaps the way we do; a bookshelf doesn't work like an array. For instance in the first step he wouldn't put book 7 in the third spot, he'd put it in the seventh.

Here's another way -- put the 7 at the end, then put the 10 at the end, etc. -- I count five steps this way (for this set of data).

Philip Stuyck 7-Jan-13 15:43pm

What exactly counts as step here ?
For instance buble sort swaps numbers based on one of the values being bigger than the other, but iterates through the whole array.
Is a swap already a step, or is a full sweep of the array a step ?

velvet7 7-Jan-13 15:44pm

A swap is a step, yes.

PIEBALDconsult 7-Jan-13 15:56pm

Then filling a binary tree and then copying it back out is zero steps.
There are other ways to sort a list that likewise require no swaps.

velvet7 7-Jan-13 15:58pm

Please look above my comment.
By the way, you are right. But that's not the case. :)

Philip Stuyck 7-Jan-13 15:50pm

Ok, so you need to find the algorithm that results in 7 such operations right ?
So what is the result of quicksort ? That one is one of the quickest I know of. Mind you I never implement sorting myself, because of all the libraries that are there.

velvet7 7-Jan-13 15:51pm

Quicksort: 9 swaps

PIEBALDconsult 7-Jan-13 23:46pm

Can you provide a link or something so we can see the actual text of the question?

I have two methods that sort that list with five "steps".

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Daniele Rota Nodari · Answer 1 · 2013-01-07T23:25:00

Solution 2

I suggest to take a look at Visualization and comparison of sorting algorithms in C# and experiment with the source code to compare different algorithms.

I took some minutes to test your numbers and I'm confindent that the constraint of 7 could be honored. ;)

Regards,
Daniele.

Posted 7-Jan-13 23:25pm

Daniele Rota Nodari

Comments

PIEBALDconsult 8-Jan-13 11:47am

But this isn't about telling a computer how to sort them; it's about telling an actual person how to sort them -- there's a big difference; humans aren't as limited as computers.

velvet7 8-Jan-13 12:10pm

I said that as an example to understand the concept better. The competition I am preparing for wrote the eaxct same thing. A librarian wants to know what are the minimum steps (swaps) to put them in order. That is the ONLY and ONE thing he cares about, nothing else. So I think this may help me, I'll check it out right away, thanks, Daniele.

PIEBALDconsult 8-Jan-13 17:14pm

Then the librarian is an idiot -- he shouldn't use swaps at all.
He can do it in five operations, or even three if he's smart.

Daniele Rota Nodari 8-Jan-13 12:17pm

Yes, You are right, but velvet7 was not asking for the whole solution: he was asking for a way to find the solution by himself.. so I think he has exactly to find how to sort them... in order to complete the process within 7 steps.
I think that article can help him walk this way.

And about limits of humans and computer: this is a topic we can discuss really long. ;)

Sergey Alexandrovich Kryukov · Answer 2 · 2013-01-07T08:59:00

Solution 1

If this is for programming competition, this is no less of cheating than if it is a homework. The competition should evaluate your real work and skills. Why should we help you more than your competitors? This is no good.

And, after all, you and your competitors can learn existing techniques on the Web, so what's the problem?

If I was the author of the problems for the competition, I would never pose a problem like sorting. This way, some knowledge of existing technique is evaluated, not in-depth knowledge and the ability to think. It is always possible to put forward an original problem, even though they are quite difficult to invent. Instead of offering some standard problems for a competition, it's much better not conduct any competitions at all.

So, if you are going for a real programming competition, knowledge of known algorithms won't really help. But if you find even some known algorithm by yourself, fully independently, it can greatly improve your skills and chances to win. But in this case, if we answer your question, we will fully take away that chance from you. As I don't want to take out this chance and hence hurt you, I'm not answering, sorry. Hope it can help you. :-)

—SA

Posted 7-Jan-13 8:59am

Sergey Alexandrovich Kryukov

Comments

velvet7 7-Jan-13 15:02pm

I am sorry, I think you misunderstood me... I am practicing for this upcoming competition. The year before last this was the problem, so I was thinking of trying to solve it, just to be prepared. I would never ever cheat... I solved all of them, except this one. This one is giving me a headache.

velvet7 7-Jan-13 15:03pm

Also, I was trying to get a HINT, not the answer. I stated that clearly in my quesiton. I know I have to find out the answer myself to get somewhere.

Sergey Alexandrovich Kryukov 7-Jan-13 15:09pm

Good. :-)
—SA

velvet7 7-Jan-13 15:14pm

Thanks, anyways :-)

Sergey Alexandrovich Kryukov 7-Jan-13 15:10pm

If you get help, it will only reduce your chances to win, can you finally get it. It's unlikely that you get exactly this problem. You need to acquire skills, not the solution...
Instead trying to get the point, for your own sake, you are down-voting the post. Guess who is going to be a looser? A hint: not me. :-)
—SA

velvet7 7-Jan-13 15:23pm

So... You are trying to say, that let's say I can't add up 2 numbers then I have to figure it out myself? Then what's the point of schools? They teach you how to use the numbers, not the solution, right?
For example, how did you start programming? You just KNEW how to do it? You read books about it maybe, but still, you had that book to help you out and get you started, the exact same thing I am asking for.
I would like to find out where to start when I get a problem like this (not exactly this), not the solution.

I hope you understand me. Maybe I am wrong, in that case, I am sorry for wasting your time.

Sergey Alexandrovich Kryukov 7-Jan-13 15:37pm

Sigh...

It simply means you wasted your time at school. (But I hope not.) People who were taught how to add numbers and did not figure it out by themselves... yes, actually add them but don't really know how to do it. I'm afraid you have no clue what a real knowledge is. Useless discussion.

No problem with my time, this is a useful experience. I advise think about saving yours: get to work, read some books, relax; after all, it's also an important part of learning...

—SA

velvet7 7-Jan-13 15:42pm

Maybe I don't know what a real knowledge is, I am not old enough yet, I admit. I am just a young boy who tries to learn new things. (I guess I don't have to say that you didn't help, that's the reason I gave you 2 points)

Thank you for your time. :)

Sergey Alexandrovich Kryukov 7-Jan-13 15:46pm

Sorry, I did not help, but only because you did not get it.
Effectively, you done-voted yourself, not me, and everyone can see it.
Hope you will later change your mind, as many did.

Good luck, anyway.
—SA

CPallini 7-Jan-13 16:27pm

Don't know why some folks down voted this. Have my 5.

Sergey Alexandrovich Kryukov 7-Jan-13 17:07pm

Well, this time, at least OP explained why he down-voted it... :-) This is way too typical.
Thank you, Carlo.
—SA

PIEBALDconsult 7-Jan-13 21:49pm

Because it's a comment; not an answer -- I'm guessing.

Sergey Alexandrovich Kryukov 7-Jan-13 22:09pm

I don't care. I think this is adequate post, as an answer. If a question is wrong, nothing is the answer, right? And so what, just writing comments? Sometimes this is not enough. This post is not an answer, but I insist that this is a solution. It is even named this way: "Solution 1".

I don't care about votes, I'm trying to help, and real help sometimes requires not the most pleasant posts...
—SA

PIEBALDconsult 7-Jan-13 23:41pm

I _do_ care. While your response is correct, it is _not_ a solution and should _not_ be marked as such. It will not help anyone else who comes along looking for different ways of sorting. This is one of the worst things about this horrible Q&A rubbish. The question should have been asked in the proper forum -- perhaps even Algorithms -- where we could have had a nice broad discussion of the subject.

What I _don't_ care about is _why_ he's asking; I just don't think that's important -- though of course I'm not going to actually give him codez either.

Sergey Alexandrovich Kryukov 8-Jan-13 0:14am

What, want to down-vote it? Do it, and let me do what I think is right. Or you want me to remove the post? Sorry, I'm not convinced. Is someone points out if I'm wrong, I say "thank you" and fix myself.

This is the formality. The only difference you may see is those damn points. I got a request from OP, I provided the response which I think is right and helps in some different way. Some inquirers need a kick, no matter of it is accepted or not. I might be remembered later. At least, OP should see some feedback. And I did it the way I did. In many other cases, I do not provide answer.

And I care first of all, why some question is asked. This is very important. Again, if you want to help, not just provide an answer and get a reputation of the answerer.

—SA

[no name] 8-Jan-13 5:51am

Dear SA i like you very much ... Why because whatever you think in your mind that's only you posted. Your not Compromise at any cost.That's way i like you....
All of them Please Read these Point's While Answering the Questions... When answering a question please:

3.If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. INSULTS ARE NOT WELCOME. Let's work to help developers, not make them feel stupid.

Sergey Alexandrovich Kryukov 8-Jan-13 9:27am

Thank you very much for your nice words.
—SA