Need help with writing this algorithm in code

Question

I have been mixed up on how to code this algorithm in c#... It is the jump search algorithm 2.3. Any hints or anything will be of help thank you.

Vulpes · Answer

Here's my attempt at coding that in C#. The only awkward point is that Lists are zero based in C# whereas the algorithm seems to be assuming that they're 1-based. I've therefore reduced the index by 1 to allow for this: using System; using System.Collections.Generic; class Program { static void Main() { var list = new List {3, 5, 7, 8, 10}; // already sorted int lower = 1; int upper = list.Count; int jump = (int)Math.Sqrt(upper); // probably optimal value for jump int[] search = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; foreach(int X in search) { int index = JumpSearch(list, lower, upper, jump, X); if (index > 0) { Console.WriteLine("{0} was found at index {1}", X, index); } else { Console.WriteLine("{0} is not in the list", X); } } Console.ReadKey(); } static int JumpSearch(List list, int lower, int upper, int jump, int X) { if (lower if (upper if (jump if (jump > (upper - lower + 1) ) throw new ArgumentException("jump must not be more than upper-lower+1"); int index = lower + jump - 1; while(upper > index && X > list[index - 1]) // List is zero based { index += jump; } if (upper > index) upper = index; return LinearSearch(list, index - jump + 1, upper, X); } static int LinearSearch(List list, int lower, int upper, int X) { for(int i = lower; i { if (list[i - 1] == X) return i; // List is zero based } return 0; } } The output is: 1 is not in the list 2 is not in the list 3 was found at index 1 4 is not in the list 5 was found at index 2 6 is not in the list 7 was found at index 3 8 was found at index 4 9 is not in the list 10 was found at index 5

Vulpes · Answer

Well, what we can see just tells us how to implement the algorithm using pseudo-code. It doesn't tell us how 'jump search' actually works. So, I've simply translated the pseudo-code into C# code. As previously mentioned, the only awkward point is that List in C# is zero based, not 1-based, so I've adjusted for that. No definition was given for the LINEAR.SEARCH method so I simply assumed that we're supposed to iterate through the list, returning the 1-based index if X is found or 0 otherwise. The part between the {..} is simply a comment but I used the information in that to check the arguments are acceptable and consistent with each other. Thinking about it some more, perhaps we ought to add another line to make sure 'upper' isn't more than the number of elements in the list: if (upper > list.Count) throw new ArgumentException("upper can't be more than the number of elements in the list");

Philip Harris · Answer

Makes sense I guess I should have looked it as pseudo code and not only thought in c#, Thanks for clearing that up should go smoother for me hopefully finishing up this semester. Many thanks Vulpes.... YOU ROCK!

Philip Harris · Answer

Thank you I keep getting caught up in the wording of the text I believe do you have any tips on making it easier to interpret?

Need help with writing this algorithm in code

Answers (4)