What is the tradeoff between using an unordered array versus an ordered array

The major advantage of an ordered array is that the search times are much faster with O (log n) than an unordered array, which is O (n) for larger values of n. The disadvantage of an ordered array is that the insertion takes longer (i.e. O (n) ) because all the data with higher values need to be moved to make room. The insertion for an unordered array takes constant time of O(1). This means, it does not depend on the number of elements. The following code snippet demonstrates adding an element to both ordered and unordered array.

Inserting an element into an unsorted array

package bigo;

import java.util.Arrays;

public class InsertingElementsToArray {

public static void insertUnsortedArray(String toInsert) {

String[ ] unsortedArray = { “A”, “D”, “C” };

String[ ] newUnsortedArray = new String[unsortedArray.length + 1];

System.arraycopy(unsortedArray, 0, newUnsortedArray, 0, 3);

newUnsortedArray[newUnsortedArray.length – 1] = toInsert;

System.out.println(Arrays.toString(newUnsortedArray));

}

public static void main(String[ ] args) {

insertUnsortedArray(“B”);

}

}

Inserting an element into a sorted array

package bigo;

import java.util.Arrays;

 

public class InsertingElementsToArray {

 

public static void insertSortedArray(String toInsert) {

 

String[ ] sortedArray = { “A”, “C”, “D” };

int index = Arrays.binarySearch(sortedArray, toInsert);

 

if (index < 0) {                                   // not found.

 

// array indices are zero based. -2 index means insertion point of

// -(-2)-1 = 1,  so insertIndex = 1

int insertIndex = -index – 1;

 

String[ ] newSortedArray = new String[sortedArray.length + 1];

System.arraycopy(sortedArray, 0, newSortedArray, 0,  insertIndex);

System.arraycopy(sortedArray, insertIndex,

newSortedArray, insertIndex + 1,  sortedArray.length – insertIndex);

newSortedArray[insertIndex] = toInsert;

System.out.println(Arrays.toString(newSortedArray));

}

}

 

public static void main(String[ ] args) {

insertSortedArray(“B”);

}

}

So the decision depends on the usage pattern. Ask yourself the following questions. Do I have more inserts/deletes or search? What is the maximum number of elements likely to be stored in this array? How often do I need the sorted data? And finally what does my performance benchmark show