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
int main()
{
int arr1[25], arr2[25], i, j;
for ( i = 0, j = 24; i < 25; i++, j-- )
{
scanf ("%d", &arr1[i]);
arr2[j] = arr1[i];
}
printf("\nArray 1\n");
for ( i = 0; i < 25; i++ )
{
printf("%d ", arr1[i]);
}
printf("\nArray 2\n");
for ( i = 0; i < 25; i++ )
{
printf("%d ", arr2[i]);
}
printf("\n\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 arr1[25], arr2[25], i, j; -> Here we define the variables we are going to use in our program.
arr1[25], arr2[25] hold the user input numbers and reversed array respectively.
i, j are used as the loop variables to loop through the array.
for ( i = 0, j = 24; i < 25; i++, j-- )
{
scanf ("%d", &arr1[i]);
arr2[j] = arr1[i];
}
Here we loop through both arrays and do the required things. Look at the for loop definition. We have used the "," (comma) operator to initialise and increment multiple variables. This saves a few lines of code. Loop variables are initialised in one go and incrmeented/decremented in one go as well.
We then take user input to build first array. In the next step we copy that value in the last element of the second array. The loop variable "i" traverses "arr1" from left to right, and loop variable "j" traverses "arr2" from right to left. Hence we increment "i" and decrement "j".
printf("\nArray 1\n");
for ( i = 0; i < 25; i++ )
{
printf("%d ", arr1[i]);
}
printf("\nArray 2\n");
for ( i = 0; i < 25; i++ )
{
printf("%d ", arr2[i]);
}
Here we just loop through both arrays and print them for reference.
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.
int main()
{
int elements[25], loopCounter, positiveCount = 0, negativeCount = 0, evenCount = 0, oddCount = 0;
for (loopCounter = 0; loopCounter < 25; loopCounter++)
{
printf ("\nEnter Value #%d: ", loopCounter + 1);
scanf ("%d", &elements[loopCounter]);
if (elements[loopCounter] < 0)
{
negativeCount++;
}
else
{
positiveCount++;
}
if (elements[loopCounter] % 2 == 0)
{
evenCount++;
}
else
{
oddCount++;
}
}
printf ("\nNumber of Positive Numbers: %d", positiveCount);
printf ("\nNumber of Negative Numbers: %d", negativeCount);
printf ("\nNumber of Even Numbers: %d", evenCount);
printf ("\nNumber of Odd Numbers: %d\n", oddCount);
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 elements[25], loopCounter, positiveCount = 0, negativeCount = 0, evenCount = 0, oddCount = 0; -> Here we define the variables we are going to use in our program.
elements[25] hold the user input numbers.
loopCounter is used as the loop variable to loop through the array. The variables positiveCount, negativeCount, evenCount, oddCount are used to track the count of each type of number.
Here we loop through the entire array, get user input, and each input is checked whether it's odd/even/negative/positive. Appropriate count variable is incremented to store the count.
printf ("\nNumber of Positive Numbers: %d", positiveCount);
printf ("\nNumber of Negative Numbers: %d", negativeCount);
printf ("\nNumber of Even Numbers: %d", evenCount);
printf ("\nNumber of Odd Numbers: %d\n", oddCount);
After the loop, here we print the values of each variable to give the output stating the count of each number type in the user input.
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.
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.
Merge 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 merge sort algorithm is better than selection or bubble sort algorithms because of the space-time complexity, which reduces from quadratic to logarithmic, due to continue division of the data set. 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 merge sort without recursion, and the answer is yes. However, in this post today, we are going to implement it via recursion.
In merge sort the program the program divides the list into smaller sub-lists, and continues to do so until it is left with unit sized lists. It then takes two sublists, sorts their elements, and continues to work up by combining smaller sublist and sorting them.
To understand merge sort better, consider a list of 5 numbers, [5, 3, 2, 1, 4]. Following is how merge sort would sort the list. The blue-colored boxes represent the left sub-list in the iteration and pink boxes represent the right sub-array.
Unlike insertion/selection/bubble sort, the problem is solved by dividing and conquering the data set, hence sorting the list incrementally.
void merge(int inputArray[], int startIndex, int medianIndex, int inputArrayLength)
{
int leftLoop, rightLoop, remainderLoop;
int leftArrayLength = medianIndex - startIndex + 1;
int rightArrayLength = inputArrayLength - medianIndex;
int leftArray[leftArrayLength], rightArray[rightArrayLength];
void mergeSort(int inputArray[], int startIndex, int inputArrayLength)
{
if (startIndex < inputArrayLength)
{
int medianIndex = startIndex + (inputArrayLength - startIndex) / 2;
mergeSort (inputArray, startIndex, medianIndex);
mergeSort (inputArray, medianIndex + 1, inputArrayLength);
merge (inputArray, startIndex, medianIndex, inputArrayLength);
}
}
int main()
{
int userChoice, outerLoop, lengthNumberList = 0, originalNumberList[25], sortedNumberList[25];
printf ("Welcome to SortingAlgorithms v1.3\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 Merge 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
{
mergeSort (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.3\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 merge 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 mergeSort 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 merge sort, this code and the two functions merge and mergeSort 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 mergeSort(int inputArray[], int startIndex, int inputArrayLength)
{
if (startIndex < inputArrayLength)
{
int medianIndex = startIndex + (inputArrayLength - startIndex) / 2;
mergeSort (inputArray, startIndex, medianIndex);
mergeSort (inputArray, medianIndex + 1, inputArrayLength);
merge (inputArray, startIndex, medianIndex, inputArrayLength);
}
}
The function mergeSort 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). The length of the array represents the index of the last element (counting begins from 0).
This function implements Merge Sort algorithm in a recursive manner (note the function calls itself). The function first gets a suitable middle element to divide the list it is working with into two halves (equal, or almost equal; in the latter one list has one element more than the other).
The function then calls itself for the left half and the right half and then calls another function merge, to merge the two lists it worked on.
When calling itself recursively, mergeSort 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.
void merge(int inputArray[], int startIndex, int medianIndex, int inputArrayLength)
{
int leftLoop, rightLoop, remainderLoop;
int leftArrayLength = medianIndex - startIndex + 1;
int rightArrayLength = inputArrayLength - medianIndex;
int leftArray[leftArrayLength], rightArray[rightArrayLength];
The function merge is the place where actual sorting of elements happen. The function sorts the elements by merging the two sub-arrays, comparing each element and putting them in their correct place when doing so. It is important to note, that the program is passing the address of main array, sortedNumberList since the beginning, hence the sub-lists are actually changing data elements in the main array itself. Let's look at it further.
The function merge accepts 4 arguments: int inputArray[] (the address of the array being worked upon), int startIndex (the index of the first element of the sub-list), int medianIndex (the index of the middle 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 leftLoop, rightLoop, remainderLoop are the various loop variables. int leftArrayLength = medianIndex - startIndex + 1 stores the length of left sub-array and int rightArrayLength = inputArrayLength - medianIndex; stores the length of right sub-array. int leftArray[leftArrayLength], rightArray[rightArrayLength]; are the arrays that will hold the sublist data.
Left and right sub-arrays are then populated with the data, left of the median and right of the median.
Next, the while loop compares all the elements of both sub arrays and put them at appropriate positions. Whichever element is successfully put in place, should not be repeated in comparisons, hence the loop counter for that list is incremented. However, it is important to note that once either of the lists is empty, the remaining elements of the other list are left as-is. Hence, we have the other two while loops, that push in the remaining elements. Since the mergeSort function calls merge with lists as small as 2 elements, the remaining sub-list is always sorted. The remainderLoop variable is pointing to the element of main array that should be replaced. Hence, in the end when the control comes out of the merge function, the part of the list is sorted which it was working with.
The combination of mergeSort and merge 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.3\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.
