Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======Selection Sorting Implementation======

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

This project was begun on December 1st and is anticipated to take 2 hours. 

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


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

  * Matthew Haas
  * [[http://en.wikipedia.org/wiki/Selection_sort]]
  * Understanding the C programming language
 

=====Background=====
The purpose of this project it to implement a selection sort algorithm.

The entire data structures course up to this point has been about data management. To do this we have stored data in different data structures. But what good is the data if we do not know how to sort it?

The selection sort project will attempt to sort data that is stored in a data structure. This implementation will sort data that is stored in an array but this could easily be changed to sort data being stored in a linked list or something like that.


=====Scope=====
Once I write the heart of the selection 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 selection sort algorithm will sort through the array until it has been sorted. 
Once that is done the array will be displayed.


=====Attributes=====
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 selection sorting algorithm 


=====Code=====
===selection.c===
<code c>

/****************************************************                                                                          
* Author: Dave Schoeffler                           *
* Purpose: This program implements a selection sort *
* algorithm. The program will accept as input ten   * 
* integers and then store them in a dynamic array.  *
* It will then implement a selection sort algorithm *
* on that array and then sort them in accending     *
* order. It will then output the newly sorted       *
* array.                                            *
*                                                   *
* Compile with: gcc -o selection selection.c        *
*                                                   *
* Execute with: ./selection                         *
*                                                   *
****************************************************/
#include <stdio.h>
#include <stdlib.h>
int minLocation(int *array, int first, int last);

int main()
{
   int *array;
   array = (int*) malloc(sizeof(int)*10);
   int tmp,i,j,minIndex;
   int input;
   int ARRAY_LENGTH = 10; 
   //loads ten values into an array
   for(i = 0; i < 10; i++)
   {   
      printf("enter 10 different integers: ");
      scanf("%d",&input);
      *(array+i) = input;
   }   
   //meat of the selection sort algorithm
   for (i = 0; i < ARRAY_LENGTH; i++)
   {   
      //this function returns the index of the smallest value in the array
      minIndex = minLocation(array, i, ARRAY_LENGTH - 1); 
      //swaps the min value with the value in position i
      tmp = *(array+i);
      *(array+i) = *(array+minIndex);
      *(array+minIndex) = tmp;
   }   
   for( i = 0; i < ARRAY_LENGTH; i++)
   {
      printf("[%d]:%d\n", i, *(array+i));
   }
   return 0;
}
// function minLocation() accepts 3 parameters. The first parameter is an
// integer pointer pointing to the base of the array. The next provide bounds
// for where in the array to look for the minimum value
int minLocation(int *array, int first, int last)
{
   int loc, minIndex;

   minIndex = first;
   for (loc = first + 1; loc <=last; loc++)
   {
      if (*(array+loc) < *(array+minIndex))
      {
         minIndex = loc;
      }
   }
   return minIndex;
}

</code>
=====Execution=====
In the execution of my code, I ran the program twice entering different values each time.
<cli>
lab46:~/src/data/sorts$ ./selection
enter 10 different integers: 90
enter 10 different integers: 89
enter 10 different integers: 78
enter 10 different integers: 67
enter 10 different integers: 56
enter 10 different integers: 45
enter 10 different integers: 34
enter 10 different integers: 2
enter 10 different integers: 3
enter 10 different integers: 12
[0]: 2
[1]: 3
[2]: 12
[3]: 34
[4]: 45
[5]: 56
[6]: 67
[7]: 78
[8]: 89
[9]: 90
lab46:~/src/data/sorts$ ./selection
enter 10 different integers: 543
enter 10 different integers: 22222222
enter 10 different integers: 976545
enter 10 different integers: 23423
enter 10 different integers: 0
enter 10 different integers: 4
enter 10 different integers: 567
enter 10 different integers: 22
enter 10 different integers: 22
enter 10 different integers: 6666
[0]: 0
[1]: 4
[2]: 22
[3]: 22
[4]: 543
[5]: 567
[6]: 6666
[7]: 23423
[8]: 976545
[9]: 22222222
lab46:~/src/data/sorts$
 
</cli>
Notice that both times it sorted the data completely and accurately. 

=====Reflection=====
This being a shorter project I wasn't able to have the opportunity to research, explore, fail at certain things, etc... as compared to some other projects
I have done in the past. But despite that, I feel I learned a lot of things about how the selection sort algorithm. In my opinion it
is one of the simpler sorting algorithms out there. Being simple though comes with its disadvantages(that being its worse case scenario
performance). This means that it is not the most optimal way to sort data. I plan to explore alternative ways of sorting data in
the future an then compare the performance on my own. I can say after this project I now have a good knowledge of the selection sort algorithm.

=====References=====
In performing this project, the following resources were referenced:

  * Matthew Haas
  * [[http://en.wikipedia.org/wiki/Selection_sort]]
Lab46 Wiki

User Tools

Site Tools

Page Tools
