Thread: sort array of 3 keys while minimizing the total cost

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

    sort array of 3 keys while minimizing the total cost

    i ve asked the same question 6 months ago but havent really understood how to solve this yet

    suppose that we have an array of size n where n <=10 and the keys are 1,2,3

    if n = 3 then

    Code:
    A[] = {2,1,3}
    we want to find the min cost in order to sort it in an ascending order

    one way would be the following

    Code:
    2 1 3
    2 3 1
    1 3 2
    1 2 3
    with a total cost of 3

    another way would be the following

    Code:
    2 1 3
    1 2 3
    with a total cost of 1

    but if we have a bigger number of n for example n = 5 the problem gets harder

    Code:
    A[] = {3,2,2,1,3}
    etc

    i ve tried many sorting algorithms, one that suits the problem is counting sort, but that hasnt helped me at all

    can anyone please help me with hints? thanks

  2. #2
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    use bubble sort and count the sort.

  3. #3
    Registered User
    Join Date
    Feb 2010
    Posts
    72
    Quote Originally Posted by treenef View Post
    use bubble sort and count the sort.
    i dont think that would work

    im actually thinking of doing something like this

    count the number of 1,2,3 in the sequence and then i can know how the sorted array would be

    so for example we have

    Code:
    A[] = {2,1,3,2,2}
    the sorted array would be
    Code:
    K[]
    1
    2
    2
    2
    3
    now having A and the new array K[]
    Code:
    A[]    K[]
    2        1
    1        2
    3        2
    2        2
    2        3
    its obvious that we need just 2 swaps in order to sort the array

    but what if we have something that cant be put in the correct place with just a swap? for example if we have this

    Code:
    A[]  K[]
    
    2     1
    1     1
    3     2 
    2     2
    1     3
    we cant swap anything

    hence i dont think that method would work for all cases
    Last edited by nik2; 07-16-2010 at 07:23 AM.

  4. #4
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    Try quick sort and count the sorts?

  5. #5
    Registered User
    Join Date
    Feb 2010
    Posts
    72
    how would you do that? i really think there is a better way of doing this

    and i dont think this way is the qsort algorithm, because you cant know if it does a minimum amount of rearrangements in the sequence, or you can?

    in my previous reply if i find a way to solve the second problem then i think that would be the solution i will try qsort but i dont think it ll work

  6. #6
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Quote Originally Posted by nik2 View Post
    Code:
    A[]  K[]
    
    2     1
    1     1
    3     2 
    2     2
    1     3
    You've pretty much got it; it just requires two passes. First pass, check for swaps that correctly solve both elements. If you find such a swap, do it. If you don't (such as in the case above), go to the next pass. In the next pass, all you have to do is find a swap that solves one element. It's not as good as a swap that solves both elements, but it's as good as you can do from your current position.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by nik2 View Post
    one way would be the following

    Code:
    2 1 3
    2 3 1
    1 3 2
    1 2 3
    But what use is starting with swapping two numbers that were already in order? If you don't limit yourself to swaps that make progress then what's to stop you from swapping the same 1 and 3 repeatedly?

    now having A and the new array K[]

    Code:
    A[] K[]
    2 1
    1 2
    3 2
    2 2
    2 3
    its obvious that we need just 2 swaps in order to sort the array
    Yes but you can't know that in advance. You cannot look at the situation as an oracle. To work out where each item fits into the sorted ordering requires O(n log n) comparisons in the worst case.

    If you want optimal sorting for <= 10 items, simply look up optimal sorting networks. If you want one of the most efficient general purpose algorithms for sorting so few items, then look into bubble sort or insertion sort.

    If that doesn't answer everything, what is your actual question, or what are you actually trying to work out?
    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. Need a for loop to sort an array
    By lostandconfused in forum C Programming
    Replies: 5
    Last Post: 06-17-2010, 10:15 PM
  2. Replies: 8
    Last Post: 02-10-2010, 01:28 PM
  3. Functions, have errors...NEED HELP FAST
    By alkamenes in forum C++ Programming
    Replies: 6
    Last Post: 11-02-2009, 03:00 PM
  4. The Timing is incorret
    By Drew in forum C++ Programming
    Replies: 5
    Last Post: 08-28-2003, 04:57 PM
  5. Replies: 4
    Last Post: 04-22-2003, 12:52 PM