sort array in accending order while minimizing the cost

This is a discussion on sort array in accending order while minimizing the cost within the C Programming forums, part of the General Programming Boards category; *ascending hi if we have for example {3,2,1} and we want to make it {1,2,3} how to find the minimum ...

  1. #1
    Registered User
    Join Date
    Feb 2010
    Posts
    72

    sort array in accending order while minimizing the cost

    *ascending

    hi

    if we have for example {3,2,1}

    and we want to make it {1,2,3}

    how to find the minimum cost that is required in order to achieve this?

    when i say cost i mean the number of rearrangements between two elements of the array

    we could do this

    Code:
    {3,2,1}
    {1,2,3}
    which has cost = 1

    or this

    Code:
    {3,2,1}
    {2,3,1}
    {2,1,3}
    {1,2,3}
    which has cost = 3

    this is simple example what would happen in an array with N elements? how to find then the minimum cost?

    thanks
    Last edited by nik2; 02-09-2010 at 02:48 PM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    In sorting you have 4 parameters to consider (at least):

    1) Overall run time

    2) Number of swaps (and whether you want to swap data or just pointers/indexes).

    3) Number of comparisons made.

    4) Do you need a "stable" sort, where the names that are *equal* and now rank higher in the list, remain in that higher position (relative to lower equals), after the sort is done?

    #1 is influenced strongly by #2 and #3, but algorithm efficiency and locality of reference trumps #2 and #3 - generally.

    #2 bites you when the data is a large struc or stringt and you need to actually move them, instead of just an index or pointer to that struct or string.

    #3 If you're on a network, and every comparison has to be called up with a substantial delay factor, then comparisons are a real factor to keep in mind. Otherwise, who cares?

    #4 Some sorts can be done while the data is still being accessed, if it is a "stable' sort (like Insertion sort). Other sorting algorithms may be much faster, but need to be done when the dbase being sorted, is off-line.

    Selection sort and Insertion sort are well known for their low number of comparisons or swaps. I'll leave it to you to figure out which does the fewest of what.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    IMO what you really want is expressed in terms of big O notation. Typical sorting algorithms have a "cost" of O(nlogn) while ideal ones have O(n) where n is the number of items to be sorted. Google big O notation.

  4. #4
    Registered User
    Join Date
    Feb 2010
    Posts
    72
    Quote Originally Posted by Adak View Post
    In sorting you have 4 parameters to consider (at least):

    1) Overall run time

    2) Number of swaps (and whether you want to swap data or just pointers/indexes).

    3) Number of comparisons made.

    4) Do you need a "stable" sort, where the names that are *equal* and now rank higher in the list, remain in that higher position (relative to lower equals), after the sort is done?

    #1 is influenced strongly by #2 and #3, but algorithm efficiency and locality of reference trumps #2 and #3 - generally.

    #2 bites you when the data is a large struc or stringt and you need to actually move them, instead of just an index or pointer to that struct or string.

    #3 If you're on a network, and every comparison has to be called up with a substantial delay factor, then comparisons are a real factor to keep in mind. Otherwise, who cares?

    #4 Some sorts can be done while the data is still being accessed, if it is a "stable' sort (like Insertion sort). Other sorting algorithms may be much faster, but need to be done when the dbase being sorted, is off-line.

    Selection sort and Insertion sort are well known for their low number of comparisons or swaps. I'll leave it to you to figure out which does the fewest of what.
    hi

    i just want the number of rearrangements

    i just finished reading about these two algorithms they seem to be able to do what i want

    i dont think that insertion would work because for example if we have this array

    Code:
    2 1 3 2 2
    the insertion would do

    Code:
    2 1 3 2 2
    1 2 3 2 2 
    1 2 2 3 2
    1 2 2 2 3
    here cost will be = 3

    but the actual cost is less than 3 it's 2 because:

    Code:
    2 1 3 2 2
    1 2 3 2 2
    1 2 2 2 3
    seems like insertion wouldn't work, then we have selection sort which seems pretty interesting

    if im correct it can make 2 kind of rearrangements, it can put the min in the beginning or the max in the end

    putting the min in the beginning we have:
    Code:
    2 1 3 2 2 
    1 2 3 2 2
    1 2 2 3 2
    1 2 2 2 3
    where cost = 3 -> wrong

    putting the max in the end we have:

    Code:
    2 1 3 2 2
    2 1 2 2 3
    1 2 2 2 3
    where cost = 2 -> right

    so i guess if I take 2 different selection sorts and then count the arrangements and take the min of the arrangements that would be the min of arrangements needed in order to sort the array in ascending order?

    correct me if im wrong

    thanks
    Last edited by nik2; 02-09-2010 at 03:45 PM.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    With a number of items so small, it makes sense to just study "optimal sorting networks".
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    The number of swaps will depend on the data itself. The number of comparisons might, as well, depending on what kind of algorithm you use. A sorting network will always make the same number of comparisons, but the number of swaps ALWAYS depends on the data. This is pretty obvious, because an already-sorted array requires no swaps (at least if the algorithm isn't doing something stupid), while ANY other ordering will require at least one swap.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    Registered User
    Join Date
    Feb 2010
    Posts
    72
    what if the array of n elements would only have 3 different numbers?

    for example a=3, b = 5 and c = 6?

    would this simplify the whole problem?

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by nik2 View Post
    what if the array of n elements would only have 3 different numbers?

    for example a=3, b = 5 and c = 6?

    would this simplify the whole problem?
    An array of three elements with 3, 5, and 6 as values, is already sorted. One insertion sort scan over the values will confirm it, and no swaps are needed, of course.

    A sorting program won't know in advance if the data is already sorted, and must be prepared to handle any arrangement of data. At the very least it must compare every value, to every other value, at least once.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by Adak View Post
    At the very least it must compare every value, to every other value, at least once.
    Slight mistake there. The above would mean that there were no sorting algorithm better than O(n*n).
    Take a look at binary insertion sort for a clear example of where you went wrong with your logic. (yes that's still O(n*n) due to moving items)

    HeapSprt is an example of an algorithm that moves items around when the array was already sorted. It's not stupid though.

    If data is known to have many duplicates AND the ordering of those duplicates does not matter, then yes an algorithm that takes advantage of this can outperform a general sorting algorithm. Case in point: "Several Unique Sort"
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 12-06-2009, 11:27 AM
  2. How to sort an array of pointers to structure
    By broli86 in forum C Programming
    Replies: 3
    Last Post: 06-30-2008, 02:52 PM
  3. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  4. Sorting an array of structures with sort()
    By rmullen3 in forum C++ Programming
    Replies: 3
    Last Post: 01-03-2003, 02:02 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21