Thread: Sort array with difference

  1. 04-10-2012 #1
    fmiboy
    fmiboy is offline
    Registered User
    Join Date
    Mar 2012
    Posts
    10

    Question Sort array with difference

    Hello everybody,

    I have a question to ask, what is the efficient way to sort array according to difference of elements?

    Let's say I have array/vector

    a = [0 2 3 6 8]; //which is sorted and start from 0.

    But I want to sort by neighbor difference

    abs(0-2) = 2 //difference between first and second elements in vector
    abs(2-3) = 1 //difference between second and third elements in vector
    abs(3-6) = 3
    abs(6-8) = 2

    Now sorted output:
    abs(2-3) = 1
    abs(0-2) = 2
    abs(6-8) = 2
    abs(3-6) = 3

    make new vector from sorted:
    a = [0 1 3 5 8] now their difference is accordance of sorted early vector.

    If there is anything is not clear, please let me know I will do my best to explain more in details.
    Any idea appreciated!
    Thanks!
  2. 04-10-2012 #2
    DRK
    DRK is offline
    Registered User
    Join Date
    Jun 2009
    Posts
    120
    In C++ you could use set container - it would sort values for you. In C you can try different sorting algorithms and check which one of them is the most efficient (fastest) in this case.
    Last edited by DRK; 04-10-2012 at 07:07 AM.
  3. 04-10-2012 #3
    claudiu
    claudiu is offline
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    I think you are on the wrong forum mate, this is C not C++.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.
  4. 04-10-2012 #4
    claudiu
    claudiu is offline
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    As for the OP, post your attempt, this is not a homework service.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.
  5. 04-10-2012 #5
    DRK
    DRK is offline
    Registered User
    Join Date
    Jun 2009
    Posts
    120
    Quote Originally Posted by claudiu View Post
    I think you are on the wrong forum mate, this is C not C++.
    My fault, I've edited my post.
  6. 04-10-2012 #6
    fmiboy
    fmiboy is offline
    Registered User
    Join Date
    Mar 2012
    Posts
    10
    Thanks for responds, DRK.

    I might try qsort though problem is in subtraction part, I need to go through all elements in order to subtract them, which made me post here to get some ideas.

    NOTE claudiu: I am not expecting any code, just ideas. and beside it is not a homework or assignment of any kind. Just came across with problem and thought would be good to ask opinions.

    Hoping to sort of find smarter way to do it!
  7. 04-10-2012 #7
    claudiu
    claudiu is offline
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Well to begin with you can easily extract the difference vector as you are reading in the data vector.

    Then you could do a merge sort on the difference vector. You just need to ensure that you also save the original indexes so that you can print your original array in the correct order (if you are not allowed to rearrange that as well).
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.
« Previous Thread | Next Thread »
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. difference between pointer and array
    By zcrself in forum C Programming
    Replies: 4
    Last Post: 04-25-2010, 09:10 AM
  2. Difference between arr and &arr where arr is 1D array
    By SasDutta in forum C Programming
    Replies: 7
    Last Post: 04-14-2010, 08:45 AM
  3. Insertion sort - sort an array of structs using a single field
    By budala in forum C Programming
    Replies: 1
    Last Post: 01-26-2010, 09:02 AM
  4. Sort values in an array without using sort functions (Urgent)
    By fedya in forum C Programming
    Replies: 4
    Last Post: 12-06-2009, 12:27 PM
  5. Difference between char* and array[]
    By kotoko in forum C Programming
    Replies: 9
    Last Post: 04-23-2008, 06:03 AM

Tags for this Thread