I am trying to create a function that will rearrange an array so it is in descending order. The array is made up from positive integers, with no two equal elements. This is what I have:
int check (int *v, int n){
int i;
for (i=0; i<n; i++){
if (v[i] != -1){
return -1;
break;
}
else return 1;
}
}
void sortVector (int *v, int n){
int i, k, j=0, vp[n];
while (check(v,n) == -1){
for (i=0; i<n; i++){
for (k=i+1; k<n; k++){
if (v[k] > v[i]) break;
else if (k == n-1){
vp[j] = v[i];
v[i] = -1;
j++;
}
}
}
}
for (i=0; i<n; i++)
v[i] = vp[i];
}
Which is not working correctly. I've been thinking about this for the past week so some pointers would be great. Thanks.
I tried to follow the idea that you have stated in your comment by starting from your code above and made few changes and here is the two final functions
#include <stdio.h>
int check (int *v, int n)
{
int i;
for (i=0; i<n; i++)
{
if (v[i] != -1)
{
return -1; // break is useless because return has the same effect
}
}
return 1; // you need to add a return here to handle all the cases
// the case if the loop is not entered you need to return a value
}
void sortVector (int *v, int n)
{
int i, k, j=0, vp[n];
int maxIndex=0;//you need to add this variable in order to keep track of the maximum value in each iteration
while (check(v,n) == -1)
{
for (i=0; i<n; i++)
{
maxIndex=i; //you suppose that the maximum is the first element in each loop
for (k=i+1; k<n; k++)
{
if (v[k] > v[maxIndex])
maxIndex=k; // if there is another element greater you preserve its index in the variable
}
//after finishing the loop above you have the greatest variable in the array which has the index stored in maxIndex
vp[i] = v[maxIndex]; // put it in vp array
v[maxIndex]=v[i];//put it in treated elements zone
v[i]=-1;// make it -1
j++;
}
}
for (i=0; i<n; i++)
v[i] = vp[i];
}
This is the test
int main()
{
int tab[]= {1,152,24,11,9};
sortVector (tab, 5);
int i=0;
for(i=0; i<5; i++)
{
printf("%d ",tab[i]);
}
return 0;
}
which gives the desired output
152 24 11 9 1
Note: You can improve your code by making swaps on the same array instead of allocating another array !
There are really lots of algorithms for sorting. A simple algorithm is to find the minimum element in your array and put it in the first position by swapping it with whatever item was in the first position and then recursively sorting the array but this time starting at the next position.
void sort(int a[], int l, int r)
{ if(l == r) return; /* 1-elemnt array is already sorted */
int min = l;
for(int i = l+1; i <= r; i++)
{ if(a[i] < a[min])
{ min = i;
}
}
swap(a[l], a[min]);
sort(a, l+1, r);
}
You can also do it iteratively.
Perhaps, the intention like following
int check (int *v, int n){
int i;
for (i=0; i<n; i++){
if (v[i] != -1){
return -1;
//break; //This code that does not reach
}
//else return 1; //move to after for-loop
}
return 1;
}
void ordenaVetor (int *v, int n){
int i, k, j=0, vp[n];
while (check(v,n) == -1){
for (i=0; i<n; i++){
if(v[i]<0) continue;//Element of -1 excluded. v[k] too.
for (k=i+1; k<n; k++){
if (v[k]>=0 && v[i] < v[k]) break;
}
if (k == n){
vp[j] = v[i];
v[i] = -1;
j++;
break;//start over
}
}
}
for (i=0; i<n; i++){
v[i] = vp[i];
}
}
You could use an existing sort implementation instead of reinventing the wheel:
#include <stdlib.h>
int desc(void const *a, void const *b)
{
if ( *(int *)a < *(int *)b ) return 1;
return -1;
}
void sortVector (int *v, int n)
{
qsort(v, n, sizeof *v, desc);
}
