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.