Thread: C Programming: Arrays and Sorting?

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    12

    C Programming: Arrays and Sorting?

    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!

  2. #2
    Stoned Witch Barney McGrew's Avatar
    Join Date
    Oct 2012
    Location
    astaylea
    Posts
    420
    Yes you can do that, although an array isn't very suitable due to the difficulty of insertion.

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    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.

  4. #4
    Registered User
    Join Date
    May 2012
    Posts
    505
    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 the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    12
    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..

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by orangePeel View Post
    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.
    Last edited by rcgldr; 04-17-2013 at 03:06 PM.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    12
    Quote Originally Posted by rcgldr View Post
    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.
    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

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    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.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  10. #10
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Quote Originally Posted by Malcolm McLean View Post
    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.
    Hi, I'm not in school but desperate to get good at programming.

    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.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with 2D arrays and Sorting
    By ramlapam in forum C Programming
    Replies: 3
    Last Post: 11-26-2011, 10:03 PM
  2. Replies: 16
    Last Post: 01-01-2008, 04:07 PM
  3. Replies: 2
    Last Post: 02-23-2004, 06:34 AM
  4. Question sorting character arrays: C programming
    By NeoSigma in forum C Programming
    Replies: 3
    Last Post: 05-23-2003, 09:28 PM
  5. Help with sorting arrays
    By Silence in forum C Programming
    Replies: 5
    Last Post: 05-17-2002, 10:05 AM