Bubble sort does not sort as expected

Question

I have a problem with a C program that is supposed to sort the environmental variables by order based on their name. However, it doesn't seem to be sorting them correctly, as the strcmp is supposed to sort the variables in order by the ASCII value of the first character (a variable beginning with D goes before a variable beginning with H).

Here is the code I used:

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

void swap(char **a, char **b) {
        char *temp = *a;
        *a = *b;
        *b = temp;
}

void sort (char *envp[]) {
        char *name1, *name2, *token;
        for (int i = 0; envp[i] != NULL; i++) {
                for (int j = 0; envp[j] != NULL; j++) {
                        token = strdup(envp[i]);
                        name1 = strtok(token, "=");
                        free(token);

                        token = strdup(envp[j]);
                        name2 = strtok(token, "=");
                        free(token);

                        if (strcmp(name1, name2) > 0) {
                                swap(&envp[i], &envp[j]);
                        }
                }
        }
}

int main(int argc, char *argv[], char *envp[]) {
        printf("Before sorting:\n");
        for (int i = 0; envp[i] != NULL; i++) {
                printf("%s\n", envp[i]);
        }

        sort(envp);

        printf("After sorting:\n");
        for (int i = 0; envp[i] != NULL; i++) {
                printf("%s\n", envp[i]);
        }

        return 0;
}

Here is the "after sorting" result:

LS_COLORS=rs=0:di=01;34:ln=01;36:mh=00:pi=40;33:so=01;35:do=01;35:bd=40;33;01:cd=40;33;01:or=40;31;01:mi=00:su=37;41:sg=30;43:ca=30;41:tw=30;42:ow=34;42:st=37;44:ex=01;32:*.tar=01;31:*.tgz=01;31:*.arc=01;31:*.arj=01;31:*.taz=01;31:*.lha=01;31:*.lz4=01;31:*.lzh=01;31:*.lzma=01;31:*.tlz=01;31:*.txz=01;31:*.tzo=01;31:*.t7z=01;31:*.zip=01;31:*.z=01;31:*.dz=01;31:*.gz=01;31:*.lrz=01;31:*.lz=01;31:*.lzo=01;31:*.xz=01;31:*.zst=01;31:*.tzst=01;31:*.bz2=01;31:*.bz=01;31:*.tbz=01;31:*.tbz2=01;31:*.tz=01;31:*.deb=01;31:*.rpm=01;31:*.jar=01;31:*.war=01;31:*.ear=01;31:*.sar=01;31:*.rar=01;31:*.alz=01;31:*.ace=01;31:*.zoo=01;31:*.cpio=01;31:*.7z=01;31:*.rz=01;31:*.cab=01;31:*.wim=01;31:*.swm=01;31:*.dwm=01;31:*.esd=01;31:*.jpg=01;35:*.jpeg=01;35:*.mjpg=01;35:*.mjpeg=01;35:*.gif=01;35:*.bmp=01;35:*.pbm=01;35:*.pgm=01;35:*.ppm=01;35:*.tga=01;35:*.xbm=01;35:*.xpm=01;35:*.tif=01;35:*.tiff=01;35:*.png=01;35:*.svg=01;35:*.svgz=01;35:*.mng=01;35:*.pcx=01;35:*.mov=01;35:*.mpg=01;35:*.mpeg=01;35:*.m2v=01;35:*.mkv=01;35:*.webm=01;35:*.ogm=01;35:*.mp4=01;35:*.m4v=01;35:*.mp4v=01;35:*.vob=01;35:*.qt=01;35:*.nuv=01;35:*.wmv=01;35:*.asf=01;35:*.rm=01;35:*.rmvb=01;35:*.flc=01;35:*.avi=01;35:*.fli=01;35:*.flv=01;35:*.gl=01;35:*.dl=01;35:*.xcf=01;35:*.xwd=01;35:*.yuv=01;35:*.cgm=01;35:*.emf=01;35:*.ogv=01;35:*.ogx=01;35:*.aac=00;36:*.au=00;36:*.flac=00;36:*.m4a=00;36:*.mid=00;36:*.midi=00;36:*.mka=00;36:*.mp3=00;36:*.mpc=00;36:*.ogg=00;36:*.ra=00;36:*.wav=00;36:*.oga=00;36:*.opus=00;36:*.spx=00;36:*.xspf=00;36:
SSH_AUTH_SOCK=/tmp/ssh-sjl03UGnNi/agent.17850
PWD=/home/sgl24
LOGNAME=sgl24
XDG_SESSION_TYPE=tty
MOTD_SHOWN=pam
HOME=/home/sgl24
LANG=C.UTF-8
SHELL=/bin/bash
SSH_CONNECTION=35.235.244.34 36427 10.128.0.7 22
LESSCLOSE=/usr/bin/lesspipe %s %s
XDG_SESSION_CLASS=user
TERM=xterm-256color
LESSOPEN=| /usr/bin/lesspipe %s
USER=sgl24
SHLVL=1
XDG_SESSION_ID=94
XDG_RUNTIME_DIR=/run/user/1001
SSH_CLIENT=35.235.244.34 36427 22
XDG_DATA_DIRS=/usr/local/share:/usr/share:/var/lib/snapd/desktop
PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin
DBUS_SESSION_BUS_ADDRESS=unix:path=/run/user/1001/bus
SSH_TTY=/dev/pts/1
_=./a.out

Can you figure out how to make the program sort the variables in the correct order?

Answer 1

One problem is here:

token = strdup(envp[i]);
name1 = strtok(token, "=");   // now name points into the token string,
                              // more precisely at the beginning of token
free(token);                  // here you free toke, so the memory
                              // points is no longer valid

...but after you use name1 which now points also to invalid memory.

Read the documentation of strtok closely.

You probably want this:

void sort(char* envp[]) {
  char *name1, *name2, *token1, *token2;
  for (int i = 0; envp[i] != NULL; i++) {
    for (int j = 0; envp[j] != NULL; j++) {
      token1 = strdup(envp[i]);
      name1 = strtok(token1, "=");

      token2 = strdup(envp[j]);
      name2 = strtok(token2, "=");

      if (strcmp(name1, name2) > 0) {
        swap(&envp[i], &envp[j]);
      }

      free(token1);  // free token pointers only once you're done with them
      free(token2);
    }
  }
}

Or better declare variables as you use them:

void sort(char* envp[]) {
  for (int i = 0; envp[i] != NULL; i++) {
    for (int j = 0; envp[j] != NULL; j++) {
      char *token1 = strdup(envp[i]);
      char *name1 = strtok(token1, "=");

      char *token2 = strdup(envp[j]);
      char *name2 = strtok(token2, "=");

      if (strcmp(name1, name2) > 0) {
        swap(&envp[i], &envp[j]);
      }

      free(token1);
      free(token2);
    }
  }
}

Please be aware that this code has still problems:

1. on certain platforms you may not be allowed to modify envp directly. It works on my platform (Windows) but it might not work on your platform.
2. The code is not very efficient because there are a lot of strdups and frees, you'd be better off writing your own kind of strcmp which considers = as string terminator, then you don't need all the strdup/free.

Answer 2

Using qsort() is simplest:

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

extern char ** environ;

int pstrcmp( const void * a, const void * b )
{
    return strcmp( *(const char **)a, *(const char **)b );
}

size_t count_strings( char ** strings )
{
    char ** p = strings;
    while (*p) ++p;
    return p - strings;
}

int main(void)
{
    size_t environ_size = count_strings( environ );
    qsort( environ, environ_size, sizeof(char *), pstrcmp );

    printf( "%zu environment variables:\n", environ_size );
    for (char ** env = environ;  *env;  ++env)
    {
        char * p = strchr( *env, '=' );
        printf( "  %.*s\n", (int)(p - *env), *env );
    }

    return 0;
}

BTW, it is unclear whether environ is writable (but I think it typically is, just like argv[]).

BTW, on Windows you need to use _environ (with the leading underscore).