Click here to Skip to main content
11,414,234 members (72,160 online)
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C#
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 9:49am
velvet71.1K
Edited 7-Jan-13 9:50am
v3
Comments
PIEBALDconsult at 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 at 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 at 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 at 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 at 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 at 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 at 7-Jan-13 15:44pm
   
A swap is a step, yes.
PIEBALDconsult at 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 at 7-Jan-13 15:58pm
   
Please look above my comment.
By the way, you are right. But that's not the case. :)
Philip Stuyck at 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 at 7-Jan-13 15:51pm
   
Quicksort: 9 swaps
PIEBALDconsult at 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".
Rate this: bad
good
Please Sign up or sign in to vote.

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. Wink | ;)

Regards,
Daniele.
  Permalink  
Comments
PIEBALDconsult at 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 at 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 at 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 at 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. ;)
Rate this: bad
good
Please Sign up or sign in to vote.

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. Smile | :)

—SA
  Permalink  
Comments
velvet7 at 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 at 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 at 7-Jan-13 15:09pm
   
Good. :-)
—SA
velvet7 at 7-Jan-13 15:14pm
   
Thanks, anyways :-)
Sergey Alexandrovich Kryukov at 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 at 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 at 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 at 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 at 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 at 7-Jan-13 16:27pm
   
Don't know why some folks down voted this. Have my 5.
Sergey Alexandrovich Kryukov at 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 at 7-Jan-13 21:49pm
   
Because it's a comment; not an answer -- I'm guessing.
Sergey Alexandrovich Kryukov at 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 at 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 at 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
Sergey Alexandrovich Kryukov at 8-Jan-13 9:27am
   
Thank you very much for your nice words.
—SA

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

  Print Answers RSS
0 Sergey Alexandrovich Kryukov 9,130
1 OriginalGriff 7,477
2 Maciej Los 3,710
3 Abhinav S 3,298
4 Peter Leow 3,084


Advertise | Privacy | Mobile
Web04 | 2.8.150427.2 | Last Updated 8 Jan 2013
Copyright © CodeProject, 1999-2015
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100