Hi! This is not a tutorial, though I'll explain any code I post here. On this blog I post source codes of various programs I have written, though the questions/programming problems may or may not be my own. These include solutions to some questions of some good books too. Not too language specific, since I'll be posting codes in C, C++, Java, C#, etc. For contact information, see my Disclosure Policy, for more info, check out my first post: http://letsplaycoding.blogspot.com/2014/03/welcome.html
Write a program to implement Sieve of Eratosthenes.
Explanation of Problem
Sieve of Eratosthenes is a simple algorithm which is used to find prime numbers easily and in a quick way. As compared to traditional way where we divide each number with every number before them to check if they are prime or not, sieve of Eratosthenes removes all mulitples of a number as it progresses forward, thus eliminating the need of a lot of extra comparisons. Hence the algorithm makes it very efficient to find prime numbers.
To implement the sieve of Eratosthenes, we would follow the following steps.
Step one: Fill and array with numbers 1 to n.
Step two: Starting with the number "2", set all its multiples to zero.
Step three: Proceed to the next non-zero element and set all its multiples to zero.
Step four: Repeat step three until all the multiples of all the non zero elements are set to zero.
Step five: At the conclusion of step four, all the non zero entries left in the array would be prime numbers; so print out these numbers.
As you can see in this algorithm the way prime numbers are derived, is far easier and incurs less amount of time as compared to the traditional way how we check if a number is prime or not where in, we would loop through all the numbers until that number and Keep checking if any of those numbers is full divisor of that number, which we are checking to be prime or not. What we are doing in this implementation is that we end up removing all the entries which are multiples of a number in each pass, for example when we are working with the number 2 we remove all its multiples in the first pass of the list itself so we are not going to check all the Even Numbers again and again for all the numbers before that, to check whether or not they have a full divisor or not. Hence, this algorithm saves some time, and in the end we have some elements which are non zero which represent the prime numbers and some elements which are zero which represent the non prime numbers. The prime numbers are left above the sieve as non-zero and the numbers which are non Prime get out of the sieve as zeroes.
Refer the following example to better understand how it works.
The implementation is fairly simple so let's dive into the code.
#include <stdio.h>
int main()
{
int userInput, outerLoop, innerLoop, numberList[10000];
printf ("Welcome to SieveOfEratosthenes\n");
printf ("Made by Toxifier\n");
printf ("Enter the number upto which to find prime numbers (upto 9999): ");
scanf ("%d", &userInput);
for (outerLoop = 2; outerLoop <= userInput; outerLoop++)
{
if (numberList[outerLoop] != 0)
{
printf("%d ", numberList[outerLoop]);
}
}
printf ("\nThank You for using SieveOfEratosthenes\n");
printf ("Made by Toxifier\n");
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 userInput, outerLoop, innerLoop, numberList[10000]; -> Here we define the variables we are going to use in our program.
outerLoop and innerLoop are the loop variables.
userInput is used to gather user input. It defines the number upto which you want the program to find prime numbers. numberList[10000] is the array which will hold the numbers, and be worked upon to have only prime numbers in the end.
Here we implement the Sieve of Eratosthenes algorithm. We start with number 2 and go upto the high value entered by user. We then mark all multiple of that number as 0. Looking at the loop, you'd notice that the inner loop starts from outerLoop * outerLoop. This is because all the multiples prior to that value are already removed by the previos iteration. For exmaple, when the loop works for number 2, it removes all even numbers. Hence, for 3, we dont need to consider 6 and start with 9 directly. Similarly, for 5, 10 and 20 are removed by 2 and 15 by 3, hence we directly start with 25. And so on.
for (outerLoop = 2; outerLoop <= userInput; outerLoop++)
{
if (numberList[outerLoop] != 0)
{
printf("%d ", numberList[outerLoop]);
}
}
Here we print the remaining values on the sieve, all non zero values from 2 onwards. This is the list of prime numbers.
printf ("Thank You for using SieveOfEratosthenes\n");
printf ("Made by Toxifier\n");
Here we just print a goodbye message for user before exiting the program :)
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.
Quick Sort is considered an intermediate level sorting algorithm, from implementation complexity perspective. Usually, it is taught to students once they are familiar with basic programming constructs and recursion. The quick sort algorithm is better than selection or bubble sort algorithms because of the space-time complexity, which reduces from quadratic to logarithmic, due to continuous division of the data set. However, in the worst-case scenario, the complexity tends to be quadratic, so it may not be the best algorithm always. This algorithm is used to demonstrate recursion and divide and conquer problem solving techniques.
A question may arise here if it is possible to implement quick sort without recursion, and the answer is yes. However, in this post today, we are going to implement it via recursion.
In quick sort, the program identifies an element, called 'pivot', and sorts the list around this pivot value. There are various ways to identify the first pivot to start with. One popular method is to choose the first or the last element as pivot. In this post, we are going to use the last element as initial pivot. Once a pivot value is chosen, the algorithm tries to place this pivot value at position better than its current position. It does so by partitioning the list around the pivot (one list of value before pivot and other list after the pivot), putting values less than pivot one by one, thus shifting the values higher than pivot. At the end, the values of initial pivot and the value next to the last index where the value was swapped are exchanged, and the new position of pivot element is the new pivot index. Now we have two lists, one to the left of the pivot and one to the right. The algorithm then quicksorts the left list and the right list, by recursively calling itself.
To understand quick sort better, consider a list of 5 numbers, [5, 3, 2, 1, 4]. Following is how quick sort would sort the list. The blue-colored box represent the pivot.
Unlike insertion/selection/bubble sort, the problem is solved by dividing and conquering the data set, hence sorting the list incrementally.
int partition (int inputArray[], int startIndex, int inputArrayLength)
{
int valueAtPivot = inputArray[inputArrayLength];
int leastIndex = startIndex - 1;
int loopVar, exchangeSpace;
void quickSort(int inputArray[], int startIndex, int inputArrayLength)
{
if (startIndex < inputArrayLength)
{
int pivotIndex = partition (inputArray, startIndex, inputArrayLength);
quickSort (inputArray, startIndex, pivotIndex - 1);
quickSort (inputArray, pivotIndex + 1, inputArrayLength);
}
}
int main()
{
int userChoice, outerLoop, lengthNumberList = 0, originalNumberList[25], sortedNumberList[25];
printf ("Welcome to SortingAlgorithms v1.4\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 Quick 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
{
quickSort (sortedNumberList, 0, lengthNumberList - 1);
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.4\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, 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 is the loop variable.
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.
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 intact for future reference.
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.
This is the third case of our program where we have the problem statement addressed - implementing the quick sort algorithm. We first check the length of the array, and proceed with sorting only if there are any elements. The program then calls the function quickSort to sort the list. Once the list is sorted, it is displayed.
It is important to note that we are working on the sortedNumberList array instead of the originalNumberList array. The idea is to preserve the original list for any reference.
When implementing quick sort, this code and the two functions partition and quickSort are 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.
void quickSort(int inputArray[], int startIndex, int inputArrayLength)
{
if (startIndex < inputArrayLength)
{
int pivotIndex = partition (inputArray, startIndex, inputArrayLength);
quickSort (inputArray, startIndex, pivotIndex - 1);
quickSort (inputArray, pivotIndex + 1, inputArrayLength);
}
}
The function quickSort expects 3 parameters. The array to be sorted (int inputArray[]); the starting point of the array for the function call (int startIndex); and the length of the array (int inputArayLength).
This function implements Quick Sort algorithm in a recursive manner (note the function calls itself). The function only works if there are more than 1 elements in the list. It would call the function partition to move the pivot element to a better place than it is at right now (last position), and retrieve the index of the new place where the pivot element is moved to. It then calls itself, first on the list to the left of pivot, then on the list to right of the pivot. Eventually dividing the list and working upon the sub-lists.
When calling itself recursively, quickSort keeps dividing the list it works upon further, until the list reduces to unit size. Hence, the entire logic is wrapped under an if condition, which says that the function should do something only if the starting position of the array is less than the number of elements in the list, basically giving the control back to the previous recursive call upon encountering a single element sub-array.
int partition (int inputArray[], int startIndex, int inputArrayLength)
{
int valueAtPivot = inputArray[inputArrayLength];
int leastIndex = startIndex - 1;
int loopVar, exchangeSpace;
The function partition is the place where actual sorting of elements happen. The function puts the elements smaller than the pivot one by one, shifting the larger values further down the list and finally exchanging the first largest value from its last position after shifting, with the pivot value. The function then returns the new index of the pivot. Since the function quickSort calls this function for smaller lists, the overall lists eventually gets sorted with a combination of these two functions.
The function partition accepts three arguments: int inputArray[] (the address of the array being worked upon), int startIndex (the index of the first element of the sub-list), int inputArrayLength (the length of the sublist).
Additionally, we have a bunch of variables defined to aid in the process. int valueAtPivot that holds the value of the pivot element; int leastIndex which is used to track the position at which the next element needs to be put at; int loopVar, exchangeSpace which are used to loop through the sub-list and to exchange the values when needed.
Next, the for loop iterates through the sub-list and keep shifting any elements higher than pivot down the list. It is important to note, the values are not put at the correct position in one go, they eventually land in place. Hence, in worst case scenario, the list gets iterated multiple times, causing quadratic complexity of the algorithm. After the loop, int leastIndex is pointing to the index at which the first high element is placed at in the end. The function then exchanges the value at this index and that at original pivot and returns the new index of pivot to work further.
The combination of quickSort and partition calls, eventually sorts the entire array.
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.4\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 switch-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.
