What Is Ordered Array in Data Structure?

An ordered array is a data structure that stores a collection of elements in a specific order. It is also known as a sorted array because the elements are arranged in ascending or descending order based on their values. In an ordered array, each element has a unique index that represents its position within the array.

Creating an Ordered Array

To create an ordered array, you first need to define its size and data type. For example, if you want to store integers in the array, you would declare an integer array with a specific size:

  
    int maxSize = 10; // maximum size of the array
    int[] orderedArray = new int[maxSize]; // declaration and initialization
  

Once you have created the array, you can start inserting elements into it. The insertion process should maintain the order of the elements. For example, if we want to insert the number 5 into the ordered array [1, 3, 4, 7], we need to find its correct position:

  
    // Find the correct position for insertion
    int elementToInsert = 5;
    int insertIndex = -1;
    for(int i = 0; i < orderedArray.length; i++) {
        // Check if current element is greater than elementToInsert
        // If true, set insertIndex to current index and break out of the loop
        if(orderedArray[i] > elementToInsert) {
            insertIndex = i;
            break;
        }
    }
  

After finding the correct position, we need to shift the elements to make room for the new element:

  
    // Shift elements to the right from insertIndex onwards
    for(int i = orderedArray.length - 1; i > insertIndex; i--) {
        orderedArray[i] = orderedArray[i - 1];
    }

    // Insert elementToInsert at the correct position
    orderedArray[insertIndex] = elementToInsert;
  

Searching in an Ordered Array

Searching for an element in an ordered array is more efficient compared to an unordered array because of its sorted nature. One common search algorithm used is called binary search, which follows these steps:

• Step 1: Set two pointers, ‘start’ and ‘end’, initially pointing to the first and last elements of the array, respectively.
• Step 2: Calculate the middle index between ‘start’ and ‘end’:

  int middleIndex = (start + end) / 2;

• Step 3: Compare the middle element with the Target element you are searching for.
• If they are equal, the element is found at the middleIndex.
• If the middle element is greater than the Target element, set ‘end’ to middleIndex – 1 and repeat from Step 2.
• If the middle element is less than the Target element, set ‘start’ to middleIndex + 1 and repeat from Step 2.
• Step 4: Repeat Steps 2-3 until either the Target element is found or ‘start’ becomes greater than ‘end’. If ‘start’ becomes greater than ‘end’, it means the Target element does not exist in the array.

Example:

  
    int[] orderedArray = {1, 3, 4, 7, 10};
    int TargetElement = 4;

    // Binary search algorithm
    int start = 0;
    int end = orderedArray.length - 1;
    
    while(start <= end) {
        int middleIndex = (start + end) / 2;
        
        // Check if TargetElement is found at middleIndex
        if(orderedArray[middleIndex] == TargetElement) {
            System.out.println("Element found at index " + middleIndex);
            break;
        }
        
        // Adjust start and end based on comparison with middle element
        // If true, update start or end accordingly and repeat loop
        if(orderedArray[middleIndex] > TargetElement) {
            end = middleIndex - 1;
        } else {
            start = middleIndex + 1;
        }
    }

    // Output: Element found at index 2
  

In this example, the Target element 4 is found at index 2 using the binary search algorithm.

Advantages of Ordered Arrays

• Ease of searching: Searching in an ordered array can be done efficiently using algorithms like binary search.
• Maintains order: The elements in an ordered array are always sorted, making it easier to perform operations like finding the smallest or largest element.

Disadvantages of Ordered Arrays

• Inefficient insertion and deletion: Inserting or deleting elements in an ordered array requires shifting elements, which can be time-consuming for large arrays.
• Static size: The size of an ordered array is fixed during its creation and cannot be easily changed. If the array becomes full, you may need to create a new larger array and copy all the elements into it.

An ordered array is a useful data structure for scenarios where searching for elements is a common operation and maintaining their order is important. However, if frequent insertions or deletions are required, other data structures like linked lists or binary search trees may be more suitable.

Now that you understand what an ordered array is and how it works, you can apply this knowledge to efficiently store and retrieve elements in your programs.