Sorting lines of text according to first character - C programming

Question

Hello I wanted to make a sorting software in C. That sorts line of text based on the first character of the line. I want to group lines starting of V with Vs. so lines with letters starting with V will be sorted together. Anyone can guide me on how to do this?

f -0.80811 -0.520398 -0.275942

v 0.0146114 -0.0939821 0.00366211
v 0.0133369 -0.0926109 0.00480863
v 0.0142794 -0.0932492 0.00325213



f -0.788618 -0.530816 -0.310349

v 0.0146114 -0.0939821 0.00366211
v 0.0142794 -0.0932492 0.00325213
v 0.0144766 -0.0933648 0.00294873



f -0.726784 -0.686213 0.0299526

v 0.0154684 -0.0952972 0.00472045
v 0.0158173 -0.0956479 0.00515121
v 0.0150361 -0.0947439 0.00690701

Answer 1

This proof of concept does what you need. But it would be much easier to
$ sort file.txt

Disclaimer: This is my first post to stack overflow, so if I did something wrong please tell me. :)

Memory overhead of this is 8MiB(sizeof(char *) * 1024*1024). It also stores the full contents of the file in memory. Consuming approximately ~60Mib of RAM.

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>

#define LINES_IN_FILE 32

int compare(const void *ap, const void *bp)
{
    char **a = (char **)ap;
    char **b = (char **)bp;

    return strcmp(*a, *b);
}

int main(void)
{
    FILE *in = fopen("text.txt", "r");
    if (!in)
        return 1;

    char **pbuf, **buf;
    pbuf = buf = malloc(sizeof (char *) * LINES_IN_FILE);

    size_t count = 0, len = 0;
    while (getline(pbuf, &len, in) != -1) {
        pbuf++;
            count++;
        len = 0;
    }

    qsort(buf, count, sizeof(char *), compare);

    /* cleanup and print or whatever */
    return 0;
}

You can speed this up a bit by replacing the strcmp() function with tests to only compare the first bytes, i.e. if(*a[0] > *b[0]) ...

Answer 2

a quick way (I have not think much about complexity) is:

1. create a structure

   struct CharIntPair { int lineNr; char firstChar; };

2. Read the first character of each line and create an array of line number and first character.

3. Write your compare function and use qsort to sort that array according to the letter.
4. For each letter in the array, copy the elements into a subarray (complexity O(n), because it is already sorted).
5. Write another compare function to sort each sub-array according to the line number
6. Read the sorted lines...

Answer 3

This kind of problems should be solved by (in decreasing preference)

1. using specific tools, sort in this case
2. programming in scripting languages, such as Perl, or Python
3. programming in "low-level" programming languages, such as C

You should choose method one unless the specific tools are unavailable, or this problem only a small part of a larger project. In former situation, you should try the second method; in latter, you should choose the programming language used in that larger project.