Problem Question
Write a program to implement Selection Sort.
Explanation of Problem
Selection Sort is a simple sorting algorithm. However, due to the high order of space-time complexity it incurs to sort a list, makes it impractical for large applications.
In selection sort the program iterates through the list of values as many times as the number of items in the list. Through each pass, the algorithm finds the minimum value in the list and assigns it to the first element. In the next pass, the algorithm works with the remaining list, except for the first element. Hence, the new minimum will be assigned to the first element of this sublist, which is actually second element of the overall list. Going forward this way, the list will be sorted after the algorithm has iterated the entire list as many times as the numer of elements. When the first element of the working sublist is assigend with new value, the value at the first element is exchanged with the value where the new minimum is found. Hence the algorithm is a type of Exchange Sort.
To understand selection sort better, consider a list of 5 numbers, [5, 3, 2, 1, 4]. Following is how selection sort would sort the list.
Unlike bubble sort, the working size of the list shrinks with every pass, hence it appears to be slightly better. However, in generalised Big-O notation, it would still have the quadratic complexity.
Code
#include <stdio.h>
/**@Title: SortingAlgorithms v1.2.c*
*@Language: ANSI C*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Toxifier*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 09-05-2015*
*/
#include <stdio.h>
int main()
{
int userChoice, outerLoop, innerLoop, minIndex, exchangeSpace, lengthNumberList = 0, originalNumberList[25], sortedNumberList[25];
printf ("Welcome to SortingAlgorithms v1.2\n");
printf ("Made by Toxifier\n");
do
{
printf ("\n1: Add an element to the list\n");
printf ("2: Display Original List\n");
printf ("3: Perform Selection Sort\n");
printf ("4: Empty List\n");
printf ("5: Exit\n");
printf ("Enter your choice: ");
scanf ("%d", &userChoice);
switch (userChoice)
{
case 1:
if (lengthNumberList >= 25)
{
printf ("\nArray Full\n");
}
else
{
printf ("\nEnter the value: ");
scanf ("%d", &originalNumberList[lengthNumberList]);
sortedNumberList[lengthNumberList] = originalNumberList[lengthNumberList];
lengthNumberList++;
}
break;
case 2:
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
printf ("\nOriginal List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", originalNumberList[outerLoop]);
}
}
break;
case 3:
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
for ( outerLoop = 0; outerLoop < lengthNumberList - 1; outerLoop++ )
{
minIndex = outerLoop;
for ( innerLoop = outerLoop + 1; innerLoop < lengthNumberList; innerLoop++ )
{
if (sortedNumberList[minIndex] > sortedNumberList[innerLoop])
{
minIndex = innerLoop;
}
}
if (minIndex != outerLoop)
{
exchangeSpace = sortedNumberList[outerLoop];
sortedNumberList[outerLoop] = sortedNumberList[minIndex];
sortedNumberList[minIndex] = exchangeSpace;
}
}
printf ("\nSorted List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", sortedNumberList[outerLoop]);
}
}
break;
case 4:
lengthNumberList = 0;
break;
case 5:
printf ("Thank You for using SortingAlgorithms v1.2\n");
printf ("Made by Toxifier\n");
break;
default:
printf ("\nWrong Choice!\n");
break;
}
}
while (userChoice != 5);
system("pause");
return 0;
}
Explanation of Code
#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H
int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.
printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.
scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.
int userChoice, outerLoop, innerLoop, minIndex, exchangeSpace, lengthNumberList = 0, originalNumberList[25], sortedNumberList[25]; -> Here we define the variables we are going to use in our program.
userChoice is used for the switch and do-while loop. The program is menu driven to allow user to change the array and move in any order they wish to.
outerLoop, innerLoop are the loop variables and exchangeSpace is the temporary space which we would use during value exchange operation.
lengthNumberList is used to track the final position of the arrays. originalNumberList[25], sortedNumberList[25] are the arrays which will hold the user input and the sorted list, respectively.
minIndex is used to track the index of minimum element in the list.
if (lengthNumberList >= 25)
{
printf ("\nArray Full\n");
}
else
{
printf ("\nEnter the value: ");
scanf ("%d", &originalNumberList[lengthNumberList]);
sortedNumberList[lengthNumberList] = originalNumberList[lengthNumberList];
lengthNumberList++;
}
This is the first case of the program where the user inputs the array values. Since the array is defined with maximum length of 25, an error is thrown to the user and they are not allowed to add more values to the list once the limit is reached.
If the array has enough space though, the user can proceed further and input a value to the array, which will get stored at the end of the list. Every user input is copied to the sortedNumberList as well, so that original list is inatct for future reference.
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
printf ("\nOriginal List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", originalNumberList[outerLoop]);
}
}
This is the second case of our program which is used to display the list created by the user so far. The code iterates through the array, originalNumberList and prints each element.
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
for ( outerLoop = 0; outerLoop < lengthNumberList - 1; outerLoop++ )
{
minIndex = outerLoop;
for ( innerLoop = outerLoop + 1; innerLoop < lengthNumberList; innerLoop++ )
{
if (sortedNumberList[minIndex] > sortedNumberList[innerLoop])
{
minIndex = innerLoop;
}
}
if (minIndex != outerLoop)
{
exchangeSpace = sortedNumberList[outerLoop];
sortedNumberList[outerLoop] = sortedNumberList[minIndex];
sortedNumberList[minIndex] = exchangeSpace;
}
}
printf ("\nSorted List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", sortedNumberList[outerLoop]);
}
}
This is the third case of our program where we have the probem statement addressed - implementing the selection sort algorithm. We first check the lenght of the array, and proceed with sorting only if there are any elements. The outer loop is used to iterate through the list as many times as the number of elements in the list, actually one less because the last element will be sorted automatically. The inner loop finds the index of the element with least value in the list between the current index pointed by outer loop till the end of the array. After the inner loop completes, before going through next iteration of outer loop, the minimum value's indx is compared with the outer loop counter. If the index is not same as outer loop, the values are exhcnaged. If the values are same, that means the first element of the list (or sublist in current iteration) is alredy placed at correct position and does not require any change in place. Once the list is sorted, it is displayed.
It is important to note that we are working on the sortedNumberList array insted of the originalNumberList array. The idea is to preserve the original list for any reference.
When implementing selection sort, this code is good enough to solve the problem. Rest of the code in our C program is only having a few useful additions which helps in easy execution of the program, making it more user friendly.
lengthNumberList = 0; -> This is the fourth case where we reset the lengthNumberList variable, which tracks the last element of the array. This helps in giving the user ability to redo any operation, without the need of closing and starting the program again.
printf ("Thank You for using SortingAlgorithms v1.2\n");
printf ("Made by Toxifier\n");
This is the fifth case statement, which allows the user to safely exit the program.
default:
printf ("\nWrong Choice!\n");
When using the case statement, it is important to use the break keyword at the end of each case to avoid the program from falling through the next case. It is also important to note the default case, which is important to handle any wrong values in the swithc-case logic.
system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.
Output(s)
Download Source Code
No comments:
Post a Comment
Need help?