Thread: 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

Originally Posted by Adak

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

With a number of items so small, it makes sense to just study "optimal sorting networks".

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.

Originally Posted by Adak

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"