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.
======Project: Selection Sort======

A project for Data Structures and Systems programming by Brandon Kennedy during the Fall 2011 Semester.

This project was begun on 12-15-2011 and is anticipated to take 3 hours.
=====Objectives=====
The point of this project is to demonstrate my knowledge of command-line arguments, queue based data structures, and selection sorting algorithms.
=====Prerequisites=====
In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

  * man page for atoi
  * previous projects reguarding queues
  * wikipedia on selection sorting

=====Background=====
Through this project I am pursuing a greater knowledge of how to integrate a queue structure into any program, and combine it with powerful sorting algorithms if needed. I was hoping to throw a bunch of random concepts together, and come out with something pretty sweet that demonstrated my knowledge of those concepts.
=====Scope=====
This project will take integers from the command-line or from stdin, and sort them via a selection sort. They will then be loaded into a queue by use on enqueueing as they are sorted, and then printed from that queue by dequeueing.

=====Attributes=====
State and justify the attributes you'd like to receive upon successful approval and completion of this project.

  * attribute1: sorts -> this program will use a selection sort algorithm
  * attribute2: queue -> this program will implement a queue to hold and print the sorted data.
  * attribute3: command-line arguments: this is for systems programming -> this program will be able to bring in data via the command line.
=====Procedure=====
The first step I took was to figure out how to accept command line arguments and cast them to integer values via the atoi function.
<code c>
value[i] = atoi(argv[i+1]);
</code>

After that i put in a simple stdin loop to give me my needed values.

<code c>
for(i=0;i<size;i++)
{
   printf("enter value for slot %d", i)
   scanf("%d", value[i]);
}
</code>
Then i could do my processing via the value[] array whether they entered via command-line or stdin.
After that i moved into my sorting algorithm that you can find in the code section below. Once i had the program running, I slipped in a queue to show how they can be used in many different circumstances. Of course i didn't need to use the queue, but it was fun to put it in. Maybe one day i'll write a swap() for linked lists so that i can write sorting algorithms for linkedlists.

=====Code=====
===main===
<code c 1>
#include<stdio.h>
#include<stdlib.h>
#include"quelist.h"

int main(int argc, char **argv)
{
        int i = 0;
        int j = 0;
        int size = 5; //size of the array being loaded, changes whole program to size 10, 20, 100, etc...
        int position = 0; //position of lowest value in the array
        int temp = 0; //temp variable for switching values around
        int lowval = 0; //lowest value in the array bounds
        int value[size]; //my array
        Queue *myque; //queue structure being used from a previous project, pulled with ehader file "quelist.h"
        myque = (Queue *) malloc (sizeof(Queue)); //malloc the queue
        myque -> head = myque -> tail = myque -> tmp = NULL; //initialize all parts to NULL so i know what they are doing and where they are
        if(argc < size+1) //if there isn't enough command-line arguments entered
        {
                for(i=0;i<size;i++)
                {
                        printf("Enter a value for slot %d: ", i);
                        scanf("%d", &value[i]);
                }
        }
        else //if there is enough command-line arguments
        {
                for(i=0;i<size;i++)
                        value[i] = atoi(argv[i+1]); //load the arguments into the array so that the processing for the stdin and command-line arguments
        }                                           //is the same. casted to an int via atoi().
        i = 0;
//meat of the selection sort
        while(j < size)
        {
                lowval = value[j]; //set the low value to be the first element in the array bounds
                for(i=j;i<size-1;i++)
                {
                        if(lowval > value[i+1])
                        { //if lowval is greater than the next value in the array
                                lowval = value[i+1]; //lowvalue is now the next value in an attempt to find the lowest value
                                position = i+1; //save the position of that low value
                        }
                }
                if(lowval != value[j]) //if lowvalue isnt the first position of the array bounds
                {
                        temp = value[j];
                        value[j] = lowval;
                        value[position] = temp; //bring the low value to the front
                }
                enqueue(myque, lowval); //start loading that queue!
                j++;
        }

        printf("This array is now sorted via a selection sort");
        for(i=0;i<size;i++)
                printf(" . %d", (dequeue(myque) -> value)); //dequeue returns a node, so we need to point to its value
        printf("\n");
        return 0;
}
</code>

===enqueue===
</code>
/*
This is a simple function to enqueue a node to a queue.
Accepts: A que struct containing the head, tail and a tmp node of the queue,  and a character value.
Returns: nothing
Requires the "linkedlist.h" header file, which is in "quelist.h"
*/
#include"quelist.h"

void enqueue(Queue *que, char val)
{
        Node *tmp1;
        tmp1 = (Node *) malloc (sizeof(Node));
        tmp1 -> value = val;

        if(que -> head == NULL)
        {
                que -> head = que -> tail = tmp1;
        }
        else
        {
                que -> head -> prev = tmp1;
                tmp1 -> next = que -> head;
                que -> head = que -> head -> prev;
        }
}
</code>
===Dequeue===
<code c>
/*
Deueue is a simple program to dequeue a node from a list.
Node *dequeue(Queue *)
Accepts: a queue struct
Returns: the dequeued node
*/
#include"quelist.h"

Node *dequeue(Queue *que)
{
        que -> tmp = que -> tail;
        if(que -> tail != que -> head)
        {
                que -> tail = que -> tail -> prev;
                que -> tmp -> prev = NULL;
                que -> tail -> next = NULL;
        }
        return (que -> tmp);
}
</code>
===quelist.h===
<code c>
#ifndef QUE_LIST_H
#define QUE_LIST_H
#include"linkedlist.h"

struct queue{
        struct node *head;
        struct node *tail;
        struct node *tmp;
};
typedef struct queue Queue;

Node *dequeue(Queue *);
void enqueue(Queue *, char);

#endif
</code>
===linkedlist.h===
contains the node structure
=====Execution=====
Again, if there is associated code with the project, and you haven't already indicated how to run it, provide a sample run of your code:

===stdin===
<cli>
lab46:~/src/DataS$ ./selsort
Enter a value for slot 0: 1
Enter a value for slot 1: 3
Enter a value for slot 2: 6
Enter a value for slot 3: 4
Enter a value for slot 4: 2
This array is now sorted via a selection sort . 1 . 2 . 3 . 4 . 6
lab46:~/src/DataS$
</cli>
===command-line===
<cli>
lab46:~/src/DataS$ ./selsort 4 8 9 5 1
This array is now sorted via a selection sort . 1 . 4 . 5 . 8 . 9
lab46:~/src/DataS$
</cli>
=====Reflection=====
I think i am getting the hang of this coding thing. I am learning at least 2 new powerful functions a week, and many other tiny ones. And I am able to implement them in a program when i need them without much trouble, like the atoi(). I used it here to cast command-line arguments saved as char ** to integers saved in a regular integer array, heck yes! that way i was able to save stdin or command line args to an array and then do the same processing reguardless of the way i got the data.
=====References=====
In performing this project, the following resources were referenced:

  * previous queue projects/libraries
  * the c programming quide
  * my mind
  * man page for atoi()
Lab46 Wiki

User Tools

Site Tools

Page Tools
