Table of contents
- Q1. Implement Bubble Sort and analyze its time complexity.
- Q2. Implement Selection Sort and analyze its time complexity
- Q3. Solve the "sort an array of 0s, 1s, and 2s" problem.
- Q4. Implement Insertion Sort and count the number of shifts/swaps during sorting.
- Q5. Solve the "merge two sorted arrays without extra space" problem.
Today’s focus was on mastering the basics of sorting algorithms. I implemented Bubble Sort, Selection Sort, and Insertion Sort while analyzing their time complexities. Additionally, I worked on solving problems like sorting an array of 0s, 1s, and 2s, counting shifts/swaps during Insertion Sort, and merging two sorted arrays without using extra space. These exercises helped me solidify my understanding of fundamental sorting techniques and their efficiency.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Implement Bubble Sort and analyze its time complexity.
#include <iostream>
using namespace std;
void bubbleSort(int arr[],int size){
for(int i=0;i<size-1;i++){
// Outer loop runs for size-1 iterations
for(int j=0;j<size-i-1;j++){
// Inner loop for comparing adjacent elements
if(arr[j]>arr[j+1]){
// Swap if the current element is greater than the next
swap(arr[j],arr[j+1]);
}
}
}
cout<<"The sorted array is: ";
for(int i=0;i<size;i++){
cout<<arr[i]<<" ";
}
}
int main()
{
int n;
cout<<"Enter length of the array: ";
cin>>n;
int arr[n];
cout<<"Enter the elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
bubbleSort(arr,n);
return 0;
}
This C++ code implements the Bubble Sort algorithm to sort an array of integers. The program first asks the user to input the length of the array (n) and then the elements of the array. The bubbleSort function is responsible for sorting the array using the bubble sort technique, which repeatedly compares adjacent elements in the array and swaps them if they are in the wrong order. The outer loop runs size-1 times, ensuring that each pass bubbles the largest unsorted element to its correct position. The inner loop performs the actual comparisons and swaps for each pass. After sorting, the sorted array is printed to the console. The time complexity of bubble sort is O(n^2) in the worst and average cases because each pair of adjacent elements is compared and potentially swapped for every element in the array. In the best case (when the array is already sorted), the time complexity is O(n) if optimized to detect no swaps during a pass.
Q2. Implement Selection Sort and analyze its time complexity
#include <iostream>
using namespace std;
void selectionSort(int arr[],int n){
for(int i=0;i<=n-2;i++){
int min=i; // Assume the current element is the minimum
for(int j=i+1;j<n;j++){
if(arr[j]<arr[min]){
min=j; // Update the minimum index if a smaller element is found
}
}
if(min!=i){
swap(arr[min],arr[i]); // Swap the minimum element with the current element
}
}
}
int main(){
int n;
cout<<"Enter length of the array: ";
cin>>n;
int arr[n];
cout<<"Enter the elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
selectionSort(arr,n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
This code implements the Selection Sort algorithm, which is a simple comparison-based sorting algorithm. It works by repeatedly selecting the smallest (or largest, depending on sorting order) element from the unsorted portion of the array and swapping it with the element at the current position. The process begins with the first element, assuming it to be the minimum, and compares it with all remaining elements to find the smallest one. Once the smallest element is found, it is swapped with the element at the current position. This process is repeated for each element in the array, progressively moving through the array until it's fully sorted. The time complexity of this algorithm is O(n^2) in both the worst and average cases because it uses two nested loops: one to pick the current element and another to find the minimum element. The space complexity is O(1) since it only requires a constant amount of extra space for swapping.
Q3. Solve the "sort an array of 0s, 1s, and 2s" problem.
#include <iostream>
using namespace std;
void sortArrayof012s(int arr[], int n){
int high=n-1;
int low=0;
int mid=0;
while(mid<=high){ // Loop until mid crosses high
if(arr[mid]==0){
// If the element is 0, swap it with the element at low pointer
swap(arr[mid],arr[low]);
low++;
mid++;
}
else if(arr[mid]==1){
// If the element is 1, just move mid pointer
mid++;
}
else if(arr[mid]==2){
// If the element is 2, swap it with the element at high pointer
swap(arr[mid],arr[high]);
high--;
}
}
}
int main()
{
int n;
cout<<"Enter length of the array: ";
cin>>n;
int arr[n];
cout<<"Enter the elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
sortArrayof012s(arr,n);
cout<<"The sorted array is: ";
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
return 0;
}
This code solves the "Sort an array of 0s, 1s, and 2s" problem using the Dutch National Flag algorithm. The array consists of only three distinct elements: 0s, 1s, and 2s, and the goal is to sort the array in linear time. The algorithm uses three pointers: low, mid, and high. Initially, low is set to the beginning of the array, high is set to the end, and mid starts from the first element. The algorithm iterates through the array with the mid pointer. If arr[mid] is 0, it swaps the element with arr[low] and increments both low and mid. If arr[mid] is 1, it simply moves the mid pointer forward. If arr[mid] is 2, it swaps the element with arr[high] and decrements high, without moving mid since the swapped element needs to be processed. This approach ensures the array is sorted in a single pass, achieving O(n) time complexity and O(1) space complexity.
Q4. Implement Insertion Sort and count the number of shifts/swaps during sorting.
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n){
int count=0;
for(int i=1;i<n;i++){
int j=i;
while(j>0 && arr[j-1]>arr[j]){
// Swap elements if the previous element is greater
swap(arr[j-1],arr[j]);
count+=1;
j--; // Move to the previous element
}
}
cout<<"The number of swaps/shifts to sort the array were: "<<count<<endl;
}
int main(){
int n;
cout<<"Enter length of the array: ";
cin>>n;
int arr[n];
cout<<"Enter the elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
insertionSort(arr,n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
This code implements Insertion Sort while also counting the number of swaps/shifts performed during sorting. The algorithm iterates through the array from the second element to the last. For each element, it checks if the previous elements are greater and shifts them one position to the right to make space for the current element. This process continues until the correct position for the current element is found. The count variable keeps track of the number of swaps made. If a swap occurs, it increments the count. After sorting, the program outputs the total number of swaps/shifts that occurred and displays the sorted array. The time complexity of this algorithm is O(n^2) in the worst case, and the space complexity is O(1).
Q5. Solve the "merge two sorted arrays without extra space" problem.
#include <iostream>
using namespace std;
#include <algorithm>
void merge(int arr1[],int n1,int arr2[],int n2){
int left=n1-1; // Start from the end of the first array
int right=0; // Start from the beginning of the second array
while(left>=0 && right<n2){
if(arr1[left]>arr2[right]){
// Swap elements if the current element of the first array is greater
swap(arr1[left],arr2[right]);
}
left--; // Move left pointer backward
right++; // Move right pointer forward
}
// Sort both arrays after rearranging
sort(arr1, arr1 + n1);
sort(arr2, arr2 + n2);
}
void display_merged_array(int arr1[], int n1, int arr2[],int n2){
cout<<"The merged array is: ";
for(int i=0;i<n1;i++){
cout<<arr1[i]<<" ";
}
for(int i=0;i<n2;i++){
cout<<arr2[i]<<" ";
}
}
int main()
{
int n1,n2;
cout<<"Enter length of the first array: ";
cin>>n1;
int arr1[n1];
cout<<"Enter the elements of the first array(in sorted order): ";
for(int i=0;i<n1;i++){
cin>>arr1[i];
}
cout<<"Enter length of the second array: ";
cin>>n2;
int arr2[n2];
cout<<"Enter the elements of the second array(in sorted order): ";
for(int i=0;i<n2;i++){
cin>>arr2[i];
}
merge(arr1,n1,arr2,n2);
display_merged_array(arr1,n1,arr2,n2);
return 0;
}
This code solves the problem of merging two sorted arrays without using extra space. The algorithm works by comparing the largest element of the first array (arr1[left]) with the smallest element of the second array (arr2[right]). If the element from arr1 is greater, it swaps the two elements. After this rearrangement, both arrays may be unsorted, so they are sorted again using the sort() function from the C++ Standard Library. The merge function performs this process while maintaining the original arrays, without needing additional space. The display_merged_array function then prints the elements of both arrays after merging. The time complexity is O(n1 log n1 + n2 log n2), where n1 and n2 are the lengths of the two arrays.
Today's practice provided a deeper insight into sorting algorithms and their complexities. From implementing Bubble, Selection, and Insertion Sorts to solving practical problems like sorting arrays with limited elements and merging arrays, I feel more confident in tackling a wide range of sorting challenges. Ready for more advanced topics on Day 12!