Sorting an array algorithm in C and C++
|
Previous
|< Basic data structures |
Next
Binary search >| |
Sorting an array in non-descending or non-increasing order involves finding one permutation of the elements of the array in which the elements appear in non-descending order, i.e. non-increasing order.
Sort an array by selection method
Let's assume that we have a set of numbers:
int A [7] = {2, 5, 11, 4, 1, 9, 0};
To sort it in, for example, By decreasing the order from the largest to the smallest, we will do the following:
We pass through all the members of the series and find the greatest of all and put it first.
int A [7] = {2, 5, 11, 4, 1, 9, 0};
To sort it in, for example, By decreasing the order from the largest to the smallest, we will do the following:
We pass through all the members of the series and find the greatest of all and put it first.
|
This is done by comparing the current element A [j] with the element in the first place A [i]. If we encounter a larger one we are replacing the two elements, so that the greater of them goes to the first place. Otherwise, we take the next element for comparing A [j] without replacement. We continue to investigate and if we come back to the larger one, we substitute until we examine all the elements. When this ends up in the first place, it's the greatest of all. In our example, we would first replace 5 with 2, and 5 would be found on the first and then when we arrive at 11, we would replace 5 and 11. All other numbers are smaller. |
Figure 1: Sorting an array by selection method
|
The following code does this:
int i=0;
int for(int j = i+1; j < n; j++){
int for(int j = i+1; j < n; j++){
if(A[j] > A[i])
{
}{
/*Swap two elements*/
int b=A[i];
A[i]=A[j];
A[j]=b;
/*End of swap*/
}int b=A[i];
A[i]=A[j];
A[j]=b;
/*End of swap*/
|
Now that we have found the biggest one and put it first, we repeat the process for the remaining elements and we are looking for the largest ones. The procedure is identical, we only apply it to a subset that has not already found the largest element.
|
Figure 2: Sorting array algorithm-Selection Sort
|
The procedure is repeated for the next sub-arrays where it is found largest for all the remaining members on the right side except for the first two. By repeating the process, we have fewer and fewer sub-arrays that we sort until we sort out completely.
Figure 3: Sorting array algorithm-Selection Sort-finish
Finally, the entire sort code:
for(int i=0; i<N-1; i++)
{
for(int j=i+1; j<N; j++)
{
if(A[ j ] < A [ i ] )
{
int b=A[ i ];
A[ i ]=A[ j ];
A[ j ]=b;
}
}
}
for(int i=0; i<N-1; i++)
{
for(int j=i+1; j<N; j++)
{
if(A[ j ] < A [ i ] )
{
int b=A[ i ];
A[ i ]=A[ j ];
A[ j ]=b;
}
}
}
Example: Load the number of n array elements, then set a series of randomly generated n integers whose value is 0 to 100. Sort the array in descending order and print on the screen.
#include <iostream>
#include<stdlib.h>
#define DIM 20
using namespace std;
int main()
{
int a[DIM], n, j;
cin>>n;
if(n<=0 || n>DIM) return 1;
//Loading elements of a array
cout<<"Array:"<<endl;
for (int i=0; i<n; i++){
//cin>>a[i];//4,2,8,9,1,5,6
a[i]=rand()%100;
cout<<a[ i ]<<" ";
}
cout<<endl;
//Sorting array
for(int i=0;i<n-1;i++){
for(j=i+1; j<n; j++){
if(a[ j ] > a[ i ]){
//Replacement
int b=a[i];
a[i]=a[j];
a[j]=b;
}
}
}
cout<<"Sorted array:"<<endl;
for (int i=0; i<n; i++){
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
#include<stdlib.h>
#define DIM 20
using namespace std;
int main()
{
int a[DIM], n, j;
cin>>n;
if(n<=0 || n>DIM) return 1;
//Loading elements of a array
cout<<"Array:"<<endl;
for (int i=0; i<n; i++){
//cin>>a[i];//4,2,8,9,1,5,6
a[i]=rand()%100;
cout<<a[ i ]<<" ";
}
cout<<endl;
//Sorting array
for(int i=0;i<n-1;i++){
for(j=i+1; j<n; j++){
if(a[ j ] > a[ i ]){
//Replacement
int b=a[i];
a[i]=a[j];
a[j]=b;
}
}
}
cout<<"Sorted array:"<<endl;
for (int i=0; i<n; i++){
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
Sorting arrays by insertion method
Figure 4: Algorithm for sorting by insertion method
If an array (An) is assigned to elements of someone, arranged type T, which needs to be arranged in a non-ordering order, this sorting method starts from the assumption that we have arranged the initial part of the array, (this certainly applies to i = 2, since the sub-array with one element arranged) and in each step, beginning with i = 2 and increasing i, the i-th element is placed in the right place in relation to the first (arranged) i - 1.
Firstly, the currently examined element is inclined to auxiliary variable b. Thereafter, a consecutive comparison of the values aj and b for j = i-1, i-2, ..., 0 is performed. Each time it is determined that aj > b, the element aj is moved to the place aj + j. The cycle of comparing and moving ends when the first time it is not necessary to move or when it becomes less than zero.
Finally, it is still necessary to put the tested value from the variable b into its place, i.e. u element aj + 1.
Firstly, the currently examined element is inclined to auxiliary variable b. Thereafter, a consecutive comparison of the values aj and b for j = i-1, i-2, ..., 0 is performed. Each time it is determined that aj > b, the element aj is moved to the place aj + j. The cycle of comparing and moving ends when the first time it is not necessary to move or when it becomes less than zero.
Finally, it is still necessary to put the tested value from the variable b into its place, i.e. u element aj + 1.
