Sorting is a fundamental operation in computer science, often used to organize and preprocess data. Today’s problems focused on implementing basic sorting algorithms, analyzing their efficiency, and solving problems that involve efficient data arrangement.
1. Bubble Sort
Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The algorithm's primary drawback is its inefficiency, with a time complexity of O(n^2) in the worst case. However, it's an excellent starting point for understanding sorting concepts.
public class BubbleSort{
public static int[] Sort(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]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {1, 5, 7, 2, 9, 4};
System.out.println("Array before Sorting: ");
for(int i : arr)
System.out.print(i+" ");
arr = Sort(arr);
System.out.println();
System.out.println("Array after sorting: ");
for(int i: arr)
System.out.print(i+" ");
}
}
2. Selection Sort
Selection Sort repeatedly selects the smallest (or largest) element from the unsorted portion of the list and moves it to the sorted portion. While it’s more intuitive than Bubble Sort, it still has a time complexity of O(n^2).
public class SelectionSort {
public static int[] Sort(int arr[]){
for(int i=0; i<arr.length-1; i++){
int min_index = i;
for(int j=i+1; j<arr.length; j++){
if(arr[j] < arr[min_index])
min_index = j;
}
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
return arr;
}
public static void main(String[] args) {
int[] arr = {1, 5, 7, 2, 9, 4};
System.out.println("Array before Sorting: ");
for(int i : arr)
System.out.print(i+" ");
arr = Sort(arr);
System.out.println();
System.out.println("Array after sorting: ");
for(int i: arr)
System.out.print(i+" ");
}
}
3. Sort an Array of 0s, 1s, and 2s
This problem involves sorting an array containing only 0s, 1s, and 2s without using a sorting algorithm. A variation of the Dutch National Flag algorithm allows solving this in O(n) time by using three pointers to partition the array.
public class DutchNationalFlag {
public static int[] Sort(int arr[]){
int low = 0;
int mid = 0;
int high = arr.length-1;
while(mid < high){
if(arr[mid] == 0){
int temp = arr[low];
arr[low] = arr[mid];
arr[mid] = temp;
mid++;
low++;
}else if(arr[mid] == 1)
mid++;
else if(arr[mid] == 2){
int temp = arr[high];
arr[high] = arr[mid];
arr[mid] = temp;
mid++;
high--;
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {0, 1, 2, 1, 1, 2, 0, 2, 1, 0};
System.out.println("Array before Sorting: ");
for(int i : arr)
System.out.print(i+" ");
arr = Sort(arr);
System.out.println();
System.out.println("Array after sorting: ");
for(int i: arr)
System.out.print(i+" ");
}
}
4. Insertion Sort with Swap Count
Insertion Sort builds the sorted list one element at a time by placing each element in its correct position. By counting the shifts or swaps made during sorting, we gain insights into the sorting process and its efficiency. The algorithm has a worst-case time complexity of O(n^2), but it’s efficient for nearly sorted data.
public class InsertionSort {
public static int[] Sort(int arr[]){
int count = 0;
for(int i=1; i<arr.length; i++){
if(arr[i]<arr[i-1]){
int num = arr[i];
int j = i;
while(arr[j-1] >= num){
arr[j] = arr[j-1];
j--;
count++;
}
arr[j] = num;
}
}
System.out.println();
System.out.println();
System.out.println("Total number of shifts to sort the array: "+count);
return arr;
}
public static void main(String[] args) {
int[] arr = {1, 5, 7, 2, 9, 4};
System.out.println("Array before Sorting: ");
for(int i : arr)
System.out.print(i+" ");
arr = Sort(arr);
System.out.println();
System.out.println("Array after sorting: ");
for(int i: arr)
System.out.print(i+" ");
}
}
5. Merge Two Sorted Arrays Without Extra Space
Merging two sorted arrays without using extra space involves modifying the arrays in place. The challenge is to ensure that the combined array is sorted efficiently, using O(n.m) time for arrays of size n and m. This problem highlights the importance of optimizing memory usage in sorting-related tasks.
public class Merge2SortedArrays {
public static void MergeArray(int[] arr1, int[] arr2){
int arr[] = new int[arr1.length+arr2.length];
int index1 = 0;
int index2 = 0;
for(int i=0; i<arr.length; i++){
if(index1 == arr1.length || index2 == arr2.length){
if(index1 != arr2.length){
arr[i] = arr1[index1];
index1++;
}else{
arr[i] = arr2[index2];
index2++;
}
}
else if(arr1[index1]<arr2[index2]){
arr[i] = arr1[index1];
index1++;
}else if(arr1[index1] > arr2[index2]){
arr[i] = arr2[index2];
index2++;
}
}
System.out.print("Merged Array: ");
for(int i : arr)
System.out.print(i+" ");
}
public static void main(String[] args) {
int[] arr1 = {1, 3, 5, 7, 9};
int[] arr2 = {2, 4, 6, 8, 10};
System.out.print("Array 1: ");
for(int i : arr1)
System.out.print(i+" ");
System.out.println();
System.out.print("Array 2: ");
for(int i : arr2)
System.out.print(i+" ");
System.out.println();
MergeArray(arr1, arr2);
}
}
Reflection
Day 11 focused on foundational sorting techniques and emphasized the importance of understanding algorithmic efficiency. Problems like sorting an array of 0s, 1s, and 2s and merging arrays without extra space showcased practical applications of sorting concepts. These exercises have built a strong base for exploring more advanced sorting algorithms and problems in the coming days. 🚀