Array Sorting Algorithms V

This tutorial is the fifth part of the "Array Sorting Algorithms" series. In Array Sorting Algorithms V, we will explore a very simple sorting algorithm that you can implement quickly and easily. A basic knowledge of C++ is, as always, necessary to fully grasp this tutorial.

Within the "Array Sorting Algorithms" series of tutorials, we have explored a number of options for your data sorting needs. I have shown options for basic sorting (Bubble sort), speed sorting (Quicksort) and even a joke sorting method (Bogosort). So you may be asking, "What sorting method could possibly be left?" Well, there are several more algorithms for sorting data, but in this tutorial, I will focus on the simplest of all sorting methods, Gnome sort. Gnome sort is perhaps the easiest sorting method to implement and certainly requires the least code. Gnome sort works by comparing one piece of data to the one before it and determining if they need to be switched or not. Before I explain more about Gnome sort, let's see some pseudo code:


function gnomeSort(array[], length)

{

    Declare integer pos and set it to zero

    while pos is less than length

        if pos is equal to zero or array[pos] >= array[pos-1]

            increment pos

        else

            swap a[pos] and a[pos-1]

            decrement pos

        end if

    end while

}

If you have seen the other sorting algorithms that I have covered in previous tutorials, you will notice that this code is much smaller than other sorting algorithms. Also, gnome sort only has one loop instead of two like Bubble sort. This code works by going into a loop first that determines when we have run out of items to sort. Next, if the position of the array is zero, or the array is in order, we move to the next item. Otherwise, we swap the data and move backwards in the array. Once we have gotten to the end of the array, the loop ends and so does the procedure.

So, now that we have our pseudo code worked out, lets start writing our code. Open up a new C++ file and type in the following:


#include <iostream>

using namespace std;


void gnomesort(int[], int);


int main(void)

{

    int array[5];

    

    for(int i = 0; i < 5; i++)

    {

            cout << "Enter element " << i + 1 << " of the array: ";

            cin >> array[i];

    }

    

    gnomesort(array, 5);

    cout << "The order of the sorted array is: ";

    

    for(int i = 0; i < 4; i++)

            cout << array[i] << ", ";

    

    cout << array[4] << endl;

}

Here we have the main function which will allow us to test the algorithm. As you can see, I have included the necessary header and namespace for output as well as defined the function prototype for our algorithm. The main function asks the user for input of numbers, calls our sorting algorithm, and then outputs the sorted numbers.

The only thing left to do now is to write the sorting algorithm (which shouldn't take long considering how small the code is). Type in the following below the main function you just wrote:


void gnomesort(int array[], int length)

{

     int pos = 0, temp;

     

     while(pos < length)

     {

          if (pos == 0 || array[pos] >= array[pos-1])

             pos++;

          else

          {

              temp = array[pos];

              array[pos] = array[pos - 1];

              array[pos - 1] = temp;

              pos--;

          }

     }

}

This code works the same way the pseudo code I described above works. We look at each piece of data in our array individually and move forward or backwards based on whether the data is in order or not. Compile the code that you have written and test it out.

Your next question may go something like this: "OK, this sorting algorithm works just fine, but with alternatives, why should I use this one?" Well, lets say that your working on a small project (for school or something), and you want to sort some data. Now, you COULD go looking in your C++ books or on the internet for a good sorting algorithm, but then you would have to waste time searching AND implementing the stock algorithm in your program. However, because Gnome sort has such a small size, you can memorize it fairly easily and write it out really quick in your program! Gnome sort may not be the fastest or the best sorting algorithm, but it is defiantly the simplest.

This code was written and compiled in Dev-C++ so it may need some tweaking to work in other compilers. The source code used in this project is attached for convenience. If you would like to contribute to the information provided here, or offer corrections, please post a reply.