CODEWITHSUNDEEP
javaalgorithmsorting
Oleg Vazhnev
Oleg Vazhnev

Reputation: 24067

How to re-sort already sorted array where one element updates

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!

Upvotes: 5

Views: 4761

Answers (8)

alzaimar
alzaimar

Reputation: 4622

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;
 }

Upvotes: 1

wildplasser
wildplasser

Reputation: 44250

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;
}

Upvotes: 0

Albin Sunnanbo
Albin Sunnanbo

Reputation: 47048

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.

Upvotes: 0

rai.skumar
rai.skumar

Reputation: 10677

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.

Upvotes: 0

Scout
Scout

Reputation: 575

  • 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.

Upvotes: 0

Cereal_Killer
Cereal_Killer

Reputation: 324

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.

Upvotes: 0

Rahul
Rahul

Reputation: 16335

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.

Upvotes: 0

Imre Kerr
Imre Kerr

Reputation: 2428

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

Upvotes: 0

Related Questions