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.

 

Removing Duplicate Value from Array in Java

Removing Duplicate Value from Array in Java

In this post, we’ll explore how to remove duplicate values from an array in Java using a HashMap. The HashMap is a powerful tool for this task because it only allows unique keys, which makes it easy to filter out duplicates.

Input:

8

[2,4,6,1,7,2,4,8]

Output:

1 2 4 6 7 8

CODE

import java.util.*;

class HelloWorld {

    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);

        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();

        int n=sc.nextInt();

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

            int temp=sc.nextInt();

            if(!map.containsKey(temp)){

                map.put(temp,1);

            }

        }

        int arr[]=new int[map.size()];

        int j=0;

        for (Map.Entry<Integer, Integer> e : map.entrySet()) 

          arr[j++]=e.getKey();

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

            System.out.print(arr[i]);

        }

    }

} 

Explanation

1. Input:

   • The program first reads the size of the array, n.
   • It then reads the array elements.

2. Using a HashMap to Filter Duplicates:

   • A HashMap is used to store each number as a key.
   • If a number is already in the map (map.containsKey(temp)), it is ignored.
   • Otherwise, the number is added to the map with a placeholder value (e.g., 1).

3. Creating a New Array:

   • After filtering, the unique numbers (keys of the HashMap) are transferred to a new array.

4. Sorting the Unique Values:

   • The Arrays.sort() method is used to sort the array of unique values.

5. Output:

   • The sorted unique values are printed.

---

Example Input and Output

Input:

8
2 4 6 1 7 2 4 8

Process:

• Original Array: [2, 4, 6, 1, 7, 2, 4, 8]
• After removing duplicates: [2, 4, 6, 1, 7, 8]
• After sorting: [1, 2, 4, 6, 7, 8]

Output:

1 2 4 6 7 8

---

How This Works

1. HashMap Filters Duplicates:

   • The HashMap automatically ensures that only unique numbers are stored as keys.

2. Efficient Transfer:

   • The unique numbers are transferred from the HashMap to an array using a simple loop.

3. Sorting:

   • The Arrays.sort() method sorts the array in ascending order efficiently.

---

Key Points

1. Time Complexity:

   • Inserting elements into a HashMap is O(1) on average.
   • Sorting the array is O(n log n), where n is the number of unique elements.

2. Space Complexity:

   • The HashMap and the new array require extra space proportional to the number of unique elements.

3. Edge Cases:

   • Empty Array: If the input size n is 0, the program will produce no output.
   • All Elements Are the Same: The program will output a single element.
     • Input: [5, 5, 5, 5]
       Output: 5

4. Sorted Output:

   • The program sorts the unique values before printing them. If sorting is not required, you can skip the Arrays.sort() step.

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!

Find the Minimum and Maximum Value in Array

Minimum and Maximum Value in Array

In this post, we will discuss a simple Java program to find the minimum and maximum values in an array. This program uses straightforward logic to traverse the array, comparing each element to identify the smallest and largest numbers. Let's break it down step-by-step.

import java.util.*;

public class hello(){

        public static void main(String args[]){

int n=sc.nextInt();

int arr[]=new int[n];

int min=Integer.MAX_VALUE;

                int max=Integer.MIN_VALUE;

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

    arr[i]=sc.nextInt();

    if(arr[i]<min){

        min=arr[i];

    }

                    if(arr[i]>max){

                        max=arr[i];

                    }

}

System.out.print(min+" "+max);

    }

}

How This Program Works

1. Input Array Size

   
   int n = sc.nextInt();
   

   The program first reads the size of the array, n, from the user.

2. Initialize the Array:

   int arr[] = new int[n];
   

   An array of size n is created to store the integers.

3. Set Initial Min and Max:

   int min = Integer.MAX_VALUE;
   int max = Integer.MIN_VALUE;
   

   • Integer.MAX_VALUE is the largest value an int can hold (2^31 - 1). This ensures that any number in the array will be smaller.
   • Integer.MIN_VALUE is the smallest value an int can hold (-2^31). This ensures that any number in the array will be larger.

4. Iterate Through the Array: The program loops through all elements in the array using:

   
   for (int i = 0; i < n; i++) {
       arr[i] = sc.nextInt();
   }
   

   Each element is read and stored in the array. During this loop:

   • If the current element is smaller than min, the program updates min.
   • If the current element is larger than max, the program updates max.

5. Print Results: Once the loop finishes, the smallest (min) and largest (max) numbers in the array are printed:

   System.out.print(min + " " + max);
   

---

Example Input and Output

Input:

5
3 1 9 2 6

Process:

• Array elements: [3, 1, 9, 2, 6]
• min starts at Integer.MAX_VALUE and is updated to 3 → 1 (smallest so far).
• max starts at Integer.MIN_VALUE and is updated to 3 → 9 (largest so far).

Output:

1 9

---

Key Points

1. Efficiency:
   • The program only loops through the array once, making it efficient with a time complexity of O(n).
2. Edge Cases:
   • If all numbers in the array are the same, both min and max will have that value.
   • For an empty array (if n == 0), the program would fail as no inputs would be read. You can add a check for this case.

---

Improvements

To make this program more robust, you can:

1. Validate the input size n to ensure it's greater than 0.
2. Use exception handling to catch invalid inputs.