Sorting DSA in c++
Bubble
Sort
#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 arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) cout
<< arr[i] << " ";
return 0;
}
2. Selection Sort
Time Complexity: O(n²)
Stable: No
#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[minIdx], arr[i]);
}
}
int main() {
int arr[] = {64,
25, 12, 22, 11};
int n =
sizeof(arr) / sizeof(arr[0]);
selectionSort(arr,
n);
cout <<
"Sorted array: ";
for (int i = 0; i
< n; i++) cout << arr[i] << " ";
return 0;
}
3. Insertion Sort
Time Complexity: O(n²)
Stable: Yes
#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 arr[] = {12,
11, 13, 5, 6};
int n =
sizeof(arr) / sizeof(arr[0]);
insertionSort(arr,
n);
cout <<
"Sorted array: ";
for (int i = 0; i
< n; i++) cout << arr[i] << " ";
return 0;
}
4. Merge Sort
Time Complexity: O(n log n)
Stable: Yes
#include <iostream>
using namespace std;
// Function to merge two halves
void merge(int arr[], int left, int mid, int right) {
int n1 = mid -
left + 1;
int n2 = right -
mid;
int leftArr[n1],
rightArr[n2];
for (int i = 0; i
< n1; i++)
leftArr[i] =
arr[left + i];
for (int i = 0; i
< n2; i++)
rightArr[i] =
arr[mid + 1 + i];
int i = 0, j = 0,
k = left;
while (i < n1
&& j < n2) {
if (leftArr[i]
<= rightArr[j]) {
arr[k] =
leftArr[i];
i++;
} else {
arr[k] =
rightArr[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] =
leftArr[i];
i++;
k++;
}
while (j < n2)
{
arr[k] =
rightArr[j];
j++;
k++;
}
}
// Function to perform merge sort
void mergeSort(int arr[], int left, int right) {
if (left <
right) {
int mid = left
+ (right - left) / 2;
mergeSort(arr,
left, mid);
mergeSort(arr,
mid + 1, right);
merge(arr,
left, mid, right);
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i
< size; i++)
cout <<
arr[i] << " ";
cout <<
endl;
}
int main() {
int arr[] = {12,
11, 13, 5, 6, 7};
int size =
sizeof(arr) / sizeof(arr[0]);
cout <<
"Original array: ";
printArray(arr,
size);
mergeSort(arr, 0,
size - 1);
cout <<
"Sorted array: ";
printArray(arr,
size);
return 0;
}
Explanation:
- Divide:
The array is recursively divided into two halves until single-element
arrays are left.
- Merge:
The two sorted halves are merged in sorted order.
- Merge
Function: It merges two sorted subarrays into a single sorted array.
- Time
Complexity: O(nlogn)O(n \log n)O(nlogn)
Let me know if you need further explanation! 🚀
4o
You said:
give me explanation also
ChatGPT said:
ChatGPT
Explanation of Merge Sort
Merge Sort is a divide and conquer algorithm that
splits an array into smaller subarrays, sorts them, and then merges them back
together.
Steps of Merge Sort
- Divide:
- The
array is recursively divided into two halves until each subarray contains
only one element (a single element is always sorted).
- Conquer
(Sort & Merge):
- The
sorted subarrays are merged back together in sorted order.
Code Breakdown
1. Merging Two Sorted Arrays (merge function)
cpp
CopyEdit
void merge(int arr[], int left, int mid, int right) {
int n1 = mid -
left + 1; // Size of left subarray
int n2 = right -
mid; // Size of right subarray
int leftArr[n1],
rightArr[n2]; // Temporary arrays
// Copy data into
temporary arrays
for (int i = 0; i
< n1; i++)
leftArr[i] =
arr[left + i];
for (int i = 0; i
< n2; i++)
rightArr[i] =
arr[mid + 1 + i];
int i = 0, j = 0,
k = left; // Indices for left, right, and merged array
// Merge the two
sorted subarrays
while (i < n1
&& j < n2) {
if (leftArr[i]
<= rightArr[j]) {
arr[k] =
leftArr[i];
i++;
} else {
arr[k] =
rightArr[j];
j++;
}
k++;
}
// Copy remaining
elements from left array (if any)
while (i < n1)
{
arr[k] =
leftArr[i];
i++;
k++;
}
// Copy remaining
elements from right array (if any)
while (j < n2)
{
arr[k] =
rightArr[j];
j++;
k++;
}
}
📌 What it does:
- Copies
elements into two temporary arrays.
- Compares
and merges them in sorted order.
- If
any elements remain, they are copied into the main array.
2. Recursive Sorting (mergeSort function)
cpp
CopyEdit
void mergeSort(int arr[], int left, int right) {
if (left <
right) {
int mid = left
+ (right - left) / 2; // Find middle index
mergeSort(arr,
left, mid); // Sort first half
mergeSort(arr,
mid + 1, right); // Sort second half
merge(arr,
left, mid, right); // Merge the sorted halves
}
}
📌 What it does:
- Base
Case: If there's one element, it's already sorted.
- Recursive
Calls: Splits the array into halves.
- Merge
Step: Merges two sorted halves.
3. Printing the Array (printArray function)
cpp
CopyEdit
void printArray(int arr[], int size) {
for (int i = 0; i
< size; i++)
cout <<
arr[i] << " ";
cout <<
endl;
}
📌 What it does:
- Simply
prints the array elements.
4. Main Function (main)
cpp
CopyEdit
int main() {
int arr[] = {12,
11, 13, 5, 6, 7};
int size =
sizeof(arr) / sizeof(arr[0]);
cout <<
"Original array: ";
printArray(arr,
size);
mergeSort(arr, 0,
size - 1);
cout <<
"Sorted array: ";
printArray(arr,
size);
return 0;
}
5. Quick Sort
Time Complexity: O(n log n)
Stable: No
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot =
arr[high], i = low - 1;
for (int j = low;
j < high; j++) {
if (arr[j]
< pivot) 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 pi =
partition(arr, low, high);
quickSort(arr,
low, pi - 1);
quickSort(arr,
pi + 1, high);
}
}
int main() {
int arr[] = {10,
7, 8, 9, 1, 5};
int n =
sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0,
n - 1);
cout <<
"Sorted array: ";
for (int i = 0; i
< n; i++) cout << arr[i] << " ";
return 0;
}
6. Heap Sort
Time Complexity: O(n log n)
Stable: No
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i,
left = 2 * i + 1, right = 2 * i + 2;
if (left < n
&& arr[left] > arr[largest]) largest = left;
if (right < n
&& arr[right] > arr[largest]) largest = right;
if (largest != i)
{
swap(arr[i],
arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2
- 1; i >= 0; i--) heapify(arr, n, i);
for (int i = n -
1; i > 0; i--) {
swap(arr[0],
arr[i]);
heapify(arr,
i, 0);
}
}
int main() {
int arr[] = {12,
11, 13, 5, 6, 7};
int n =
sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout <<
"Sorted array: ";
for (int i = 0; i
< n; i++) cout << arr[i] << " ";
return 0;
}
2. Selection Sort
Concept:
- Finds
the minimum element and swaps it with the first unsorted element.
- Reduces
the unsorted portion one step at a time.
Time Complexity:
- Best/Worst/Average:
O(n²)
C++ Code:
cpp
CopyEdit
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i
< n - 1; i++) {
int min_idx =
i;
for (int j = i
+ 1; j < n; j++) {
if (arr[j]
< arr[min_idx])
min_idx = j;
}
swap(arr[i],
arr[min_idx]); // Swap the minimum element with the first element
}
}
int main() {
int arr[] = {64,
25, 12, 22, 11};
int n =
sizeof(arr) / sizeof(arr[0]);
selectionSort(arr,
n);
for (int i = 0; i
< n; i++)
cout <<
arr[i] << " ";
return 0;
}
Sure! Let's break down the Selection Sort code step
by step.
Understanding the Code
1. Header Files and Namespace
#include <iostream>
using namespace std;
- #include
<iostream>: Allows input/output operations (cout for printing).
- using
namespace std;: Avoids the need to write std::cout, std::endl, etc.
2. Selection Sort Function
void selectionSort(int arr[], int n) {
- This
function sorts an array arr[] of size n using the Selection Sort
algorithm.
Loop to Iterate Over Array
for (int i = 0; i < n - 1; i++) {
- Outer
loop: Runs n-1 times because after sorting n-1 elements, the last
element will already be in place.
Finding the Minimum Element
int min_idx = i; // Assume the first unsorted element is the
smallest
- Assume
the first element of the unsorted part is the smallest.
for (int j = i + 1; j < n; j++) {
if (arr[j] <
arr[min_idx]) // Find the minimum element
min_idx = j;
}
In Selection Sort, we’re looking for the smallest
element in the unsorted part of the array and then swapping it into its
correct position.
Here’s the key:
- i
represents the current index we’re placing in the correct position.
- j
starts from i + 1 because:
- We
assume that the smallest element in the remaining unsorted portion
is at index i.
- So,
there’s no need to compare it with itself — we start looking from the next
element.
- If
j started at i, it would always compare the element with itself first,
which is unnecessary.
- Inner
loop: Scans the remaining unsorted part of the array to find the smallest
element.
- If
we find a smaller element, we update min_idx.
Swapping the Minimum Element
swap(arr[i], arr[min_idx]); // Swap the found minimum
element with the first unsorted element
- After
finding the smallest element, we swap it with the first unsorted
element.
3. Main Function
cpp
CopyEdit
int main() {
int arr[] = {64,
25, 12, 22, 11};
int n =
sizeof(arr) / sizeof(arr[0]); // Calculate array size
- sizeof(arr)
/ sizeof(arr[0]): Finds the number of elements in the array.
cpp
CopyEdit
selectionSort(arr, n); // Call the sorting function
- Calls
the selectionSort() function to sort the array.
cpp
CopyEdit
for (int i = 0; i < n; i++)
cout <<
arr[i] << " ";
- Prints
the sorted array.
cpp
CopyEdit
return 0;
- Ends
the program.
Dry Run (Step-by-Step Execution)
Input Array
arr[] = {64, 25, 12, 22, 11}
Iteration 1 (i = 0)
- Find
the smallest in {64, 25, 12, 22, 11} → Smallest = 11 at index 4.
- Swap
64 ↔ 11
- Array
after swap: [11, 25, 12, 22, 64]
Iteration 2 (i = 1)
- Find
the smallest in {25, 12, 22, 64} → Smallest = 12 at index 2.
- Swap
25 ↔ 12
- Array
after swap: [11, 12, 25, 22, 64]
Iteration 3 (i = 2)
- Find
the smallest in {25, 22, 64} → Smallest = 22 at index 3.
- Swap
25 ↔ 22
- Array
after swap: [11, 12, 22, 25, 64]
Iteration 4 (i = 3)
- Find
the smallest in {25, 64} → Smallest = 25 (already at correct
position).
- No
swap needed.
Final Sorted Array
[11, 12, 22, 25, 64] ✅
This blog provides excellent insights into the challenges students face while preparing academic essays. Every assignment has unique requirements, making personalized guidance very important. Students looking for custom essay writing help should choose experienced academic professionals who understand university standards and deliver original work. Your article offers practical advice that encourages better organization and stronger writing skills. Thank you for sharing such helpful information. I look forward to exploring more educational content on your blog in the future.
ReplyDelete