Scribd
Upload
6 views6 pages

Sort Array Halves: Ascending & Descending

The document outlines a method for sorting an array by dividing it into two halves: the first half is sorted in ascending order and the second half in descending order. It details the algorithm's steps, time complexity of O(n log n), and space complexity of O(1), while providing a Java code implementation. The technique is useful for scenarios requiring partial ordering of data for efficient searching or visualization.

Uploaded by

surnokomol
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views6 pages

Sort Array Halves: Ascending & Descending

The document outlines a method for sorting an array by dividing it into two halves: the first half is sorted in ascending order and the second half in descending order. It details the algorithm's steps, time complexity of O(n log n), and space complexity of O(1), while providing a Java code implementation. The technique is useful for scenarios requiring partial ordering of data for efficient searching or visualization.

Uploaded by

surnokomol
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Theory: -

Sorting Half of an Array in Ascending and the Other Half in Descending Order

Problem Statement

Given an array of integers, the task is to sort the first half of the array in
ascending order and the second half in descending order.

Key Concepts

1. Array Splitting:

- The array is divided into two parts based on its midpoint.

- For an array of length ‘n’, the midpoint ‘mid’ is calculated as ‘(n + 1) / 2’.
This ensures that:

- If ‘n’ is even, the first half contains exactly ‘n/2’ elements.

- If ‘n’ is odd, the first half contains ‘(n + 1)/2’ elements (including the
middle element).

2. Sorting:

- First Half (Ascending Order): The elements from index ‘0’ to ‘mid – 1’ are
sorted in ascending order using a standard sorting algorithm (e.g.,
‘[Link]’ in Java).

- Second Half (Descending Order):

- The elements from index ‘mid’ to ‘n – 1’ are first sorted in ascending


order.

- The sorted segment is then reversed to achieve descending order.


Reversing is done by swapping elements symmetrically around the center of
the segment.

3. Time Complexity:

- Sorting the first half: \(O(\frac{n}{2} \log \frac{n}{2})\).


- Sorting and reversing the second half: \(O(\frac{n}{2} \log \frac{n}{2} +
\frac{n}{2})\).

- Overall time complexity: \(O(n \log n)\), dominated by the sorting steps.

4. Space Complexity:

- The algorithm operates in-place, using only a constant amount of extra


space for swapping elements. Thus, the space complexity is \(O(1)\).

Algorithm Steps

1. Input: Read the array size and elements from the user.

2. Midpoint Calculation: Compute ‘mid = (n + 1) / 2’.

3. Sort First Half: Sort the subarray ‘arr[0..mid-1]’ in ascending order.

4. Sort and Reverse Second Half:

- Sort the subarray ‘arr[mid..n-1]’ in ascending order.

- Reverse the sorted subarray to get descending order.

5. Output: Print the modified array.

Example

Input Array: [5, 2, 4, 7, 9, 3, 1, 6, 8] (length n = 9)

- Midpoint: mid = (9 + 1) / 2 = 5

- First Half (Indices 0 to 4): [5, 2, 4, 7, 9] → Sorted to [2, 4, 5, 7, 9]

- Second Half (Indices 5 to 8): [3, 1, 6, 8] → Sorted to [1, 3, 6, 8] → Reversed


to [8, 6, 3, 1]

- Final Array: [2, 4, 5, 7, 9, 8, 6, 3, 1]

Applications :-

- This technique is useful in scenarios where data needs to be partially


ordered for efficient searching or visualization.
- It can be adapted for problems requiring hybrid sorting strategies, such as
organizing data with different priority orders.

Algorithm: -

BEGIN

PRINT “Enter the size of the array: ”

READ size

DECLARE array[size]

PRINT “Enter the elements of the array:”

FOR I = 0 TO size – 1

READ array[i]

END FOR

Mid = (size + 1) / 2

SORT array[0..mid-1] in ascending order

SORT array[mid..size-1] in ascending order

Start = mid

End = size – 1

WHILE start < end

SWAP array[start] and array[end]

Start = start + 1

End = end – 1
END WHILE

PRINT “Sorted array with first half in ascending and second half in
descending order:”

PRINT array

END

Code :-

import [Link];

import [Link];

class HalfSort {

public static void main(String[] args) {

Scanner scanner = new Scanner([Link]);

[Link]("Enter the size of the array: ");

int size = [Link]();

int[] array = new int[size];

[Link]("Enter the elements of the array:");

for (int i = 0; i < size; i++) {

array[i] = [Link]();

sortHalf(array);
[Link]("Sorted array with first half in ascending and second
half in descending order:");

[Link]([Link](array));

[Link]();

public static void sortHalf(int[] arr) {

if (arr == null || [Link] <= 1) {

return;

int n = [Link];

int mid = (n + 1) / 2;

[Link](arr, 0, mid);

[Link](arr, mid, n);

int start = mid;

int end = n - 1;

while (start < end) {

int temp = arr[start];

arr[start] = arr[end];

arr[end] = temp;

start++;

end--;

}
}

Conclusion :-

By splitting the array into two halves and applying different sorting strategies
to each, we achieve a hybrid order that meets specific requirements
efficiently. The algorithm leverages standard sorting and reversing
operations, ensuring clarity and optimal performance.

Common questions

Powered by AI

'Arrays.sort' is suitable for this problem because it provides a time-efficient way to sort portions of an array. It handles the sorting of both the first and second halves in ascending order effectively, leveraging built-in sorting optimizations. Using 'Arrays.sort' helps maintain the overall time complexity of O(n log n) because it is optimized for speed and generally runs in this time complexity for primitive data types . This suitability makes it an appropriate choice for in-place sorting tasks.

The algorithm ensures that the second half of the array achieves descending order by first sorting it in ascending order and then using a reversing step. During the reversing step, it swaps elements starting from the midpoint towards the end, moving elements from the end toward the midpoint concurrently . This element swapping effectively flips the ascending order into descending, thereby ensuring the second half ends up arranged in descending order as intended.

The steps involved are: 1) Calculate the midpoint using 'mid = (n + 1) / 2'. 2) Sort the first half of the array, from index 0 to 'mid-1', in ascending order. 3) Sort the second half of the array, from index 'mid' to 'n-1', in ascending order. 4) Reverse the sorted second half to arrange it in descending order by swapping elements symmetrically from start to end . These steps ensure a hybrid order efficiently.

Reading both the size and elements of the array from user input allows the algorithm to be flexible and adaptable to various user needs, providing the ability to handle dynamic data sizes and compositions . This flexibility is beneficial in practice, wherein data might not be known beforehand, and users need to accommodate varying amounts of input during each run of the program. Moreover, it facilitates testing different data sets without changing code structure.

The space complexity remains constant, i.e., O(1), because the algorithm operates in-place and uses only a constant amount of additional space for swapping elements. The sorting of both halves of the array and the reversing of the second half are conducted using the original array space without allocating any additional data structures . This means that no extra space relative to the input size is required beyond a few variables for indices and temporary storage during swapping.

The midpoint of an array is calculated as '(n + 1) / 2' to divide it into two halves. This calculation ensures that if 'n' (the length of the array) is even, the first half contains exactly 'n/2' elements. If 'n' is odd, the first half contains '(n + 1)/2' elements, including the middle element . This method is used to handle both even and odd-length arrays consistently, ensuring that the first half always contains the middle element when applicable.

The significance of the hybrid order achieved by sorting the first half of the array in ascending order and the second half in descending order lies in its potential applications in data arrangement where such specific ordering is beneficial. For example, it can be used in scenarios requiring efficient retrieval where recent data or high-priority items need to be highlighted and accessible quickly. The hybrid order can aid in visualizations where contrasting data trends need to be displayed within one dataset . Such sorting provides a flexible and efficient structure for mixed-order requirements.

Swapping elements symmetrically around the center reorders an ascending sequence into a descending sequence. By taking the first element after the midpoint and swapping it with the last element, then proceeding inward to the center, each pair reversal effectively places the largest available elements on the descending end while the smallest ones move towards the midpoint . This method systematically reverses the order of the elements, achieving the desired descending order efficiently.

The overall time complexity is O(n log n) because it is dominated by the sorting operations. Specifically, sorting the first half takes O(n/2 log n/2) and sorting the second half also involves sorting in ascending order before reversing, which takes additional O(n/2). Combined, both sorting operations yield a time complexity of O(n log n). The reversing operation is linear O(n/2) and does not affect the overall complexity significantly.

This sorting technique could be useful in scenarios where data needs to be partially ordered for efficient searching or visualization. It can be adapted for problems requiring hybrid sorting strategies, such as organizing data with different priority orders . For instance, it can be useful in displaying priority tasks or in user interfaces where recent items need to appear at the top while others are sorted alphabetically.

You might also like