Re: Beginners Tutorial : The C-language:: Tutorial-20
Hello everyone again this is simplycoder and welcome to the 20[SUP]th[/SUP] tutorial of C-programing.
In this tutorial, we are going to learn more on arrays.
In last tutorial,we have seen how to reverse an array and concept of histogram using arrays.
In this tutorial, we are going to see how to sort an array using different algorithms.
So let us begin with our first program.
- WAP to sort an array of integers in acending order.
So how shall we go about this program?
Solution 1:
- Take the array, and compare the values, in current location and rest of the array . Swap if necessary.
- Repeat the step-1 for n-1 times, where n are the number of elements.
So from the above steps, we can easily come to know that we require nested for-loops.
The first for loop is required to traverse the array from index 0 to index n-1.
The second for loop is required to compare the indices and traverse the array.
let us assume the array to be
array[]={4,3,2,1}
The expected output is 1,2,3,4
array[0]=4.
array[1]=3.
array[2]=2.
array[3]=1.
Let us follow our algorithm.
let us assume our index of first for loop to be index_one and that of second for loop is index_two.
to compare the elements, we know that index_two=index_one+1.
so let us start now.
array is {4,3,2,1}
Iteration 1.1:
Value of index_one=0.
Value of index_two=1.
Compare array[0] with array[1], is swap required? Yes.
Now the array is {3,4,2,1}
Iteration 1.2:
Value of index_one=0.
Value of index_two=2.
Compare array[0] with array[2], is swap required? Yes.
Now the array is {2,4,3,1}
Iteration 1.3:
Value of index_one=0.
Value of index_two=3
Compare array[0] with array[3], is swap required? Yes.
Now the array is {1,4,3,2}
See after the first main interation, we have found the smallest value in the array and have placed it in correct place aswell.
Now let us go for the second iteration.
the array is {1,4,3,2}
Iteration 2.1:
Value of index_one=1.
Value of index_two=2.
Compare array[1] with array[2], is swap required? Yes.
Now the array is {1,3,4,2}
Iteration 2.2:
Value of index_one=1.
Value of index_two=3.
Compare array[1] with array[2], is swap required? Yes.
Now the array is {1,2,4,3}
So now let us go to our third iteration.
the array is {1,2,4,3}
Iteration 3.1:
Value of index_one=2.
Value of index_two=3.
Compare array[2] with array[3], is swap required? Yes.
Now the array is {1,2,3,4}
Thus you can now see that the array is sorted.
We are now in a position to write code for above algorithm.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*Author : simplycoder*/
int main(int argc, char *argv[])
{
int index_one,index_two,temp;
int array[]={4,3,2,1};
int size_of_array=sizeof(array)/sizeof(int);
for(index_one=0;index_one<size_of_array-1;index_one++)
{
for(index_two=index_one+1;index_two<size_of_array;index_two++)
{
if(array[index_one]>array[index_two])
{
temp=array[index_one];
array[index_one]=array[index_two];
array[index_two]=temp;
}
}
}
for(index_one=0;index_one<size_of_array;index_one++)
printf("%d ",array[index_one]);
printf("\n\n\n");
system("PAUSE");
return 0;
}
Ok this one was one simple type of sorting, at this moment we are not interested in performance of algorithms, efficiency and other advance stuff.
We are not even interested in the names of algorithms that we are going to use. In this way, we would avoid being channelized.
So above algorithm finds the smallest value in the first main iteration and places it correctly, then it finds out the second smallest element,places it correctly.
In our next solution, we are going to modify above algorithm such that it finds the greatest value first and places it in the correct place.
So how do we proceed it.
We shall compare the adjacent elements, find the greater of the two and swap the places.
Repeat this till we have compared all the elements in array.
We shall assume the array to be{4,3,2,1}
Iteration 1.1:
Value of index_one=0.
Value of index_two=0.
Value of index_two+1=1.
Compare array[0] with array[1], is swap required? Yes.
Now the array is {3,4,2,1}
Iteration 1.2:
Value of index_one=0.
Value of index_two=1.
Value of index_two+1=2.
Compare array[1] with array[2], is swap required? Yes.
Now the array is {3,2,4,1}
Iteration 1.3:
Value of index_one=0.
Value of index_two=2
Value of index_two+1=3.
Compare array[2] with array[3], is swap required? Yes.
Now the array is {3,2,1,4}
See after the first main interation, we have found the largest value in the array and have placed it in correct place aswell.
Now let us go for the second iteration.
the array is {3,2,1,4}
Iteration 2.1:
Value of index_one=1.
Value of index_two=0
Value of index_two+1=1
Compare array[0] with array[1], is swap required? Yes.
Now the array is {2,3,1,4}
Iteration 2.2:
Value of index_one=1.
Value of index_two=1.
Value of index_two+1=2.
Compare array[1] with array[2], is swap required? Yes.
Now the array is {2,1,3,4}
So now let us go to our third iteration.
the array is {2,1,3,4}
Iteration 3.1:
Value of index_one=2.
Value of index_two=0.
Value of index_two+1=1.
Compare array[0] with array[1], is swap required? Yes.
Now the array is {1,2,3,4}
Thus you can now see that the array is sorted.
We are now in a position to write code for above algorithm.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*Author : simplycoder*/
int main(int argc, char *argv[])
{
int index_one,index_two,temp;
int array[]={4,3,2,1};
int size_of_array=sizeof(array)/sizeof(int);
for(index_one=0;index_one<size_of_array;index_one++)
{
for(index_two=0;index_two<size_of_array-1;index_two++)
{
if(array[index_two]>array[index_two+1])
{
temp=array[index_two];
array[index_two]=array[index_two+1];
array[index_two+1]=temp;
}
}
}
for(index_one=0;index_one<size_of_array;index_one++)
printf("%d ",array[index_one]);
printf("\n\n\n");
system("PAUSE");
return 0;
}
This is it for this tutorial, In the next tutorial, we are going to see how to delete duplicates in the array.
Its very important to practice. Try comming up with your own algorithms of sorting an array.
Until the next time, take care.
Caio.