Home > Articles, Data Structures & Algorithms > Implementation of an application for the sorting of an array of strings.

Implementation of an application for the sorting of an array of strings.

The following program demonstrates a significant processing operation on arrays of strings. More precisely, we present the re-sorting of a set of strings in order to classify them. So, we read the strings and place them in a temporary storage area (buffer) large enough to be able to store all, keeping in an array a pointer to each string. Then we re-sort the pointers (only pointers and not strings to increase the performance) to place the pointer to the “smallest” string at the first position of the array, the pointer to the next “largest” string at the second position of the array, and so on.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

#include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

const int N_MAX = 1000;
const int M_MAX = 10000;

int
compare (const void * i, const void * j) {
  return strcmp (*(char **) i, *(char **) j);
}

int
main () {
  int N, M = 0;

  char * sorted[N_MAX], buffer[M_MAX];

  for (N = 0; N < N_MAX; N++) {
    sorted[N] = &buffer[M];

    if (!(cin >> sorted[N]))
      break;

    M += strlen (sorted[N]) + 1;
  }

  qsort (sorted, N, sizeof (char *), compare);

  for (int i = 0; i < N; i++)
    cout << sorted[i] << endl;

  return EXIT_SUCCESS;
}
  1. March 9, 2011 at 03:50

    Thank you for your suggestions. However, I did not mean to imply something else beyond what you told me (I had just a little expressive difficulty in the title of the article).

    Yes, the code does not implement a sorting algorithm, but is simply an example of sorting strings. I will soon fix the title so as not to confuse other readers.

    Also, I have attended in the past these videos you recommend. Moreover, I have known the “quick sort” for several years (as a recursive / iterative method “divide and conquer”).

    I do not study “Algorithms & Data Structures” in this period (I did so several years ago – now I find out about what’s new in this area) but I try to create a collection of useful algorithms and data structures for those interested.

    Finally, I am familiar with the issue of C and C++ you mention.

    It is true that it is good to program clearly using either C or C++. I try to keep this rule when necessary, but not always. For example, when working at the kernel level or device drivers I only make use of GNU C. While, when I develop an object-oriented project, I use only C++.

    Finally, I am not very interested in this issue in the examples I quote (those that do not exceed 50-100 lines of code). Personally, I think it is more important to understand the algorithm rather than to use the tool. You’ll also notice that I don’t make many white-box checks in the source code when the examples are simple (once again to emphasize only the steps of the algorithm).

    Be well!

  2. March 8, 2011 at 21:11

    This is not an algorithm for sorting strings.

    The sorting is done by ‘qsort’.

    The code you show is just the “boilerplate”.

    If you learn programming, it is worth knowing how qsort works from the “inside” since it is a very elegant and smart algorithm. I suggest you watch the video of lectures on algorithms at MIT.

    In this as well as in other relevant posts I notice an “identity crisis” in your code between C and C++. My opinion is, since you pay the (considerable) cost of using the standard library of C++, to try to make the step and write full C++ code (for example, to use the templated version of qsort in order to remove the function pointer).

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: