Selection Sort
Problem:
● Given an array of N elements.
● Sort them in ascending order using Selection Sort.
Algorithm:
● Loop through array.
● Pick the smallest element from the unsorted part.
● Swap it with the first unsorted position.
● Repeat until array is sorted.
Complexity:
● Time: O(N²)
● Space: O(1)
Pseudocode:
for i = 0 to N-2:
minIdx = i
for j = i+1 to N-1:
if A[j] < A[minIdx]:
minIdx = j
swap A[i], A[minIdx]
Code (C++):
#include<iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for(int i=0; i<n-1; i++) {
int minIdx = i;
for(int j=i+1; j<n; j++) {
if(arr[j] < arr[minIdx]) minIdx = j;
}
swap(arr[i], arr[minIdx]);
}
}
int main() {
int n; cin >> n;
int arr[n];
for(int i=0; i<n; i++) cin >> arr[i];
selectionSort(arr, n);
for(int i=0; i<n; i++) cout << arr[i] << " ";
}
Insertion Sort
Problem:
● Sort an array with Insertion Sort.
Algorithm:
● Start from 2nd element.
● Compare it with left side.
● Shift larger values right.
● Insert element at correct place.
Complexity:
● Best: O(N) (already sorted).
● Worst: O(N²).
Pseudocode:
for i = 1 → N-1:
key = A[i]
j = i-1
while j >= 0 and A[j] > key:
A[j+1] = A[j]
j--
A[j+1] = key
Code:
#include<iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for(int i=1; i<n; i++) {
int key = arr[i], j = i-1;
while(j>=0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
int main() {
int n; cin >> n;
int arr[n];
for(int i=0; i<n; i++) cin >> arr[i];
insertionSort(arr, n);
for(int i=0; i<n; i++) cout << arr[i] << " ";
}
Bubble Sort
Problem:
● Sort array using Bubble Sort.
Algorithm:
● Compare adjacent pairs.
● Swap if left > right.
● Repeat until array sorted.
Complexity:
● Best: O(N)
● Worst: O(N²)
Pseudocode:
for i=0 to N-1:
for j=0 to N-i-2:
if A[j] > A[j+1]:
swap A[j], A[j+1]
Code:
#include<iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for(int i=0; i<n-1; i++) {
for(int j=0; j<n-i-1; j++) {
if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
}
}
}
int main() {
int n; cin >> n;
int arr[n];
for(int i=0; i<n; i++) cin >> arr[i];
bubbleSort(arr, n);
for(int i=0; i<n; i++) cout << arr[i] << " ";
}
Quick Sort
Problem:
● Sort array using Quick Sort (divide and conquer).
Algorithm:
● Pick pivot.
● Partition into < pivot and > pivot.
● Recursively sort both parts.
Complexity:
● Best: O(N log N)
● Worst: O(N²).
Pseudocode:
quickSort(A, low, high):
if low < high:
p = partition(A, low, high)
quickSort(A, low, p-1)
quickSort(A, p+1, high)
Code:
#include<iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low-1;
for(int j=low; j<high; j++) {
if(arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i+1], arr[high]);
return i+1;
}
void quickSort(int arr[], int low, int high) {
if(low < high) {
int p = partition(arr, low, high);
quickSort(arr, low, p-1);
quickSort(arr, p+1, high);
}
}
int main() {
int n; cin >> n;
int arr[n];
for(int i=0; i<n; i++) cin >> arr[i];
quickSort(arr, 0, n-1);
for(int i=0; i<n; i++) cout << arr[i] << " ";
}
Merge Sort
Problem:
● Sort array using Merge Sort.
Algorithm:
● Divide into halves.
● Sort each half recursively.
● Merge two sorted halves.
Complexity:
● Always O(N log N).
Pseudocode:
mergeSort(A, l, r):
if l < r:
mid = (l+r)/2
mergeSort(A, l, mid)
mergeSort(A, mid+1, r)
merge(A, l, mid, r)
Code:
#include<iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
int n1 = m-l+1, n2 = r-m;
int L[n1], R[n2];
for(int i=0; i<n1; i++) L[i] = arr[l+i];
for(int j=0; j<n2; j++) R[j] = arr[m+1+j];
int i=0, j=0, k=l;
while(i<n1 && j<n2) {
if(L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while(i<n1) arr[k++] = L[i++];
while(j<n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if(l < r) {
int m = (l+r)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
int main() {
int n; cin >> n;
int arr[n];
for(int i=0; i<n; i++) cin >> arr[i];
mergeSort(arr, 0, n-1);
for(int i=0; i<n; i++) cout << arr[i] << " ";
}