Scribd
Upload
4 views2 pages

Sorting Algorithms Explained: Code & Complexity

The document provides an overview of four sorting algorithms: Selection Sort, Bubble Sort, Insertion Sort, and Merge Sort, detailing their time complexity (TC) and space complexity (SC). Each algorithm is accompanied by its implementation code in C++. Selection and Bubble Sorts have a TC of O(N^2) and SC of O(1), Insertion Sort has a TC of O(N) and SC of O(1), while Merge Sort has a TC of O(N log N) and SC of O(N).

Uploaded by

boardofwar22
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

Sorting Algorithms Explained: Code & Complexity

The document provides an overview of four sorting algorithms: Selection Sort, Bubble Sort, Insertion Sort, and Merge Sort, detailing their time complexity (TC) and space complexity (SC). Each algorithm is accompanied by its implementation code in C++. Selection and Bubble Sorts have a TC of O(N^2) and SC of O(1), Insertion Sort has a TC of O(N) and SC of O(1), while Merge Sort has a TC of O(N log N) and SC of O(N).

Uploaded by

boardofwar22
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1) Selection Sorting:TC->O(N2), SC->O(1)

Selecting minimum value and Swap it : CODE:


void selectionSort(int arr[], int n)
{
int mini;
for(int i=0;i<=n-2;i++){
mini=i;
for(int j=i;j<=n-1;j++){
if(arr[mini]>arr[j]) mini=j;
}
swap(arr[mini],arr[i]);
}
}

=================================================
CODE:
void bubbleSort(int arr[], int n) {
2) Bubble Sorting: TC->O(N2), SC->O(1) for(int i=n-1;i>0;i--){
for(int j=0;j<i;j++){
if (arr[j]>arr[j+1])
swap(arr[j+1],arr[j]);
}
}
}
(Or)
void bubbleSort(int arr[], int n) {
for(int i=n-1;i>0;i--){
int flag=0;
for(int j=0;j<i;j++){
if (arr[j]>arr[j+1]){
swap(arr[j+1],arr[j]);
flag=1;
}
}
if(flag==0) break;
}
}
================================================
CODE:
3) Insertion Sorting:TC->O(N ), SC->O(1)
2

Placing a value in its “Correct Position”. void insertionSort(int arr[], int n){
int i,j;
for (int i=0;i<n;i++){
j=i;
while(j>0 && arr[j-1]>arr[j]){
// swap(arr[j-1],arr[j]);
int temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
j--;
}
}
}

===============================================================
4) Merge Sorting:TC->O(NlogN), SC->O(N) void merge(int arr[], int l, int mid, int r)
{
Divide and conquer Method, Recursion vector<int> temp;
Splitting and merging: int left=l;
int right=mid+1;
while(left<=mid && right<=r){
if(arr[left]<=arr[right]){
temp.push_back(arr[left]);
left++;
}
else{
temp.push_back(arr[right]);
right++;
}
}
while(left<=mid){
temp.push_back(arr[left]);
left++;
}
while(right<=r){
temp.push_back(arr[right]);
right++;
}
for(auto i=l;i<=r;i++)
arr[i]=temp[i-l];
}

void mergeSort(int arr[], int l, int r)


{
if(l>=r) return;
int mid=l+(r-l)/2;
mergeSort(arr,l,mid);
mergeSort(arr,mid+1,r);
merge(arr,l,mid,r);
}

You might also like