C Sorting

[prathiyus]

**i'm trying to sort the number in the ascending order,i have a problem in doing that....im quite new to c **

*my input is a={40,50,20,30};,b={20,30,40,50};my output will be a=20 30 40 50 ,b=40 50 20 30 *
sorting all the columns of a data by one of its column
    int a[10],b[10],i,j,n;
    int temp;
    printf("Enter the number of elements for A");
    scanf("%d",&n);
    printf("Enter %d integers \n ",n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    printf("Enter the number of elements of B");
        scanf("%d",&n);
    printf("Enter %d integers \n ",n);
    for(i=0;i<n;i++)
        scanf("%d",&b[i]);      

    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if (a[i]>a[j])
            {
            swap(a[i],a[j]);
            swap(b[i],b[j]);

                     }
             }
    }

    printf("\n After sorting \n");

    for(i=0;i<n;i++)

    printf("%d\n",a[i]);
    for(i=0;i<n;i++)

    printf("%d\n",b[i]);
}
swap(int x[],int i,int j)
{
int temp;
temp=x[i];
x[i]=x[j];
x[j]=temp;

}

[Gonbe]

Try to do it with 1 array first. There is no added value when working with two, and with your code you lose track of how many elements A contains. Your code also doesn't compile. (You call swap with 2 arguments while it has 3 for example)

Try to explain in words what you're trying to achieve. Looks like you read something about bubble sort, but wording it might help you understand it better yourself too. (Quack!)

[Adak]

Your sort is a substitution sort (very similar to a bubble sort), and your outer for loop should stop at i < n-1, instead of i < n. Because j is i+1, on the last loop.

[Gonbe]

Your sort is a substitution sort

Ah yes, I read over the code to quickly I guess. I've never actually used this one myself (and I don't think I ever will =P) but ensuring the current index is the smallest by repeatedly swapping elements further in the array with it if they are smaller seems a bit odd.

Why isn't the smallest value in the remaining section only looked up and then swapped with index i at the end?

[Ancient Dragon]

Why isn't the smallest value in the remaining section only looked up and then swapped with index i at the end?

Because that's a different sorting algorithm. For small amounts of data or data that is already nearly sorted insertion sort is as good and fast as most others, maybe faster. IMO It's also the easiest to code and remember.

[Gonbe]

Because that's a different sorting algorithm. For small amounts of data or data that is already nearly sorted insertion sort is as good and fast as most others, maybe faster. IMO It's also the easiest to code and remember.

It's not inserting the element at 'i' into the 'already sorted' section though. Instead of going through all elements of an array using 'i' and then doing a swap for every element 'j' that follows it if it's smaller than 'i', going through the remains and only remembering the lowest value and afterwards doing the swap doesn't really seem different to me. Only that you swap less but the principle is exactly the same.

[Schol-R-LEA]

If you need to sort two different arrays, then you need to test both of the arrays separately. It would make far more sense (in general, and in this specific case) to re-write the sorting algorithm as a function, which could then be passed the array to sort. Here is your code re-done in this manner (with minor corrections):

int* sort(int a[])
{
    int i, j;

    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if (a[i]>a[j])
            {
            swap(a[i],a[j]);
            }
        }
    }
    return a;
}

This also allows you to test the sorting algorithm with known test data, before trying to work on user input.

[prathiyus]

the problem is i want the array to be sorted like this
just an example to define the prob
char arr[4] = {'pq','aa','km','ls'};
int arr1[4] = {40,30,50,70};
my output will be
arr = aa km ls pq
arr1 = 30 50 70 40
the base array has to be sorted in the same way the corresponding elements are also rearranged

[Adak]

Insertion sort is VERY fast for small amounts of data, or nearly sorted (or fully sorted!), data.

But this is Substitution sort, and it's almost identical to Bubble sort, but the values being compared, are NOT adjacent. This was my first sort because it was easy to memorize.

@praythius, are you saying that the number DON'T stay associated with the same strings, during the sort? Seems like they should stay connected to each other.

If they DO stay connected, then the ?? is, do you want the string to be the dominant key, or the integers?

[Ancient Dragon]

use one of the arrays for comparisons, then when a swap is needed you swap the same elements in both arrays.

void sort(char* nm[], int a[], int n)
{
    int i, j;

    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if (strcmp(nm[i]) > strcmp(nm[j]))
            {
                swap(nm[i], nm[j]);
                swap(a[i],a[j]);
            }
        }
    }
}

[prathiyus]

yes the string is the base array,the logic is
"array to be sorted in the order determined by sorting the base array"

[Ancient Dragon]

If you want to get creative, use a third array as indirect addressing into the other two arrays

void sort(char* nm[], int a[], int index[], int n)
{
    int i, j;

    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if (strcmp(nm[index[i]]) > strcmp(nm[index[j]]))
            {
                swap(index[i],index[j]);
            }
        }
    }
}

int main()
{
   char nm[3][5];
   int index[5];
   int a[5];
   for(int i = 0; i < 5; i++)
      index[i] = i+1;
   sort(nm,a,index,5);

   // print
   for(int i = 0; i < 5; i++)
   {
       printf("%s\t%d\n", nm[index[i]], a[index[i]]);
    }
}

[prathiyus]

@ Ancient Dragon how to write swap function for this

[Schol-R-LEA]

Actually, my own approach to this would be to bundle the pairs into a struct:

struct pair
{
    int master, slave;
} arr[5];

Then sort them based on the value of the master element:

struct pair* sort(struct pair a[])
{
    int i, j;

    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if (a[i].master > a[j].master)
            {
                swap(a, i, j);
            }
        }
    }
    return a;
}

swap(struct pair x[], int i, int j)
{
    pair temp;

    temp.master = x[i].master;
    temp.slave  = x[i].slave;

    x[i].master = x[j].master;
    x[i].master = x[j].master;

    x[j].master = temp.master;
    x[j].slave  = temp.slave;
}

All this assumes you're familiar with structures already.

[prathiyus]

@Scol-R-Lea i tried your code im getting error in the swap function
expected expression befor 'struct'
expected ';' before { token

[Schol-R-LEA]

Oops, I dropped the void type on the function. Sorry about that.

[prathiyus]

@Scol-R-Lea i tried using void but it wont help
it shows error as
pair undeclared
expected ;
temp undeclared

[Schol-R-LEA]

sigh I also dropped the word struct in the declaration of temp. That line should read:

struct pair temp;

[prathiyus]

sorry,again an error
undefined error to swap

[Schol-R-LEA]

OK, I went and wrote a full test program for the sorting and swapping functions, and found another bug in it, which I've since fixed. Here's the final test program:

#include <stdio.h>

struct pair
{
    int master, slave;
} arr[5];


struct pair* sort(struct pair a[], int n);
void swap(struct pair x[], int i, int j);

int main()
{
    int i;

    arr[0].master = 5;
    arr[0].slave = 20;

    arr[1].master = 2;
    arr[1].slave = 30;

    arr[2].master = 4;
    arr[2].slave = 60;

    arr[3].master = 9;
    arr[3].slave = 10;

    arr[4].master = 1;
    arr[4].slave = 90;

    printf("original array: ");
    for (i = 0; i < 5; i++)
    {
        printf("{%d, %d}", arr[i].master, arr[i].slave);
        if (i < 4)
        {
            printf(", ");
        }
    }


    sort(arr, 5);

    printf("\n\nSorted Array: ");
    for (i = 0; i < 5; i++)
    {
        printf("{%d, %d}", arr[i].master, arr[i].slave);
        if (i < 4)
        {
            printf(", ");
        }
    }
    puts("");

    return 0;
}



struct pair* sort(struct pair a[], int n)
{
    int i, j;

    for(i = 0; i< n-1; i++)
    {
        for(j = i+1; j<n; j++)
        {
            if (a[i].master > a[j].master)
            {
                swap(a, i, j);
            }
        }
    }
    return a;
}

void swap(struct pair x[], int i, int j)
{
    struct pair temp;

    temp.master = x[i].master;
    temp.slave  = x[i].slave;

    x[i].master = x[j].master;
    x[i].master = x[j].master;

    x[j].master = temp.master;
    x[j].slave  = temp.slave;
}

This version of the swap() function should work correctly.

[prathiyus]

//can u help me to execute this

#include<stdio.h>




struct pair {

    int first,second;
}arr[10];
struct pair* sort(struct pair a[]);
void swap(struct pair x[], int i, int j);
int main()
{
int i,n;
    //int temp;
    printf("Enter the number of elements for A");
    scanf("%d",&n);
    printf("Enter %d integers \n ",n);
    for(i=0;i<n;i++)
        scanf("%d",&arr[i].first);
    printf("Enter the number of elements of B");
        scanf("%d",&n);
    printf("Enter %d integers \n ",n);
    for(i=0;i<n;i++)
        scanf("%d",&arr[i].second);      
struct pair* sort(struct pair a[])
{
    int i,j,n;
    for(i = 0; i < n-1;i++)
    {
        for(j = i+1;j<n;j++)
        {
            if(a[i].first > a[j].first)
            {
                swap(a,i,j);
            }
        }
    }    
    return a;
}

    void swap(struct pair x[], int i, int j)
    {
        struct pair temp;


        temp.first = x[i].first;
        temp.second =  x[i].second;

        x[i].first = x[j].first;
        //x[i].second = x[j].second;
        x[j].first = temp.first;
        x[j].second = temp.second;
    }
}    

[Adak]

This shows your program, with connected array data sorting. If you want to use structs, let me know. The example given for structs is somewhat more complex than necessary.

#include<stdio.h>

//struct pair {
  //  int first,second;
//}

void sort(int *, int *, int);
void swap(int *, int, int);

int main(void) {

   int i,n;
   int a[10],b[10];  
   printf("Enter the number of elements for A");
   n=5; //scanf("%d",&n);
   printf("Enter %d integers \n ",n);
   for(i=0;i<n;i++)
      a[i] = i; // scanf("%d",&arr[i].first);

   //printf("Enter the number of elements of B");
   //scanf("%d",&n);
   printf("Enter %d integers \n ",n);
   for(i=0;i<n;i++)
      b[i]= n-i; //scanf("%d",&arr[i].second);

   printf("\nBefore sorting\n  a:     b:\n\n");
   for(i=0;i<n;i++)
      printf("%3d    %3d\n",a[i],b[i]);   


   sort(a,b,n);    //sort with a as the key
   printf("\nAfter sorting, A is the key:\n  a:     b:\n\n");
   for(i=0;i<n;i++)
      printf("%3d    %3d\n",a[i],b[i]);   


   sort(b,a,n);    //sort with b as the key

   printf("\nAfter sorting, B is the key:\n  a:     b:\n\n");
   for(i=0;i<n;i++)
      printf("%3d    %3d\n",a[i],b[i]);   

   printf("\n");
   return 0;
}


void sort(int *x, int *x2, int n) {  //x could be a[] or b[]
   int i,j;
   for(i = 0;i < n-1; i++)
   {
      for(j = i+1;j<n;j++)
      {
         if(x[i] > x[j])
         {
            swap(x,i,j);
            swap(x2,i,j);
         }
      }
   }
}
void swap(int *c, int i, int j) {  //c could be x or x2 (and x could still be a[] or b[])
   int temp;
   temp = c[i];
   c[i] = c[j];
   c[j]= temp;
}

[prathiyus]

thanks,with or without struct but i need to show the correct output which i mentioned before

[Adak]

If you just want two arrays sorted, and the data is NOT connected, just remove x2 from sort, and call sort twice. With with sort(a,n), and again with sort(b,n).

If n for a and n for b are not the same size, then you need to use a different variables (easiest), to hold the size of the b array.

[prathiyus]

the problem is i want the array to be sorted like this
just an example to define the prob
char arr[4] = {'pq','aa','km','ls'};
int arr1[4] = {40,30,50,70};
my output will be
arr = aa km ls pq
arr1 = 30 50 70 40
the base array has to be sorted in the same way the corresponding elements are also rearranged

[prathiyus]

consider char arr as basearray

[Adak]

Quite similar to this:

#include <stdio.h>
#include <string.h>

//struct pair { //  int first,second;//}

void sort(char a[][3], int *, int);
void swap(char a[][3], int *, int, int);

int main(void) {

   int i,n,b[4]={40,30,50,70};
   char a[4][3]={{"pq"},{"aa"},{"km"},{"ls"}};  
   //printf("Enter the number of elements for A");
   n=4; //scanf("%d",&n);
   //printf("Enter %d integers \n ",n);
   //for(i=0;i<n;i++)
     // a[i] = i; // scanf("%d",&arr[i].first);

   //printf("Enter the number of elements of B");
   //scanf("%d",&n);
   //printf("Enter %d integers \n ",n);

   printf("\nBefore sorting\n  a:     b:\n\n");
   for(i=0;i<n;i++)
      printf("%s    %3d\n",a[i],b[i]);   


   sort(a,b,n);    //sort with a as the key
   printf("\nAfter sorting, A is the key:\n  a:     b:\n\n");
   for(i=0;i<n;i++)
      printf("%s    %3d\n",a[i],b[i]);   


   printf("\n");
   return 0;
}


void sort(char a[][3], int *b, int n) {  
   int i,j;
   for(i = 0;i < n-1; i++)
   {
      for(j = i+1;j<n;j++)
      {
         if(strcmp(a[i],a[j])>0)
         {
            swap(a,b,i,j);

         }
      }
   }
}
void swap(char a[][3], int *b, int i, int j) {  
   int temp;
   char ctemp[3];
   strcpy(ctemp,a[i]);
   strcpy(a[i], a[j]);
   strcpy(a[j], ctemp);

   //swap the b array
   temp = b[i];
   b[i] = b[j];
   b[j]= temp;
}

[prathiyus]

thanks,it really helps using the same concept,how to write the code,taking two integer arrays and giving input at runtime

[prathiyus]

@Adak,thank it really helps,using the concept how to sort two integer arrays for n numbers

[prathiyus]

@Adak,thanks it really helps,using the concept how to sort two integer arrays for n numbers