How to re-sort an already sorted array in which one element is updated

Question

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

1 2 2 3 3 4 5 6 7 8 9 

Now exactly one element is updated:

 1 5 2 3 3 4 5 6 7 8 9 

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

update I do not know how to name what I wrote. But I believe that sorting is impossible 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 know which element is odd, i.e. his position is known!

Answer 1

This solution shifts each element by one until the correct position for the odd element is found. Since it was overwritten already in the first step, it is stored in the temporary variable "h", and then written to the end position. This requires a minimum of comparisons 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; } 

Answer 2

Bubblesort will use n ^ 2 times if the last element should get to the beginning. Use insertion sort.

Answer 3

Since the array is small, insertion sorting takes about ~ O (n) time for small arrays, and if you just update the value 1, then insertion sorting should best fulfill your purpose.

Answer 4

It can be done in O(n) . If you don't know the element, then look for the element in O (n), and then you just need to compare and swap for each element, and that will take O (n). So the sum is 2n, which means O (n). If you know the item that has been modified, compare and replace for each item.

Answer 5

You do not need to sort it again.

Only one item is changed. So you just need to go through the list and put the changed number in the appropriate place. This will be 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 for this input. Enjoy it.

Answer 6

• If you want to quickly replace an element, you can also use a structure in which deletion and insertion are quick, for example, a TreeSet in Java. This means that O (log (n)) is theoretically, but if you just manipulate arrays of 20 elements, this may not be worth it.
• If the set of all the different elements is finite, as in your example, where you just use numbers from 1 to 9, then O (1) has a solution. Instead of having a sorted list, you just save an array with the number of occurrences of your elements.
• If you still want to save everything in an array, then the fastest way is
  • find the position A of the element you are about to remove in half in O (log (n)).
  • find position B where your new item will be in the same way. More precisely, B is the smallest index, where new_element <a [k] for any k> B
  • if A <B, move all elements between A + 1 and B to the left, then set the new element to position B., if B> A, you do the same, but to the right. Now this step is in O (n), but there is no logic, it just moves the memory. In C, you should use memmove for this, and it is highly optimized, but I don't know the Java equivalent.

Answer 7

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

But searching for a new position with binary search is O (log (n)), i.e. 5 in this case. Somewhat faster, if you need the last bit of odd speed, use a binary search, otherwise you can stick with the look of the bubble.

Answer 8

Here is a naive implementation in simple C. Remove fprintf(stderr, ... after testing. ITEM can be anything if the comparison function is possible. Otherwise: use pointers for ITEM (and maybe add an extra argument sizeofelem, 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; }