5

I have array with constant size (size = 20 in real life), duplicates are allowed For example:

1 2 2 3 3 4 5 6 7 8 9

Now exactly one element updates:

1 5 2 3 3 4 5 6 7 8 9

I need to resort this array. Should I just use bubblesort?

update I don't know how to call what I wrote. But i suppose it is not possible to sort faster. comments are welcome!

    // array is already almost sorted and INCREASING, element at pos need to be inserted to the right place
    private void SortQuotes(List<Quote> quoteList, int pos)
    {
        var quoteToMove = quoteList[pos];
        if (pos == 0 || quoteList[pos - 1].Price < quoteToMove.Price)
        {
            MoveElementsDown(quoteList, pos);
        } else if (pos == quoteList.Count - 1 || quoteList[pos + 1].Price > quoteToMove.Price)
        {
            MoveElementsUp(quoteList, pos);
        }
    }

    private void MoveElementsDown(List<Quote> quoteList, int pos)
    {
        var quoteToInsert = quoteList[pos];
        var price = quoteToInsert.Price;
        for (int i = pos - 1; i >= 0; i--)
        {
            var nextQuote = quoteList[i];
            if (nextQuote.Price > price)
            {
                quoteList[i + 1] = quoteList[i];
                if (i == 0)   // last element
                {
                    quoteList[i] = quoteToInsert;
                }
            }
            else
            {
                quoteList[i + 1] = quoteToInsert;
                break;
            }
        }
    }

    private void MoveElementsUp(List<Quote> quoteList, int pos)
    {
        var quoteToInsert = quoteList[pos];
        var price = quoteToInsert.Price;
        for (int i = pos + 1; i < quoteList.Count; i++)
        {
            var nextQuote = quoteList[i];
            if (nextQuote.Price < price)
            {
                quoteList[i - 1] = quoteList[i];
                if (i == quoteList.Count - 1)   // last element
                {
                    quoteList[i] = quoteToInsert;
                }
            }
            else
            {
                quoteList[i - 1] = quoteToInsert;
                break;
            }
        }
    }

updated i do know which element is odd, i.e. it's position is known!

Improve this question
1
  • In your case doing Bubble Sort is not so bad, but a customized Bubble Sort which just iterates the list once. (And not N times), that will cost O(n). Commented Dec 8, 2012 at 13:48

8 Answers 8

Reset to default
1

This solution shifts each element by one until the right position for the odd element is found. As it has been overwritten already in the first step, it is saved in a temporary variable 'h' and then written to the final position. It requires the minimum of comparisions and shift operations:

 static void MoveOddElementToRightPosition(int[] a, int oddPosition)
 {
   int h = a[oddPosition];
   int i;
   if (h > a[oddPosition + 1])
     for (i = oddPosition; i < a.Count()-1 && a[i+1] <= h; i++)
        a[i] = a[i+1];
   else
     for (i = oddPosition; i > 0 && a[i-1] >= h; i--)
        a[i] = a[i - 1];
   a[i] = h;
 }
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

it's quite the same with what I wrote in description. However I assume this is right answer
Well, this only moves up. What if A[OldPos] happens to be lower than a[OldPos-1] ?
Ooops, was too late when I wrote this I guess. I'll add a condition
0

Bubblesort will use n^2 time if the last element needs to get to the front. Use insertion sort.

Improve this answer

3 Comments

Nope 1 iteration bubblesort will take O(n)
And, if the misplaced element needs to get towards the front of the list, will only shift that element by one place.
i forgot to say that i know which element is odd!
0

As the array is small, insertion sort takes roughly ~O(n) time for small arrays and if you are just updating 1 value, insertion sort should fulfil your purpose in the best possible way.

Improve this answer

5 Comments

Insertion sort does't take O(n)
Please refer : stackoverflow.com/questions/13229229/…
It talks about already sorted list. But this is not sorted, there is one odd element.
This list is nearly sorted. You can check it yourself using the animation as well in the below mentioned link. Choose your data set and click on refresh button on the left. linear performance for small array and nearly sorted array sorting-algorithms.com/insertion-sort
Also, if you check in jdk implementation of Arrays.sort(). you can check for INSERTION_SORT_THRESHOLD, if size < threshold use insertion else merge sort. currently the threshold_size =7
0

It can be done in O(n). If you don't know the element then search for the element in O(n) and then You just need to compare and swap for each element and that would take O(n). So total 2n which means O(n).If you know the element which has been modified then compare and swap for each element.

Improve this answer

Comments

0
  • If you're interested in replacing an element quickly, then you can also use a structure where deletion and insertion is fast, like for example a TreeSet in Java. That means O(log(n)) theoretically, but if you just manipulate arrays of 20 elements it may not be worth it
  • If the set of all different elements is finite, like in your example where you just use numbers for 1 to 9, then there is a solution in O(1). Instead of having a sorted list you just keep an array with the number of occurrences of your elements.
  • If you still want to keep everything in an array, then the fastest way is this
    1. find the position A of of the element you're going to remove by bisection in O(log(n)).
    2. find the position B of where your new element is going to end up in the same way. More precisely B is the smallest index where new_element < a[k] for every k > B
    3. if A < B, move all elements between A + 1 and B to their left, then set the new element to position B. if B > A, you do the same thing but to the right. Now this step is in O(n), but there's no logic, it's just moving memory around. In C you'd use memmove for this and it's heavily optimized, but I don't know any Java equivalent.
Improve this answer

2 Comments

I assume i do not need binary search here. I do need to move pack of outdated elements anyway. So pure bublesort may be used and it will be faster that binary search.
We're talking about algorithms and then complexity matters. Usually iterating through an array, comparing and shifting each element is faster then looking for the right place and then doing a mem move.
0

You don't need to sort it again.

Only one element changes. So you just need to go through the list and put the changed number to appropriate place. This will be of O(n) complexity.

int a[] = {1, 5, 2, 3, 3, 4, 5, 6, 7, 8, 9};
int count = 0;

//find the odd element
for(int jj=1; jj< a.length; jj++){
    if(a[jj] < a[count])
        break;
    else count++;
}
System.out.println(" Odd position "  + count);

//put odd element to proper position
for(int k= count+1; k<a.length; k++){
    if(a[count] > a[k]){
        int t = a[count];
        a[count] = a[k];
        a[k] = t;
        count++;
    }
}

Above is the working code tested for given input. Enjoy.

Improve this answer

3 Comments

thanks, in your code on each iteration you write element which will be rewritten on the next iteration. it's better to write "odd" element only at final step (as in my code above in description).
You use too many assignments / swaps in the second loop. Please see my improvement below
Agree, its not very optimized. Just wanted to have a working code :)
0

Bubblesort is quite OK in this case with 20 compares max.

But finding the new position with binary search is O(log(n)), that is 5 compares in this case.
Somewhat faster, if you need the last bit odd speed use the binary search otherwise you can stick with bubble sort.

Improve this answer

1 Comment

the point is that when bublesorting i update array. but after finding position i have to spent O(n) operations to shift elements, so bubblesort is better
0

Here is a naive implementation in plain C. Remove the fprintf(stderr, ... after testing. The ITEM can be anything, as long as a comparison function is possible. Otherwise: use pointers to ITEM, (and maybe add an extra sizeofelem argument, ala qsort)

#include <stdio.h>
#include <string.h>

typedef int ITEM;

int item_cmp(ITEM one, ITEM two);
unsigned one_bubble( ITEM *arr, unsigned cnt, unsigned hot , int (*cmp)(ITEM,ITEM) );

int item_cmp(ITEM one, ITEM two)
{
fprintf(stderr,"Cmp= %u to %u: %d\n", one, two, one-two);
if (one > two) return 1;
else if (one < two) return -1;
else return 0;
}

unsigned one_bubble( ITEM *arr, unsigned cnt, unsigned hot , int (*cmp)(ITEM,ITEM) )
{
unsigned goal = cnt;
int diff;
ITEM temp;

        /* hot element should move to the left */
if (hot > 0 && (diff=cmp( arr[hot-1], arr[hot])) > 0) {
        /* Find place to insert (this could be a binary search) */
        for (goal= hot; goal-- > 0; ) {
                diff=cmp( arr[goal], arr[hot]);
                if (diff <= 0) break;
                }
        goal++;
        fprintf(stderr,"Move %u LEFT to %u\n", hot, goal);
        if (goal==hot) return hot;
        temp = arr[hot];
                /* shift right */
        fprintf(stderr,"memmove(%u,%u,%u)\n", goal+1, goal, (hot-goal) );
        memmove(arr+goal+1, arr+goal, (hot-goal) *sizeof temp);
        arr[goal] = temp;
        return goal; /* new position */
        }
        /* hot element should move to the right */
else if (hot < cnt-1 && (diff=cmp( arr[hot], arr[hot+1])) > 0) {
        /* Find place to insert (this could be a binary search) */
        for (goal= hot+1; goal < cnt; goal++ ) {
                diff=cmp( arr[hot], arr[goal]);
                if (diff <= 0) break;
                }
        goal--;
        fprintf(stderr,"Move %u RIGHT to %u\n", hot, goal);
        if (goal==hot) return hot;
        temp = arr[hot];
                /* shift left */
        fprintf(stderr,"memmove(%u,%u,%u)\n", hot, hot+1, (goal-hot) );
        memmove(arr+hot, arr+hot+1, (goal-hot) *sizeof temp);
        arr[goal] = temp;
        return goal; /* new position */
        }
fprintf(stderr,"Diff=%d Move %u Not to %u\n", diff, hot, goal);
return hot;
}

ITEM array[10] = { 1,10,2,3,4,5,6,7,8,9,};
#define HOT_POS 1
int main(void)
{
unsigned idx;

idx = one_bubble(array, 10, HOT_POS, item_cmp);

printf("%u-> %u\n", HOT_POS, idx );

for (idx = 0; idx < 10; idx++) {
        printf("%u: %u\n", idx, array[idx] );
        }

return 0;
}
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.