qsort

[pacman169]

Hello,

How does this qsort function work? I don't understand the algorithm.

void qsort(char *v[], int i, int j);

{
   
   int i, last;
   void swap(char *v[], int i, int j);
   
   if (left >= right)                    
   return;                               

    swap(v, left, (left + right)/2);
	last = left;
	for (i = left+1; i<= right; i++)
	   if (strcmp(v[i], v[left]) < 0)
		 swap(v, ++last, i);
    swap(v, left, last);
	qsort(v, left, last-1)
	qsort(v, last+1, right);

}


  

[YFGHNG]

Great reference on quicksort, if that's what the 'q' in "qsort" stands for.
https://www.youtube.com/watch?v=aQiWF4E8flQ

Also I believe the pre-defined sort() method is a selection sort. I may be wrong on this. But I do know quicksort, when implemented correctly, is on average, faster than the sort() method you see in the qsort.

[MiiNiPaa]

Func fact: although qsort was named after quicksort, almost no modern implementations uses basic quicksort because of insufficient perfomance in worst cases.
Often median of 3 used to select pivot, recursion is replaced by iteration and quicksort is replaced by another sorting algorithm for sufficiently small subsections. Usually insertion sort is used, but some implementations use heapsort, transforming quicksort to introsort (which is used by almost all std::sort implementations)

[pacman169]

I'm trying to understand how the program works, but now can't even compile:

#include <stdio.h>
#include <string.h>

#define MAXLINES 5000     /* max #lines to be sorted */


char *lineptr[MAXLINES];     /* pointers to  text lines */

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);

void qsort(char *lineptr[], int nlines);

/* sort input lines */

int main()
{
	
	int nlines;     /* number of input lines read */
	
	
	if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
		qsort(lineptr, 0, nlines-1);
		writelines(lineptr, nlines);
		return 0;
	}   else {
		printf("error: input too big to sort\n");
		return 1;
		
	}
}
	
#define MAXLEN 1000 /* max length of any input line */
int getline(char *, int);
char *alloc(int);

  /* readlines: read input lines */
int readlines(char *lineptr[], int maxlines)
{
	int len, nlines;
	char *p, line[MAXLEN];
	
	nlines = 0;
	while ((len = getline(line, MAXLEN)) > 0)
		if (nlines >= maxlines || (p = alloc(len)) == NULL)
			return -1;
	    else {
	    	line[len-1] = '\0'; /*delete newline */
			strcpy(p, line);
			lineptr[nlines++] = p;
	    }
	
		return nlines;
	
}
	
/* writelines: write output lines */

void writelines(char *lineptr[], int nlines)
{
	int i;
	
	
	for (i = 0; i < nlines; i++)
		printf("%s\n", lineptr[i]);
	
}
	
	
	
void qsort(char *v[], int i, int j);

{
   
   int i, last;
   void swap(char *v[], int i, int j);
   
   if (left >= right)                    /* do nothing if array contains */
   return;                               

    swap(v, left, (left + right)/2);
	last = left;
	for (i = left+1; i<= right; i++)
	     if (strcmp(v[i], v[left]) < 0)
		 swap(v, ++last, i);
    swap(v, left, last);
	qsort(v, left, last-1)
	qsort(v, last+1, right);

}

GCC:

Documents/program13.c:23:21: error: too many arguments to function call,
expected 2, have 3
qsort(lineptr, 0, nlines-1);
~~~~~ ^~~~~~~~
Documents/program13.c:12:1: note: 'qsort' declared here
void qsort(char *lineptr[], int nlines);
^
Documents/program13.c:34:5: error: conflicting types for 'getline'
int getline(char *, int);
^
/usr/include/stdio.h:442:9: note: previous declaration is here
ssize_t getline(char ** __restrict, size_t * __restrict, FILE * __restri...
^
Documents/program13.c:44:36: error: too few arguments to function call, expected
3, have 2
while ((len = getline(line, MAXLEN)) > 0)
~~~~~~~ ^
/usr/include/stdio.h:442:1: note: 'getline' declared here
ssize_t getline(char ** __restrict, size_t * __restrict, FILE * __restri...
^
Documents/program13.c:71:6: error: conflicting types for 'qsort'
void qsort(char *v[], int i, int j);
^
Documents/program13.c:12:6: note: previous declaration is here
void qsort(char *lineptr[], int nlines);
^
Documents/program13.c:73:1: error: expected identifier or '('
{
^

[MiiNiPaa]

error: too many arguments to function call

YOu declared qsort as taking 2 arguments, but are trying to pass 3.

error: conflicting types for 'getline'

There is already getline function in standard library. Do not name your functions as standard library ones.

error: conflicting types for 'qsort'

There is already qsort function in standard library. Do not name your functions as standard library ones.

[pacman169]

There is already qsort function in standard library. Do not name your functions as standard library ones.

Not a single C book that I have ever read stated that I should choose meaningful names for my functions. Note that most functions in the C standard library are implemented as macros. It is easy to undefine a name with #undef. That's all.

The C standard library includes a function get line? Taken from man page:
http://www.crasseux.com/books/ctutorial/getline.html#getline


How would I use it in this context, so that I don't need to write my own?

[YFGHNG]

Not a single C book that I have ever read stated that I should choose meaningful names for my functions.

Just because they don't doesn't mean you shouldn't. For example:

int a( int b )
{
    return b*b;
}

Compare the clarity of the function above to the one below

int squareOfNum( int base )
{
    return base*base;
}

You might think "oh man that's so much writing for such a simple function". But the few extra seconds spent typing out a variable name is worth the minutes, hours, or even days of you maybe spending trying to debug a pointer or calculation error due to confusing method and variable names.

[MiiNiPaa]

Note that most functions in the C standard library are implemented as macros

No. They can also add a macro with same name, but every standard library function should be a function first. C standard requires that address of library function should be able to be taken, therefore any implementation which implements standard library function solely as macro is noncompliant.

C99_Standard wrote:

7.1.4 Use of library functions

Any function declared in a header may be additionally implemented as a function-like macro defined in the header, so if a library function is declared explicitly when its header is included, one of the techniques shown below can be used to ensure the declaration is not affected by such a macro. Any macro definition of a function can be suppressed locally by enclosing the name of the function in parentheses, because the name is then not followed by the left parenthesis that indicates expansion of a macro function name. For the same syntactic reason, it is permitted to take the address of a library function even if it is also defined as a macro.

How would I use it in this context, so that I don't need to write my own?

As I see only place where you are using getline is here:

int len, nlines;
char *p, line[MAXLEN];
	
nlines = 0;
while ((len = getline(line, MAXLEN)) > 0)

You can just slightly modify it to conform to the signatire:

size_t maxlen = 100;
char* line = (char*) malloc(maxlen + 1);
while ((len = getline(&line, &maxlen, stdin)) > 0)

[pacman169]

So how would I modify the readlines function?

I can't just modify it like that, because the code is used elsewhere.

[MiiNiPaa]

Rename it to avoid name clashes if you do not want to use library one.

[Bdanielz]

How does this qsort function work? I don't understand the algorithm.

I use visualizations when ever I get confused about how things work.

Check this out...

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

[pacman169]

And from where does the error

error: expected identifier or '('
{
^

come from?

[MiiNiPaa]

And from where does the error

error: expected identifier or '('
{
^

come from?

All errors aside from first one are potentially meaningless: parser state is already messed because of preceding erors, so for later errors there is a great chance that they are caused by previous ones.

This is why you should always fix erors starting from first one.