sorting in data structure
Sorting in the context of data structures refers to the
arrangement of data elements in a specific order. The order might be ascending
or descending, and the goal is to make it easier to search for and retrieve
specific elements.
Bubble sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the
list, compares adjacent elements, and swaps them if they are in the wrong
order.
The pass through the list is repeated until the list is
sorted. Here's a step-by-step explanation of each iteration of the Bubble Sort
algorithm in C++:
Now, let's break down the algorithm step by step:
1. Initial Array: `64 25 12 22 11`
2. First Iteration (i=0):
- Compare and swap `64`
and `25`: `25 64 12 22 11`
- Compare and swap `64` and `12`: `25 12
64 22 11`
- Compare and swap `64` and `22`: `25 12
22 64 11`
- Compare and swap `64` and `11`: `25 12
22 11 64`
3. Second Iteration (i=1):
- Compare and swap `25` and `12`: `12 25
22 11 64`
- Compare and swap `25` and `22`: `12 22
25 11 64`
- Compare and swap `25` and `11`: `12 22
11 25 64`
4. Third Iteration (i=2):
- Compare and swap `12` and `22`: `12 11
22 25 64`
- Compare and swap `22` and `11`: `12 11
22 25 64`
5. Fourth Iteration (i=3):
- Compare and swap `12` and `11`: `11 12
22 25 64`
6. Sorted Array: `11 12 22 25 64`
The algorithm has completed when no more swaps are needed
in a pass, indicating that the array is now sorted.
Let's consider an array of integers as an example:
#include <iostream>
using namespace std;
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++)
{
for (int j
= 0; j < n - i - 1; j++) {
//
Compare adjacent elements
if
(arr[j] > arr[j + 1]) {
//
Swap them if they are in the wrong order
swap(arr[j],
arr[j + 1]);
}
}
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) /
sizeof(arr[0]);
cout << "Original array:
";
for (int i = 0; i < n; i++) {
cout
<< arr[i] << " ";
}
bubbleSort(arr, n);
cout << "\nSorted array:
";
for (int i = 0; i < n; i++) {
cout
<< arr[i] << " ";
}
return 0;
}
selection sort
Selection sort is a simple sorting algorithm that works by
repeatedly finding the minimum element from the unsorted part of the array and
putting it at the beginning. Here's a step-by-step explanation of the selection
sort algorithm in C++:
Here's a step-by-step breakdown of the selection sort
algorithm using the example array {64, 25, 12, 22, 11}:
1. Iteration 1:
- Minimum element: 11 (at index 4)
- Swap elements at index 0 and index 4:
{11, 25, 12, 22, 64}
2. Iteration 2:
- Minimum element: 12 (at index 2)
- Swap elements at index 1 and index 2:
{11, 12, 25, 22, 64}
3. Iteration 3:
- Minimum element: 22 (at index 3)
- Swap elements at index 2 and index 3:
{11, 12, 22, 25, 64}
4. Iteration 4:
- Minimum element: 25 (at index 3)
- Swap elements at index 3 and index 4:
{11, 12, 22, 25, 64}
5. The array is now sorted: {11, 12, 22, 25, 64}
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++)
{
// Assume
the current index is the minimum
int
minIndex = i;
// Find the
index of the minimum element in the unsorted part
for (int j
= i + 1; j < n; j++) {
if
(arr[j] < arr[minIndex]) {
minIndex
= j;
}
}
// Swap the
found minimum element with the first element
int temp =
arr[minIndex];
arr[minIndex]
= arr[i];
arr[i] =
temp;
// Print
the array after each iteration
cout
<< "Iteration " << i + 1 << ": ";
for (int k
= 0; k < n; k++) {
cout
<< arr[k] << " ";
}
cout
<< endl;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) /
sizeof(arr[0]);
cout << "Original array:
";
for (int i = 0; i < n; i++) {
cout
<< arr[i] << " ";
}
cout << endl;
selectionSort(arr, n);
cout << "Sorted array:
";
for (int i = 0; i < n; i++) {
cout
<< arr[i] << " ";
}
cout << endl;
return 0;
}
insertion sort
Insertion Sort is a simple sorting algorithm that builds
the final sorted array one item at a time. It is much less efficient on large
lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
However, it performs well for small datasets or lists that are mostly sorted.
Here's a step-by-step explanation of how Insertion Sort works in C++:
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key =
arr[i];
int j = i - 1;
// Move elements
of arr[0..i-1] that are greater than key to one position ahead of their current
position
while (j >= 0
&& arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] =
key;
// Print the
array after each iteration
cout <<
"Iteration " << i << ": ";
for (int k = 0;
k < n; k++) {
cout << arr[k] << " ";
}
cout <<
endl;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array:
";
for (int i = 0; i < n; i++) {
cout <<
arr[i] << " ";
}
cout << endl;
insertionSort(arr, n);
cout << "Sorted array:
";
for (int i = 0; i < n; i++) {
cout <<
arr[i] << " ";
}
cout << endl;
return 0;
}
Let's go through each iteration of the insertion sort
algorithm with the provided array {12, 11, 13, 5, 6}:
1. Iteration 1:
- Array: 12 11 13 5 6
- Key: 11
- Compare 11 with 12, swap if needed: 11 12 13
5 6
2. Iteration 2:
- Array: 11 12 13 5 6
- Key: 13
- Compare 13 with 12, no swap: 11 12 13 5 6
3. Iteration 3:
- Array: 11 12 13 5 6
- Key: 5
- Compare 5 with 13, swap: 11 12 5 13 6
- Compare 5 with 12, swap: 11 5 12 13 6
- Compare 5 with 11, swap: 5 11 12 13 6
4. Iteration 4:
- Array: 5 11 12 13 6
- Key: 6
- Compare 6 with 13, swap: 5 11 12 6 13
- Compare 6 with 12, swap: 5 11 6 12 13
- Compare 6 with 11, swap: 5 6 11 12 13
The final sorted array is 5 6 11 12 13. The outer loop
iterates over each element starting from the second one, and the inner loop
compares and swaps elements to insert the current element into its correct
position in the sorted subarray.
quicksort
Quicksort is a popular sorting algorithm that follows the
divide-and-conquer paradigm. It works by selecting a pivot element from the
array and partitioning the other elements into two sub-arrays according to
whether they are less than or greater than the pivot. The process is then
applied recursively to the sub-arrays.
Here's an example of the Quicksort algorithm in C++ with a
step-by-step explanation for each iteration:
#include <iostream>
using namespace std;
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
int partition(int arr[], int low, int high) {
// Select the pivot element (in
this case, the last element)
int pivot = arr[high];
// Initialize the index of the
smaller element
int i = low - 1;
// Traverse the array and rearrange
elements
for (int j = low; j < high; j++)
{
if (arr[j]
< pivot) {
i++;
swap(arr[i],
arr[j]);
}
}
// Swap the pivot element with the
element at (i + 1), putting the pivot in its correct position
swap(arr[i + 1], arr[high]);
// Return the index of the pivot
element
return i + 1;
}
void quicksort(int arr[], int low, int high) {
if (low < high) {
//
Partition the array into two halves
int
pivotIndex = partition(arr, low, high);
//
Recursively sort the sub-arrays
quicksort(arr,
low, pivotIndex - 1);
quicksort(arr,
pivotIndex + 1, high);
}
}
int main() {
// Example array
int arr[] = {12, 4, 5, 6, 7, 3, 1,
15};
// Calculate the size of the array
int size = sizeof(arr) /
sizeof(arr[0]);
// Print the original array
cout << "Original array:
";
for (int i = 0; i < size; i++) {
cout
<< arr[i] << " ";
}
cout << endl;
// Apply Quicksort
quicksort(arr, 0, size - 1);
// Print the sorted array
cout << "Sorted array:
";
for (int i = 0; i < size; i++) {
cout
<< arr[i] << " ";
}
cout << endl;
return 0;
}
Let's go through the steps for a simple example:
Original array: 12 4 5 6 7 3 1 15
1. First Iteration:
- Pivot: 15
- Partition: 12 4 5 6 7 3 1 | 15
- Swap: 1 4 5 6 7 3 | 12 | 15
- Pivot index: 6 (element 15 is now in
its correct position)
Now the array is partitioned into two
sub-arrays: [1, 4, 5, 6, 7, 3] and [15]. The pivot (15) is in its correct
position.
2. Second Iteration (left sub-array):
- Pivot: 3
- Partition: 1 | 4 | 5 | 6 7 | 3
- Swap: 1 | 4 | 5 | 3 | 7 | 6
- Pivot index: 3 (element 3 is in its
correct position)
The left sub-array is now [1, 4, 5, 3, 7,
6], and the pivot (3) is in its correct position.
3. Third Iteration (right sub-array):
- Pivot: 7
- Partition: 1 4 5 3 | 6 | 7
- Swap: 1 4 5 3 | 6 | 7
- Pivot index: 4 (element 7 is in its
correct position)
The right sub-array is now [6, 7], and
the pivot (7) is in its correct position.
4. Continue with recursive calls:
- The left sub-array [1, 4, 5, 3] will be
partitioned, and the pivot 5 will be in its correct position.
- The right sub-array [6] is already
sorted.
- The left sub-array [1, 4, 3] will be
partitioned, and the pivot 4 will be in its correct position.
- The right sub-array [6] is already
sorted.
- ...
5. Final Result:
The sorted array is [1, 3, 4, 5, 6, 7,
12, 15].
mergesort
Certainly! Merge Sort is a popular divide-and-conquer
sorting algorithm that recursively divides an array into two halves, sorts each
half, and then merges them back together. Here's a step-by-step explanation of
the Merge Sort algorithm without using vectors, focusing on each iteration:
Let's assume you have an array `arr` of size `n` that you
want to sort using Merge Sort.
1. Initial Array:
arr = [4, 2, 7, 1, 9, 5, 3, 8]
2. First Iteration:
- The array is divided into two halves:
`[4, 2, 7, 1]` and `[9, 5, 3, 8]`.
- Each half is recursively sorted using
the same Merge Sort algorithm.
- After sorting, the two halves are
merged together.
Left Half:
[4, 2, 7, 1]
Right Half:
[9, 5, 3, 8]
Merged Result:
[2, 4, 1, 7, 3, 5, 8, 9]
3. Second Iteration:
- The left and right halves of the array
are further divided and recursively sorted.
- The left half `[2, 4]` is divided into
`[2]` and `[4]`.
- The right half `[1, 7, 3, 5, 8, 9]` is
divided into `[1, 7, 3]` and `[5, 8, 9]`.
- After sorting, the divided and sorted
halves are merged back.
Left Half (of left half):
[2]
Right Half (of left half):
[4]
Merged Result (of left half):
[2, 4]
Left Half (of right half):
[1, 7, 3]
Right Half (of right half):
[5, 8, 9]
Merged Result (of right half):
[1, 3, 5, 7, 8, 9]
Final Merged Result (of the
entire array):
[1, 2, 3, 4, 5, 7, 8, 9]
4. Final Sorted Array:
[1, 2, 3, 4, 5, 7, 8, 9]
This process continues until the entire array is sorted.
The key step is the merging process, where two sorted halves are combined to
produce a larger sorted array. The recursion ensures that each subarray is
eventually sorted.
void merge(int arr[], int left, int mid, int right) {
int n1 = mid -
left + 1;
int n2 = right -
mid;
// Create
temporary arrays to hold the two halves
int L[n1], R[n2];
// Copy data to
temporary arrays L[] and R[]
for (int i = 0; i
< n1; i++)
L[i] =
arr[left + i];
for (int j = 0; j
< n2; j++)
R[j] = arr[mid
+ 1 + j];
// Merge the two
halves back into the original array
int i = 0, j = 0,
k = left;
while (i < n1
&& j < n2) {
if (L[i] <=
R[j]) {
arr[k] =
L[i];
i++;
} else {
arr[k] =
R[j];
j++;
}
k++;
}
// Copy the
remaining elements of L[], if there are any
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
// Copy the
remaining elements of R[], if there are any
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left <
right) {
// Same as
(left+right)/2, but avoids overflow for large left and right
int mid = left
+ (right - left) / 2;
// Recursively
sort the first and second halves
mergeSort(arr,
left, mid);
mergeSort(arr,
mid + 1, right);
// Merge the
sorted halves
merge(arr,
left, mid, right);
}
}
int main() {
int arr[] = {12,
11, 13, 5, 6, 7};
int arr_size =
sizeof(arr) / sizeof(arr[0]);
cout <<
"Given array is \n";
for (int i = 0; i
< arr_size; i++)
cout <<
arr[i] << " ";
cout <<
"\n";
// Perform merge
sort
mergeSort(arr, 0,
arr_size - 1);
cout <<
"Sorted array is \n";
for (int i = 0; i
< arr_size; i++)
cout <<
arr[i] << " ";
cout <<
"\n";
return 0;
}
0 Comments