Question: What is Sorting in Java ?
Ans: Sorting in Java refers to the process of arranging elements in a specific order, often in ascending (smallest to largest) or descending (largest to smallest) order. Java provides various ways to sort data structures like arrays, collections, and lists.
Question: Why use Sorting ?
Ans:
Sorting algorithms are used in computer science and programming for a variety of reasons:
1. **Data Retrieval and Searching**: Sorted data is much easier and faster to search. Algorithms like binary search can be used to find elements in a sorted list efficiently, reducing the time complexity from O(n) to O(log n).
2. **Data Presentation**: Sorted data is often presented to users in a more readable and meaningful way. For example, a sorted list of names or numbers is more user-friendly than an unsorted one.
3. **Data Analysis**: In data analysis and statistics, sorting can help identify trends and patterns more easily. It can simplify tasks like finding the median or quartiles of a dataset.
4. **Data Manipulation**: Many algorithms and operations, such as merging two sorted lists or finding duplicates in a list, are more efficient when data is sorted.
5. **Database Queries**: Databases often use sorting to optimize queries. An indexed column in a database is typically sorted to speed up searching.
6. **Algorithm Building Blocks**: Sorting is a fundamental building block for other algorithms. For example, many divide-and-conquer algorithms, like merge sort and quicksort, rely on sorting as a substep.
7. **Optimization**: Some problems are easier to solve when data is sorted. For example, the traveling salesman problem can be optimized more efficiently when cities are sorted by distance.
8. **Presentation and User Experience**: In software applications, sorted data is often presented to users for a better user experience. For example, sorted lists in user interfaces make it easier for users to find what they are looking for.
9. **Data Storage**: Sorted data can be stored more efficiently. Certain data structures, like binary search trees and B-trees, maintain data in a sorted order to enable efficient insertion and retrieval operations.
Different sorting algorithms have different time and space complexities, which make them suitable for different scenarios. The choice of which sorting algorithm to use depends on factors like the size of the data, whether it's partially sorted or not, and the available memory. Common sorting algorithms include quicksort, mergesort, heapsort, insertion sort, and others, each with its own advantages and disadvantages. The selection of the appropriate sorting algorithm is an important decision in software development to ensure efficient and effective data processing.
PFB Sorting Algorithm Types - - - - - - -
There are numerous sorting algorithms available, each with its own set of characteristics and trade-offs. Below are some of the most well-known sorting algorithms:
Question: What is bubble sort and about bubble sort ?
Bubble Sort: Compares adjacent elements and swaps them if they are in the wrong order. It repeatedly passes through the list until no swaps are needed.
In bubble sort algorithm, array is traversed from first element to last element. Here, current element is compared with the next element. If current element is greater than the next element, it is swapped.
Concept: bubble sort me bubble ke concept ko dhyan me rakh ke develope kiya gya hai , in this sorting algorithm sabse bhari element ko last me rkha hai , phir usse kam bhari element ko usse phle to kuch is tarh se hame accending order ka element mil jata hai aur use agr reverse kar den to wo decending order me ban jata hai.
Topic: We are sorting this array in accending order using bubble sort
Array: /*175,45,75,90,802 this is my array */
>> ye ek array given hai
>Explain teration> isme ham phle wale element ko udhayenge and will check that agar this element is [170 > 45] then 45 ko phle rkho aur 170 ko uske bad kardo, isi tarh ham next se check karenge [170 > 75] agar 170 bdha hai 75 se to 75 ko phle rkh do aur 175 ko aage kar do, ab 175 aur 90 ko compare karo to [175 > 90] then 90 ko phle rkho aur 175 ko aage kardo , next [175 > 802] nhi then 175 ko phle rkho aur 802 ko last me is trh sabse bhari element bubble ki tarh last me ho gya .
Shuruaati Array: [175, 45, 75, 90, 802]
Pehla Pass:
Comparisons:
1. Pehle do elements ko compare karo: 175 aur 45. Kyunki 175 45 se bada hai, unhein swap karo.
2. Array ab yeh hogi: [45, 175, 75, 90, 802]
3. Ab 175 aur 75 ko compare karo. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
4. 175 aur 90 ko compare karo. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
5. 175 aur 802 ko compare karo. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
Pehle pass ke baad, sabse bada element 802 ko array ke ant tak pahunchaya jata hai.
Dusra Pass:
Comparisons:
1. Pehle do elements ko compare karo: 45 aur 175. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
2. 175 aur 75 ko compare karo. Kyunki 175 75 se bada hai, unhein swap karo.
3. Array ab yeh hogi: [45, 75, 175, 90, 802]
4. Ab 175 aur 90 ko compare karo. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
Dusre pass ke baad, doosra sabse bada element 175 ko array ke doosre se aakhri position par pahunchaya jata hai.
Teesra Pass:
Comparisons:
1. Pehle do elements ko compare karo: 45 aur 75. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
2. 75 aur 175 ko compare karo. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
3. 175 aur 90 ko compare karo. Kyunki 175 90 se bada hai, unhein swap karo.
4. Array ab yeh hogi: [45, 75, 90, 175, 802]
Teesre pass ke baad, teesra sabse bada element 90 ko array ke teesre se aakhri position par pahunchaya jata hai.
Chautha Pass:
Comparisons:
1. Pehle do elements ko compare karo: 45 aur 75. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
2. 75 aur 90 ko compare karo. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
3. 90 aur 175 ko compare karo. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
Chauthe pass ke baad, chautha sabse bada element 75 ko array ke chauthe se aakhri position par pahunchaya jata hai.
Panchwa Pass:
Comparisons:
1. Pehle do elements ko compare karo: 45 aur 75. Kyunki yeh sahi order mein hain, koi swap ki zarurat nahi.
Panchwe pass ke baad, array puri tarah se sort ho jata hai.
Toh, panchwe pass ke baad, sorted array yeh hoti hai: [45, 75, 90, 175, 802].
Declaration of Array and Swap in Accending order::
public class AccendingOrder_bubble_sort {
/*170,45,75,90,802,24 this is my array */
public static void swapArray(int temp, int arr[]) {
for ( int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
public static void main(String[] args) {
int arr[] = {175, 45, 75, 90, 802};
swapArray(0,arr);
System.out.print("New Array:");
for(int i = 0 ; i< arr.length; i++){
System.out.print(arr[i] + " ");
}
}
}
Time Complexity of Bubble Sort:
O(n^2) this will time complexity of bubble sort
Selection Sort: Divides the input list into two parts: the sorted part and the unsorted part. In each iteration, it selects the smallest (or largest) element from the unsorted part and moves it to the end of the sorted part.
Selection sort is a combination of searching and sorting. it sorts the array by repeatedlly finding the minimum element from the unsorted part.
Implementation of Selection Sort:
import javax.xml.transform.stream.StreamSource;
import java.sql.SQLOutput;
public class selectionSort {
public static void selection_sort(int arr[]){
int temp =0;
int min;
for(int i = 0 ; i < arr.length;i++){
min = i;
for(int j = i+1; j < arr.length; j++){
if(arr[j] < arr[min]){
min = j;
}
}temp = arr[i];//agar condition false ho jati j loop khtm ho jata hai to swap kardo
arr[i] = arr[min];
arr[min] = temp;
}
}
public static void main(String[] args) {
int arr[] = {38,59,9,18,6}; //this is array
selection_sort(arr);
System.out.println("Sorted Array:");
for(int i = 0 ;i < arr.length; i++){
System.out.print(arr[i] + " ");
}
}
}
PFA Images of Dry Run:
Insertion Sort: Divides the list into a sorted and an unsorted part. It iteratively takes an element from the unsorted part and inserts it into the correct position in the sorted part.
Merge Sort: A divide-and-conquer algorithm that recursively divides the list into smaller sublists, sorts those sublists, and then merges them back together.
Quick Sort: Also a divide-and-conquer algorithm. It selects a pivot element and partitions the list into two sublists: elements less than the pivot and elements greater than the pivot. It then recursively sorts the sublists.
Heap Sort: Builds a max-heap (or min-heap) from the input data and repeatedly removes the maximum (or minimum) element and inserts it into the sorted part.
Counting Sort: A non-comparison-based sorting algorithm that works well for integers within a known range. It counts the occurrences of each element and uses that information to place them in the correct order.
Radix Sort: Sorts elements by processing individual digits or characters from the least significant to the most significant. It's often used for integers or strings.
Bucket Sort: Distributes elements into a fixed number of buckets based on their values, sorts the buckets (often using another sorting algorithm), and concatenates the sorted buckets to produce the final sorted list.
Shell Sort: An extension of insertion sort that sorts distant elements first and then reduces the gap between elements being compared. It's known for its efficiency in practice.
Comb Sort: An improvement of bubble sort that eliminates small values near the end of the list quickly.
Cycle Sort: A sorting algorithm that reduces the number of writes to the original array.
Gnome Sort: A simple, comparison-based sorting algorithm that moves elements to their correct position by repeatedly comparing adjacent elements.
Stooge Sort: A recursive sorting algorithm with a relatively poor time complexity.
Bozo Sort: A highly inefficient sorting algorithm that repeatedly shuffles the list randomly until it's sorted.
Pancake Sorting: A sorting algorithm that sorts a disordered stack of pancakes in order of size.
These are some of the common sorting algorithms, but there are many more, each suited to different scenarios and constraints. The choice of sorting algorithm depends on factors such as the size of the data, the distribution of values, memory constraints, and desired time complexity.
Selection Sorting -
Here's a step-by-step explanation of the selection sort algorithm for sorting a list of numbers in ascending order:
- Find the minimum element in the unsorted part of the list.
- Swap the minimum element with the first element in the unsorted part.
- Move the boundary between the sorted and unsorted parts one element to the right.
- Repeat steps 1-3 until the entire list is sorted.
Here's a simple example of Selection sort in Java: -----------
package learningJava;
import java.util.*;
public class selectionSort {
public static void main(String[] args) {
// 1 6 4 3 0 2 ort this array
// temp = (arr[i]) -----
Scanner scan = new Scanner(System.in); //this is scanner for take input from console
System.out.print("Enter size of araay:");
int size = scan.nextInt(); //this is size or array
int minIndex;
int temp = 0; // temporary variable for swap
int arr [] = new int[size]; // array
System.out.println("Enter your array Element:");
for(int i = 0 ; i < size; i++) {
arr[i] = scan.nextInt(); //taking input from console on ith element
}
//compare with ith index
for(int i = 0 ; i < size; i++) {
minIndex = i;
for(int j = i+1; j < size; j++) {
//Swap process with temp variable
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
} /// ise ham loop ke bahar swap kar rhe kyo ki minimum nikalna hai
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
System.out.println(arr[i]);
}
// for(int i = 0 ; i < size; i++) {
}
}
Implement Bubble Sort algorithm---------
package learningJava;
import java.util.*;
public class bubbleSort {
public static void main(String[] args) {
//bubble sort algorithm of Array
//i+1= j
// " " 6 4 3 2 1
//Temp// Temp=5
Scanner scan = new Scanner(System.in); //This is scanner class
System.out.print("Enter Size of Array:");
int size = scan.nextInt(); //variable for allocate size of array
int temp = 0; //this is temporary memory
int [] arr = new int[size]; // array
System.out.println("Enter Array Element:");
for(int i = 0 ; i < size; i++) { //loop for take array element
arr[i] = scan.nextInt(); //take array loop wise
}
for(int i = 0 ; i < size-1; i++) {
for(int j =0 ; j < size-1; j++) {
//compare with 1st {0! 1) index of array
if(arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.print(arr[i]);
}
}
}
Comments
Post a Comment