Printable View
Hi. So I have to write a function that reads letters one at a time from a text file, such as (aBCdefG) using fgetc(). However, each character needs to be inserted into the array in ascending ASCII order, so it should come out as (BCGadef). I wanted to use an insertion sort, however, that would require me to pass the whole array. My professor wants me to sort the letters as they are read, though, and not as a whole array.Can you even do that? Any help would be appreciated!
Yes you can do that, although an array isn't very suitable due to the difficulty of insertion.
Insertion sort will work. Each time you read a character, you insert it into the array (which means you have to shift part of the array to make room for each character.
You need to know what your professor really wants.
If we needed to do this "for real", then almost everyone would declare a 256 element array, and then go through the file, indexing into it and incrementing a counter. Then get the data in the format wanted on a second pass.
But it might be that he wants you to get used to manipulating arrays by inserting elements.
I'm just in an intermediate class, so I don't think I'm doing anything super complicated. He told me the function would be similar to an insertion sort, but not exactly the same..
The main difference is that an insertion sort is usually performed on an existing array, starting at the beginning of the array. In this case, you're inputting data one character at a time, so the array is growing as you insert each character, and the array is always in a sorted state, which means you could optionally use a binary search to speed up location of the insertion point, but that wouldn't be needed for this class. It would also be possible to use other sort methods, such as a bottom up merge sort, but again, beyond what is appropriate for your class.Quote:
Originally Posted by orangePeel
Ahh ok. Yea. I haven't learned binary seach and other sorting methods, so how would I do this? Is there a way to get each character from the file and sort them as they come? I don't want anybody to do my homework for me, but a little code preview would be nice :)Quote:
Originally Posted by rcgldr
For this assignment, it's probably OK to assume a maximum size for the array, so you just need to declare the array and have a integer for the current size of the array. Use getc() to read characters one at at time.
Insertion sort is usually modeled after a person sorting cards in a hand (group) of cards. In this case, picture you start out with no cards, and then sort each card via insertion sort, as it is dealt to you. Forget all the complicated "STUFF" above, because that's not what your instructor wants done in this case.
It's simple, don't over-think it. Picture the cards being sorted as they're dealt to you, one at a time.
Hi, I'm not in school but desperate to get good at programming.Quote:
Originally Posted by Malcolm McLean
I'm assuming you use the 256 element array because that's your counting array, correct? Every time you read in a valid character, increment the appropriate array element by 1. Your 'dictionary' is created by all non-0 elements of the array. And then you can just linearly run through the array, printing out the associated character if the value of the element is >0?
And with insertion sort, don't you have to probe backwards a bit? Idk, I just wrote code the other day that sorts by looking backwards and I don't think it's very efficient. Well, it goes forward and for every step forward, it looks backwards the appropriate depth and makes checks 'n' stuffs.
No you don't go backwards, but you have a value that you store before beginning the comparisons. That may what you were implementing. The best way to understand a sort is to watch one of the many applets that demo it, and then write it up and have it work on a very small array - but only do one loop at a time, printing results as it goes, as you hit enter.
So much work went into sorting algorithms, that they are nearly always a thing of beauty to study.
I had the impression that you understood an insertion sort. Here's a simple description for the type of insertion sort you need. You need an character array to hold the sorted characters, an integer to hold the size of the array, and some more integers for indexing / inserting. The array is initially empty (size == 0), so you can consider it "sorted". For the insertion sort, for each character you get, you set an index into the array to zero. If the index is >= array size, then store the character at the end of the array (array[array_size]). Otherwise compare the character to array[index], if the character is smaller, then you need to insert the character at that point in the array. If the character is greater or equal to array[index], you increment index, and repeat the loop to check if index is >= array size. If you need to insert the character, you need to move all the characters at array[index] and above to array[index+1], starting at the end of the array and working your way backwards. You can use the standard library function memmove() to do this if you want. Finally after inserting or appending the character to array, you increment array_size.