ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
I am learning C from the book and I am a bit stuck on one exersice. I am not asking you to tell me how to wright the program for that exercise, I just want some help. I wrote the execrise question below and some questions after.
(Selection Sort) A selection sort searches an array looking for the smallest element in the array. When the smallest element is found, it is swapped with the first element of the array. The process is then repeated for the subarray beginning with the second element of the array. Each pass of the array results in one element being placed in its proper location. For an array of "n" elements, n - 1 passes must be made and for each subarray, n - 1 comparisons must be made to find the smallest value. When the subaaray being processed contains one element, the array is sorted. Write a recusive function selectionSort to perform this algorithm.
Here are the questions:
1) I have read that recursive function inludes "return", but I think the "selectionSort" function should be of type "void" because all it does is sort values in an array. So I think it will not return anything and should be of type void. Am I correct?
2) At the moment I have no idea how to make the subarray start with the second element of the array, the third and so on (recursively). Should I think that it will involve decrementing a velue untill it will equal to 1, in order to keep the recusion going? (like in the execise: n - 1)
3) In recursion, does a value always have to decrement to 1 or 0?
ahh at last, someone who gets how to ask homework questions properly.
1) well no, you'd most likely want to call the final thing using like, "newArr = sortthis(oldarr)" so the return would be the sorted array. you COULD make it rearrange the original array, but that's not a good way to do things normally.
2) remember that there is only ONE function. as such each recursion must be started with the very same information that the initial call is, i.e an array. How about simply not giving that first element to the next recursion in the first place? remove it from the array first off.
3) not sure what you mean by that at all, but essentially you are recusing until you find yourself starting the function with a single value array. you just look out for being asked to sort an array such as (999). you know you can't sort that, it's just one item! so there's the end of your sort.
essentially the new array doesn't exist at all until each successive sort has found it's lowest item. then all the recursive functions collapse in on themselves, spilling back the sorted array right at the end.
1) you don't *have* to do anything... up to you. you do need some way to access each value in turn though.
2) no. only if you think it's suitable to call the first function as newArr=(oldArr, 0) or something... and that's just messy. you should write ONE function only. you need to basically find the lowest value, keep it safe, and give everything else to the next recursion.
I study in Southampton Solent University used to be called Southampton Institute, but it is computer networking course, not programing. I am learning C by myself, I love Linux and programming and always wanted to learn C and C++, but struggling with it as you can see.
Originally posted by hubabuba 3) In recursion, does a value always have to decrement to 1 or 0?
If I could expand a little on what acid_kewpie was getting at... There is no "one way" to implement a recursive algortihm, but every recursive algorithm must include a terminating condition: a set of input values that prevents another self-call. It sounds like you're relying on a decrementing counter telling the number of unsorted elements. That'll work. You could also have a counter that increments until the number of items sorted is equal to the array's size. There are tons of way you can set up your terminating condition.
I do have a question though: Do you have to use recursion? Is that what the exercise requires? You could accomplish the same sort with two for loops (one nested in the other).
Well we can only go so far in helping you, as you're clearly aware. it's very simple recursion really, and is a great demonstration on how it's useful. But generally take the next element in the array. is it the lowest number so far? no? add it to a new array. yes? well store it in a variable. is there already a number in that variable? yes? push that one on to the new array. got to the end of the array? pass the new array to yourself as a recursion. Recieve a sorted array back from the recursion and attach your lowest number to the start and return it. job done.
i've a friend just completing a phd in marine biology or somethign down in southampton at the real uni, that silly bridge over the river is a killer...
I remember being taught recursive algorithms in my earliest programming classes, but later learned that recursive function-calling is nearly always a bad idea, for reasons of memory and stability.
As you hint at, recursion is often used because it's the solution that most closely matches how we (as humans) see the problem. But I wouldn't consider it a bad idea, even though it does inherently cost a little speed in function-call overhead. Rather, using a solution you can easily understand will save you lots of time and energy, opposed to trying to create a solution that doesn't make much logical sense, but is iterative instead of recursive. You don't lose much in terms of peformance these days, unless you're writing some really sensitive component. I'd also argue that you're more likely to make "off-by-one" iterative mistakes than infinite recursion mistakes, and even if you do, those infinite recursion errors are easier to identify. As to memory, using recursion can help you isolate variables and such that should not interact or impact one another (assuming that you're using variables with limited scope), for example when solving a maze. Recursion is good for you!
Originally posted by taylor_venable Recursion is good for you!
OK, I admit I still use it when it makes sense It is a good concept to help introduce what you can do with programming, and is usually easy to understand. But for me at least, it promoted the tendency to look for a recursive solution in cases where an iterative one would be more logical.
In my 2nd edition Deitel & Deitel "C++ How to Program", for instance, the very first recursion example is to calculate a factorial (this seems to be the favorite way of illustrating recursion). 5! = 5 * 4!, which is ( 5 * ( 4 * 3! ) ), which is ( 5 * ( 4 * ( 3 * 2! ) ) )... sure, it works, but it's simpler and more logical to just do 5! = 5 * 4 * 3 * 2 * 1. No additional function-calling overhead, no possibility of stack overflow.
Humans (in general) may find some recursive concepts more natural, but programmers should also be adept at expressing concepts in terms that computers find easier to deal with, especially if efficiency (of memory space or execution time) is of concern.
I'll recommend you to sort "in-place", because if you don't do that then you will have to merge the result of the induction in a new array and that's messy. About the recursion, use a function like this
array: the array to sort
from: the first position in the array
to: the last position in the array.
so the idea is that it sort the element between positions from and to and does not touch the others. In this way you can implement the recursion by changing the value of "from".