Thread: sorting array in increasing order

  1. #1
    Registered User
    Join Date
    Jul 2020
    Posts
    16

    sorting array in increasing order

    When we have

    list = 5 4 3 2 1

    how to sort array in increasing order ? list = 1 2 3 4 5

    here is process how I think

    5 - 4 compare if greater then update 4 5 3 2 1
    5 - 3 compare if greater then update 4 3 5 2 1
    5 - 2 compare if greater then update 4 3 2 5 1
    5 - 1 compare if greater then update 4 3 2 1 5

    and so more

    I wrote my program to sort array in increasing order


    Code:
    #include <stdio.h>
    
    int main()
    {
        int i = 0; int j = 0; int k = 0;
        
        int list[5] = {5, 4, 3, 2, 1};
        
        int temp[5];
        
        for (i = 0; i <5; i++)
        {
             for (j = i+1 ; j <5; j++)
             {
                 if (list[i]>list[j]) // if the one is greater then other swap value 
                 {
                     temp[k] = list[j];
                     list[i] = temp[k];
                     
                 }
             }
             
        }
        
        return 0;
    }
    What's wrong in code
    Last edited by Djsarkar; 08-02-2020 at 01:59 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,169
    You're not swapping anything at line 17.

    Swaps typically take 3 lines of code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jul 2020
    Posts
    16
    If we have X = 1 and Y = 3 when we will swap it would X = 3 and Y = 1

    X=1, Y=3, Temp = 0

    Temp = X=1
    X = Y = 3
    Y = temp = 1

    After swapping X =3 and Y = 1

    Code:
    #include <stdio.h> 
    int main()
    {
        int i = 0; int j = 0; int k = 0;
         
        int list[5] = {5, 4, 3, 2, 1};
         
        int temp[5];
         
        for (i = 0; i <5; i++)
        {
             for (j = i+1 ; j <5; j++)
             {
                 if (list[i]>list[j]) // if the one is greater then other swap value 
                 {
                     temp[k] = list[i];
                     list[i] = list[j];
                     list[j] = temp[k];
                      
                 }
                 printf("%d", list[j]);
             }
              
        }
         
        return 0;
    }
    Last edited by Djsarkar; 08-02-2020 at 04:29 AM.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,169
    > printf("%d", list[j]);
    Move it into the i loop, and print subscript i instead.

    Also, you don't need an array of temp, just one.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Jul 2020
    Posts
    16
    Quote Originally Posted by Salem View Post
    > printf("%d", list[j]);
    Move it into the i loop, and print subscript i instead.

    Also, you don't need an array of temp, just one.
    Thanks
    Code:
    #include <stdio.h> 
    
    int main()
    {
        int i = 0; int j = 0; 
          
        int list[5] = {5, 4, 3, 2, 1};
          
        int temp;
          
        for (i = 0; i <5; i++)
        
        {
           
            
             for (j = i+1 ; j <5; j++)
             {
                 
                 if (list[i]>list[j]) // if the one is greater then other swap value 
                 {
                     temp = list[i];
                     list[i] = list[j];
                     list[j] = temp;
                       
                 }
                 
             }
             
              printf("%d", list[i]);
               
        }
          
        return 0;
    }

  6. #6
    Registered User
    Join Date
    Feb 2019
    Posts
    721
    Code:
    #define INTARRAY_ELEMENTS(a) \
      (sizeof a / sizeof a[0])
    
    static int cmp( const void *ap, const void *bp )
    { return (*(int *)ap > *(int *)bp) - ( *(int *)ap < *(int *)bp ); }
    
    ...
      int array[] = { 5, 4, 3, 2, 1 };
    ...
      qsort( array, INTARRAY_ELEMENTS(array), sizeof array[0], cmp );

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,169
    > return (*(int *)ap > *(int *)bp) - ( *(int *)ap < *(int *)bp );
    Unnecessarily terse, and contains a bug.
    Try again.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Registered User
    Join Date
    Feb 2019
    Posts
    721
    A more "generic" approach:
    Code:
    #include <stdlib.h>
    
    // Comparison funcions named after type and identifier.
    #define QSORT_CMP_FN_ASC(T,FN) FN ## _ ## T ## _A
    #define QSORT_CMP_FN_DESC(T,FN) FN ## _ ## T ## _D
    
    // Definition of comparison functions based on type and identifier.
    #define QSORT_CMP_ASC(T,FN) \
      int QSORT_CMP_FN_ASC(T,FN) ( const void *a, const void *b ) \
      { \
        return (*(const T *)a > *(const T *)b) - \
               (*(const T *)a < *(const T *)b); \
      }
    
    #define QSORT_CMP_DESC(T,FN) \
      int QSORT_CMP_FN_DESC(T,FN) ( const void *a, const void *b ) \
      { \
        return (*(const T *)a < *(const T *)b) - \
               (*(const T *)a > *(const T *)b); \
      }
    
    // qsort() function call based on ponter to buffer, number of elements, type and identifier
    #define QSORT_ASC_CALL(ptr,E,T,FN) \
      qsort( ptr, E, sizeof(T), QSORT_CMP_FN_ASC(T,FN) )
    
    #define QSORT_DESC_CALL(ptr,E,T,FN) \
      qsort( ptr, E, sizeof(T), QSORT_CMP_FN_DESC(T,FN) )
    
    
    // Define ascending comparison static function for ints (qsort).
    static QSORT_CMP_ASC(int, cmp)
    
    // Example for ascending sort.
    void sort( int *p, size_t elements )
    { QSORT_ASC_CALL( p, elements, int, cmp ); }

  9. #9
    Registered User
    Join Date
    Feb 2019
    Posts
    721
    Quote Originally Posted by Salem View Post
    > return (*(int *)ap > *(int *)bp) - ( *(int *)ap < *(int *)bp );
    Unnecessarily terse, and contains a bug.
    Try again.
    Do you mind to clarify?

  10. #10
    Registered User
    Join Date
    May 2012
    Posts
    424
    There's a host of sorting algorithms. The one that is usually used in practice is quicksort, because it is fast and fairly easy to implement. However it requires recursion.

    Selection sort or insertion sort are easier to understand, and actually faster for very small arrays, but unacceptably slow for large arrays. Bubble sort is taught in introductory computer science classes. It's not a very good algorithm, but it's a good example of an algorithm. Merge sort is easier than quicksort and has similar good performance, but it's slightly tricky to code correctly.

    There are many more.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  11. #11
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    174
    Quote Originally Posted by flp1969 View Post
    A more "generic" approach:
    Code:
    #include <stdlib.h>
    
    // Comparison funcions named after type and identifier.
    #define QSORT_CMP_FN_ASC(T,FN) FN ## _ ## T ## _A
    #define QSORT_CMP_FN_DESC(T,FN) FN ## _ ## T ## _D
    
    // Definition of comparison functions based on type and identifier.
    #define QSORT_CMP_ASC(T,FN) \
      int QSORT_CMP_FN_ASC(T,FN) ( const void *a, const void *b ) \
      { \
        return (*(const T *)a > *(const T *)b) - \
               (*(const T *)a < *(const T *)b); \
      }
    
    #define QSORT_CMP_DESC(T,FN) \
      int QSORT_CMP_FN_DESC(T,FN) ( const void *a, const void *b ) \
      { \
        return (*(const T *)a < *(const T *)b) - \
               (*(const T *)a > *(const T *)b); \
      }
    
    // qsort() function call based on ponter to buffer, number of elements, type and identifier
    #define QSORT_ASC_CALL(ptr,E,T,FN) \
      qsort( ptr, E, sizeof(T), QSORT_CMP_FN_ASC(T,FN) )
    
    #define QSORT_DESC_CALL(ptr,E,T,FN) \
      qsort( ptr, E, sizeof(T), QSORT_CMP_FN_DESC(T,FN) )
    
    
    // Define ascending comparison static function for ints (qsort).
    static QSORT_CMP_ASC(int, cmp)
    
    // Example for ascending sort.
    void sort( int *p, size_t elements )
    { QSORT_ASC_CALL( p, elements, int, cmp ); }


    Or maybe just make the comparison a macro and let the user define the function. Might make things a little clearer anyway:



    Code:
    #include <stdlib.h>
    
    #define SORT(array, length, compare)\
    qsort(array, length, sizeof(*array), (int (*)(const void*, const void*))compare)
    
    #define STACK_SORT(array, compare)\
    SORT(array, sizeof(array)/sizeof(*array), compare)
    
    #define COMPARE(left, right) (((left) > (right)) - ((left) < (right)))
    
    /* TEST */
    
    #include <stdio.h>
    
    struct thing
    {
     int id;
    };
    
    int compare_things(struct thing* thing_one, struct thing* thing_two)
    {
     return COMPARE(thing_one->id, thing_two->id);
    }
    
    int main()
    {
     struct thing things[] = {{ 4 }, { 1 }, { 2 }, { 9 }, { 7 }};
     STACK_SORT(things, compare_things);
     for(size_t tdx = 0; tdx < 5; ++tdx)
      printf("%d ", things[tdx].id);
     puts("");
    }
    The power of null.

  12. #12
    Registered User
    Join Date
    Feb 2019
    Posts
    721
    Quote Originally Posted by Malcolm McLean View Post
    However it requires recursion.
    You are aware that any recursive routine can be made without recursion, right?

    Here's a quicksort without recursion (using an allocated stack):
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ARRAY_ELEMENTS(a) ( sizeof a / sizeof a[0] )
    #define swap(a,b) { int t; t=(a); (a)=(b); (b)=t; }
    
    static ssize_t partition( int *arr, ssize_t l, ssize_t h )
    {
      ssize_t i, j;
      int x;
    
      x = arr[h];
      i = l - 1;
    
      for ( j = l; j <= h - 1; j++ )
        if ( arr[j] <= x )
        {
          i++;
          swap( arr[i], arr[j] );
        }
    
      swap( arr[i + 1], arr[h] );
    
      return i + 1;
    }
    
    void quickSort( int *arr, ssize_t l, ssize_t h )
    {
      ssize_t *stack, top, p;
      size_t size;
    
    #define PUSH(v) do stack[++top] = (v); while(0)
    #define POP(v) do v = stack[top--]; while(0)
    
      size = sizeof( ssize_t ) * ( h - l + 1 );
      if ( !( stack = malloc( size ) ) )
      {
        fprintf( stderr, "ERROR allocating memory (%zd bytes) for quickSort() stack!\n", size );
        exit( EXIT_FAILURE );
      }
    
      top = -1;
    
      // push initial values of l and h to stack
      PUSH( l );
      PUSH( h );
    
      // Keep popping from stack while is not empty
      while ( top >= 0 )
      {
        // Pop h and l
        POP( h );
        POP( l );
    
        // Set pivot element at its correct position
        p = partition( arr, l, h );
    
        // If there are elements on left side of pivot,
        // then push left side to stack
        if ( p - 1 > l )
        {
          PUSH( l );
          PUSH( p - 1 );
        }
    
        // If there are elements on right side of pivot,
        // then push right side to stack
        if ( p + 1 < h )
        {
          PUSH( p + 1 );
          PUSH( h );
        }
      }
    
      free( stack );
    }
    
    static void printArray( int *arr, size_t n )
    {
      while ( n-- )
        printf( "%d ", *arr++ );
      putchar( '\n' );
    }
    
    // test
    int main(void)
    {
      int arr[] = { 4, 3, 5, 2, 1, 3, 2, 3 };
    
      quickSort( arr, 0, ARRAY_ELEMENTS( arr ) - 1 );
    
      printArray( arr, ARRAY_ELEMENTS( arr ) );
    
      return EXIT_SUCCESS;
    }
    BTW: This is, more or less, the implementation used on glibc.

    PS: You can avoid the dynamic allocation of the "stack" since we need only log2(elements) entries.. If you use a stack of 64 elements it will cover any array possible, in memory. Anyway, this is also the case for a recursive quick sort, which won't exhaust the stack for the same reason.
    Last edited by flp1969; 08-02-2020 at 03:39 PM.

  13. #13
    Registered User
    Join Date
    May 2012
    Posts
    424
    That's a very clean quicksort.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  14. #14
    null pointer Structure's Avatar
    Join Date
    May 2019
    Posts
    302

    Post

    sort array in increasing order
    Code:
    #include <stdio.h>
    
    #define max 4096
    #define prc 25
    
    int arr[max] = { 
        0, 11, 16, 4,
        10, 54, 0, 0,
        76, 101, 178,
        44, 57, 167, 77, 10, 
        5, 6, 8, 1, 3, 4, 5
    };
    
    int sorted() {    
        int c = 0;
        for (int i=0; i<prc; i++) {
            if ( arr[i] > arr[i+1] ) {
                c = arr[i+1];
                arr[i+1] = arr[i];
                arr[i] = c;
                return 0;
            }
        }
        return 1;
    }
    
    int sort() {
        while ( !sorted() ) { };
        return 0;
    }
    
    int main() {
    
        for (int i =0; i<prc; i++) {
            printf("%i,",arr[i]);
        }  
    
        printf("\n"); sort();
    
        for (int i =0; i<prc; i++) {
            printf("%i,",arr[i]);
        }
    
        return 0;
    }
    "without goto we would be wtf'd"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help.. how to sort word in increasing order
    By cstyle in forum C Programming
    Replies: 6
    Last Post: 03-07-2017, 04:49 AM
  2. Flowchart - three numbers in increasing order
    By Dontknowtbh in forum C Programming
    Replies: 1
    Last Post: 09-02-2016, 12:22 PM
  3. Increasing order of integers
    By Mentallic in forum C Programming
    Replies: 3
    Last Post: 03-21-2010, 07:41 AM
  4. Sorting exam score in increasing order
    By superman12 in forum C Programming
    Replies: 5
    Last Post: 07-14-2005, 12:34 AM
  5. Replies: 2
    Last Post: 03-07-2002, 10:14 AM

Tags for this Thread