Sorting In Java

                                             Sorting an array without using sort()


Sorting an array without using sort()


package org.example.CodePractise;

public class SortarrayWithoutLibrary {
public static void main(String[] args) {

int [] arr={5, 2, 9, 1};
//int temp=arr[0];

 for(int i=0;i<arr.length;i++)
{
for(int j=i+1;j<arr.length;j++)
{
if(arr[i]>arr[j])
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}

for(int a:arr)
{
System.out.println(a+ " ");
}
}
}



How to sort a map by values in Java?


package org.example.CodePractise;

import java.util.HashMap;
import java.util.Map;

public class SortMapByValue {
public static void main(String[] args) {

Map<String, Integer> map = new HashMap<>();
map.put("Shivam", 85);
map.put("Amit", 92);
map.put("Rohan", 78);

map.entrySet().stream().sorted(Map.Entry.comparingByValue()).forEach(System.out::println);

}
}

How to sort case-insensitively?


String[] names = {"shivam", "Amit", "vikas"};

Arrays.sort(names, String.CASE_INSENSITIVE_ORDER);



How to sort by multiple fields?

Example: Sort by marks (desc), then by name (asc)
list.sort(
Comparator.comparing(Student::getMarks).reversed()
.thenComparing(Student::getName)
);


How to sort in parallel in Java 8+?

Arrays.parallelSort(arr);
Uses ForkJoinPool for large arrays.

Faster for big datasets in multi-core CPUs.


9. Why use TimSort in Java for objects?

10. Can we sort null values?

  • Yes, but need to handle:

list.sort(Comparator.nullsFirst(Comparator.naturalOrder()));

11. Common follow-up tricky questions
Q: Can you sort without modifying the original list?
A: Yes — make a copy:

List<Integer> sortedList = list.stream().sorted().toList();
Q: What is the time complexity of Collections.sort()?
A: O(n log n)

Q: Is Arrays.sort() thread-safe?
A: No, you need external synchronization.


1. What is Selection Sort?

  • Think of it like selecting the smallest (or largest) element in each pass and putting it at the correct position.

  • Works in-place (no extra array needed).

  • Time complexity → O(n²) (not good for big data).

  • Space complexity → O(1).


2. How it works (Ascending Order)

Example: [5, 2, 8, 1]

Pass 1:

  • Find min in whole array → 1

  • Swap with first element → [1, 2, 8, 5]

Pass 2:

  • Find min in remaining [2, 8, 5] → 2

  • Swap (no change) → [1, 2, 8, 5]

Pass 3:

  • Find min in [8, 5] → 5

  • Swap → [1, 2, 5, 8]

 Sorted.


package org.example.CodePractise;

public class SelectionSorting {
public static void main(String[] args) {

int[] arr = {5, 2, 8, 1, 3};

int n=arr.length;

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

for(int j=i+1;j<n;j++)
{
if(arr[j]<arr[minindex])
{
minindex=j;
}
}
int temp=arr[minindex];
arr[minindex]=arr[i];
arr[i]=temp;

}
// Print sorted array
 for (int num : arr) {
System.out.print(num + " ");
}
}
}




1. What is Bubble Sort?

  • Repeatedly compare adjacent elements and swap them if they are in the wrong order.

  • After each pass, the largest element "bubbles up" to its correct position at the end.

  • Not efficient for large data — only good for teaching or small datasets.

  • Stable sort (keeps order of equal elements).

2. How it Works (Ascending Order Example)

Array: [5, 3, 4, 1]

Pass 1:
Compare pairs → swap if needed
[3, 4, 1, 5] → largest (5) at last position.

Pass 2:
[3, 1, 4, 5] → largest (4) at second last.

Pass 3:
[1, 3, 4, 5] → sorted.




package org.example.CodePractise;

public class BubbleSort {

public static void main(String[] args) {
int[] nums = {5, 3, 4, 1, 2};

int n=nums.length;

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

if(nums[j]>nums[j+1])
{
int temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}

for(int nu:nums)
{
System.out.print(nu);
}

}
}

1. What is Insertion Sort?

  • Works like arranging cards in your hand:

    • Take the first card (already sorted).

    • Pick the next card and insert it into the correct position among the already sorted cards.

  • Good for small datasets or when data is already almost sorted.

  • Stable → equal elements keep their relative order.

  • In-place → no extra memory used.

2. How it Works (Ascending Example)

Array: [5, 3, 4, 1]

Pass 1 (i=1)

  • Current = 3

  • Compare with 5 → 3 < 5 → shift 5 to right → insert 3 before it.
    Result: [3, 5, 4, 1]

Pass 2 (i=2)

  • Current = 4

  • Compare with 5 → shift 5 → insert 4.
    Result: [3, 4, 5, 1]

Pass 3 (i=3)

  • Current = 1

  • Compare with 5, 4, 3 → shift all right → insert 1 at start.
    Result: [1, 3, 4, 5]  Sorted.



package org.example.CodePractise;

public class Insertionsort {
public static void main(String[] args) {

int[] arr = {5, 3, 4, 1, 2};
int n=arr.length;

for(int i=1;i<n;i++)
{
int current=arr[i];
int j=i-1;

while(j>=0 && arr[j]>current)
{
arr[j+1]=arr[j]; //right shift
 j--; // go left to check
 }
arr[j+1]=current; ////Insert current element
 }



// Print sorted array
 for (int num : arr) {
System.out.print(num + " ");
}
}
}


Merge Sort

1. What is Merge Sort?

  • Divide and Conquer algorithm.

  • Splits the array into two halves, sorts each half, and then merges them back in sorted order.

  • Stable → keeps order of equal elements.

  • Used when stability and guaranteed O(n log n) time is needed.

2. How It Works (Ascending Example)

Array: [5, 3, 8, 4]

Step 1 – Divide:

  • Split → [5, 3] and [8, 4]

  • Split again → [5] [3] and [8] [4]

Step 2 – Conquer (Sort):

  • Sort each small array → [3, 5] and [4, 8]

Step 3 – Merge:

  • Merge [3, 5] and [4, 8] → [3, 4, 5, 8]



package org.example.CodePractise;

import java.util.ArrayList;
import java.util.List;

public class MergeSort {

public static void mergeSort(int [] arr,int start,int end)
{
int mid = start + (end - start) / 2; // prevents overflow and is correct

 if(start>=end) return;

mergeSort(arr,start,mid);
mergeSort(arr,mid+1,end);
merge(arr,start,mid,end);

}
public static void merge(int [] arr,int start,int mid,int end)
{

List<Integer> temp=new ArrayList<>();
int left=start;
int right=mid+1;

while(left<=mid && right<=end)
{
if(arr[left]<arr[right])
{
temp.add(arr[left]);
left++;
}
else {
temp.add(arr[right]);
right++;
}
}

// if elements on the left half are still left //

 while (left <= mid) {
temp.add(arr[left]);
left++;
}

// if elements on the right half are still left //
 while (right <= end) {
temp.add(arr[right]);
right++;
}

for(int i=start;i<=end;i++)
{
arr[i]=temp.get(i-start);
}

}
public static void main(String[] args) {
int n = 7;
int arr[] = { 9, 4, 7, 6, 3, 1, 5 };
System.out.println("Before sorting array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
mergeSort(arr, 0, n - 1);
System.out.println("After sorting array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}


Quick Sorting





Comments

Post a Comment

Popular posts from this blog

Two Sum II - Input Array Is Sorted

 Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order , find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice. Your solution must use only constant extra space .   Example 1: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2]. Example 2: Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3]. Example 3: Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1,...
Read more

Comparable Vs. Comparator in Java

  In Java , Comparable and Comparator both are interfaces used to sort objects. Comparable It defines  natural ordering  within a class. It is implemented  inside  the class being sorted. It uses the compareTo() method. It allows sorting  by one one . Comparable provides a  single sorting sequence . In other words, we can sort the collection on the basis of a single element such as id, name, and price. Comparable  affects the original class , i.e., the actual class is modified. Comparable is present in  java.lang  package. We can sort the list elements of Comparable type by  Collections.sort(List)  method. Only one compareTo() method can be implemented, restricting flexibility. Comparator It defines  custom sorting logic It is implemented  in a separate class  or using lambda expressions . It uses the compare() method. It allows sorting  by multiple criteria . The Comparator provides  multiple sorting...
Read more

Increasing Triplet Subsequence

 Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.   Example 1: Input: nums = [1,2,3,4,5] Output: true Explanation: Any triplet where i < j < k is valid. Example 2: Input: nums = [5,4,3,2,1] Output: false Explanation: No triplet exists. Example 3: Input: nums = [2,1,5,0,4,6] Output: true Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6. Brute Force : Failed for some testcase class Solution {     public boolean increasingTriplet ( int [] nums ) {         int n = nums . length ;         int i = 0 ;         int j =i+ 1 ;         int k =j+ 1 ;         while (i <n && j<n && k<n)         {         if (nums...
Read more