Sorting Array

Sorting Array

Sorting is one of the most fundamental operations in programming. In this post, we’ll look at how to sort an array in ascending order using a simple nested loop approach. This method is often referred to as the Bubble Sort or Selection Sort style sorting.

import java.util.*;

class HelloWorld {

    public static void main(String[] args) {

        int n=sc.nextInt();

        int arr[]=new int[n];

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

            arr[i]=sc.nextInt();

        }

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

            for(int j=i+1;j<n;j++){

                if(arr[i]>arr[j]){

                    int temp=arr[j];

                    arr[j]=arr[i];

                    arr[i]=temp;

                }

            }

        }

        for(int i:arr){

            System.out.print(i);

        }

    }

}

ow the Code Works

1. Input:

   • The program reads the size of the array (n) and then the elements of the array.

2. Sorting Logic:

   • A nested loop is used to compare every element with the others.
   • If an element at arr[i] is greater than arr[j], the two elements are swapped to bring smaller elements to the left.

3. Output:

   • The sorted array is printed in ascending order.

---

Example Input and Output

Input:

5
4 2 5 1 3

Process:

• Original Array: [4, 2, 5, 1, 3]
• After Sorting: [1, 2, 3, 4, 5]

Output:

1 2 3 4 5

---

How the Sorting Works

The sorting algorithm iterates through the array multiple times:

• Step 1:

  • Compare each element with the next one.
  • Swap if the current element is larger than the next.

• Step 2:

  • Repeat the process for all remaining elements.

This ensures that the smallest element moves to the front first, followed by the next smallest, and so on.

---

Key Points

1. Time Complexity:

   • The nested loop makes this algorithm O(n²), where n is the size of the array.
   • This is not efficient for large datasets but is simple and useful for small arrays.

2. Space Complexity:

   • The algorithm uses no additional space, making it O(1) in terms of space complexity.

3. Edge Cases:

   • Already Sorted Array: The program will still perform comparisons unnecessarily.
   • Empty Array: If n == 0, the program will output nothing, which is correct behavior.

 

Increasing-Decreasing in Array

Increasing-Decreasing in Array 

the first half sorted in ascending order and the second half sorted in descending order.

Sorting an Array into Increasing and Decreasing Order in Java

In this post, we will learn how to divide an array into two parts:

1. The first half of the array is sorted in ascending order.
2. The second half of the array is sorted in descending order.

We’ll implement this functionality in Java using nested loops for sorting. Let’s dive into the code and the explanation.

Input:

 6

[1,2,3,4,5,6]

Output:

1 2 3 6 5 4

the arrays is divided into two parts first half in ascending order and second half in decending order

6

[7 2 0 1 4,2]

0 1 2 7 4 2

import java.util.*;

class HelloWorld {

    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);

        int n=sc.nextInt();

        int arr[]=new int[n];

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

            arr[i]=sc.nextInt();

        }

        for(int i=0;i<n/2;i++){

            for(int j=i+1;j<n;j++){

                if(arr[i]>arr[j]){

                    int temp=arr[j];

                    arr[j]=arr[i];

                    arr[i]=temp;

                }

            }

        }

        for(int i=n/2;i<n;i++){

            for(int j=i+1;j<n;j++){

                if(arr[i]<arr[j]){

                    int temp=arr[j];

                    arr[j]=arr[i];

                    arr[i]=temp;

                }

            }

        }

        for(int a:arr){

            System.out.print(a+" ");

        }

    }

}

How the Code Works

1. Input:

   • The program reads the size of the array (n) and then the elements of the array.

2. Sorting the First Half:

   • A nested loop is used to sort the first half of the array (indices 0 to n/2 - 1) in ascending order.
   • If an element at arr[i] is greater than arr[j], they are swapped to ensure smaller elements come first.

3. Sorting the Second Half:

   • A nested loop is used to sort the second half of the array (indices n/2 to n - 1) in descending order.
   • If an element at arr[i] is smaller than arr[j], they are swapped to ensure larger elements come first.

4. Output:

   • The modified array is printed, where the first half is in ascending order and the second half is in descending order.

---

Example Input and Output

Input:

6
1 2 3 4 5 6

Process:

• Array: [1, 2, 3, 4, 5, 6]
• First half sorted in ascending order: [1, 2, 3]
• Second half sorted in descending order: [6, 5, 4]

Output:

1 2 3 6 5 4

Input:

6
7 2 0 1 4 2

Process:

• Array: [7, 2, 0, 1, 4, 2]
• First half sorted in ascending order: [0, 1, 2]
• Second half sorted in descending order: [7, 4, 2]

Output:

0 1 2 7 4 2

---

Key Points

1. Sorting Logic:

   • The program uses a basic nested loop for sorting, which has a time complexity of O(n²). While this is simple, it may not be optimal for very large arrays.

2. Dynamic Half Splitting:

   • The program dynamically calculates the midpoint of the array (n/2) to divide it into two halves, regardless of the size of the array.

3. Edge Cases:

   • If the array size is odd, the first half will have one more element than the second half. This is because n/2 truncates the decimal in integer division.
   • Example: For an array of size 5, the first half will contain indices [0, 1] (two elements), and the second half will contain indices [2, 3, 4] (three elements).

---

Improvements

1. Optimize Sorting:
   • Replace the nested loop with efficient sorting algorithms like Arrays.sort() or custom logic using the Collections framework.
2. Handle Odd-Sized Arrays:
   • If needed, ensure an even split by explicitly defining the midpoint or handling the extra element in one of the halves.

---

Conclusion

This program provides a simple way to divide an array into two parts:

• The first part sorted in ascending order.
• The second part sorted in descending order.

While it uses basic sorting logic, it’s a great starting point to understand array manipulation in Java. Feel free to try it out and optimize it further!