A project for Data Structures by Dave Schoeffler during the Fall 2011 semester.

This project was begun on December 12th and is anticipated to take 1 hour.

This project will explore the sorting algorithm called the bogo sort. To do this I will create a program that uses a bogo sort to sort a list of ten integers. The point of doing this is to obtain an understanding of a simple bogo sort algorithm.

In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

• Matthew Haas
• http://en.wikipedia.org/wiki/Bogo_sort
• Understanding the C programming language

The purpose of this project it to implement a bogo sort algorithm.

The whole purpose of a bogo sort is to randomly swap elements in a list and then to check whether they are in order. For the record, this is NOT a good sorting algorithm. You should not use this to actually sort data because there really is no logic behind it. It is all random which gives this algorithm a worst case performance of O(n)^infinity.

Once I write the heart of the bogo sort algorithm, I would like to then test it out. To do this, I will load ten different integer values entered by the user into an array. Then the bogo sort algorithm will sort through the array until it has been sorted.

Once that is done the array will be displayed.

The following attributes will be used in my program.

• pointers: A pointer will be used to mark the beginning of the array
• malloc/new: You must allocate memory for the array
• sort: This program implements a bogo sorting algorithm

/*************************************************                                 
* Author: Dave Schoeffler                         *
* Purpose: This program implements a bogosort sort*
* algorithm. The program will accept as input ten * 
* integers and then store them in a dynamic array.*
* It will then implement a bogosort sort algorithm*
* on that array and then sort them in accending   *
* order. It will then output the newly sorted     *
* array.                                          *
*                                                 *
* Compile with: gcc -o bogo bogo.c                *
*                                                 *
* Execute with: ./bogo                            *
*                                                 *
**************************************************/
 
#include <stdio.h>
#include <stdlib.h>
int main()
{
   srand(time(NULL));
   int *array;
   array = (int*) malloc(sizeof(int)*10);
   int i = 0,input=0,junk;
   int index1, index2;   
   int sorted = 1, tmp;
   //loads ten values from the user into the array
   for(i = 0; i < 10; i++)
   {   
      printf("enter 10 different integers: ");
      scanf("%d",&input);
      *(array+i) = input;
   }   
 
 
 
   //meat of the bogo sort
   while( sorted == 1)
   {   
      sorted = 0;
      index1 = (rand() % 10 );
      index2 = (rand() % 10 );
      tmp = *(array+(index1));
      *(array+index1) = *(array+index2);
      *(array+index2) = tmp;
      for(i = 1; i < 10; i++)
      {
         if(*(array+(i-1)) > *(array+i))//this statements checks to see
         {                              //if the elements are out of order
             sorted = 1;
         }
      }
   }
 
   //displays the array
   for(i = 0; i < 10; i++)
   {
       printf("[%d]: %d\n", i , *(array+i));
   }
 
   return (0);
}

Execution of my code.

lab46:~/src/data/sorts$ ./bogo
enter 10 different integers: 76
enter 10 different integers: 223
enter 10 different integers: 09
enter 10 different integers: 6
enter 10 different integers: 1865
enter 10 different integers: 345
enter 10 different integers: 988
enter 10 different integers: 1
enter 10 different integers: 9
enter 10 different integers: 555
[0]: 1
[1]: 6
[2]: 9
[3]: 9
[4]: 76
[5]: 223
[6]: 345
[7]: 555
[8]: 988
[9]: 1865
lab46:~/src/data/sorts$

I wanted to do this project mostly for the fun of it. After writing the algorithm, I realized how inefficient the algorithm really is. There is no logic behind the algorithm at all. It just randomly swaps elements until the list is sorted.

I noticed in the actual runtime of the program that it took longer to process the list than the previous sorting algorithms that I had written. This was to be expected.

In performing this project, the following resources were referenced:

• Matthew Haas
• http://en.wikipedia.org/wiki/Bogo_sort