Introduction:
Sorting is a fundamental operation in computer science, playing a crucial role in various applications and algorithms. Sorting involves arranging elements in a specific order, making it easier to search, retrieve, and analyze data. There are numerous sorting algorithms, each with its own unique approach and time complexity. In this blog, we'll explore some commonly used sorting techniques and see their code.
1) Selection Sort
Introduction: Selection Sort is a simple sorting algorithm that repeatedly selects the minimum element from an unsorted portion of the array and places it at the beginning. This process continues until the entire array is sorted.
Time Complexity: - Best: O(N^2) - Average: O(N^2) - Worst: O(N^2)
Code:
int main()
{
int n = 5;
int arr[] = { 9, 1, 5, 6, 3 };
for (int i = 0; i < 5; i++) {
int position = 0, minimum = 1e5;
for (int j = i; j < n; j++) {
if (arr[j] < minimum) {
position = j;
minimum = arr[j];
}
}
swap(arr[i], arr[position]);
}
for (int i = 0; i < n; i++) {
cout << arr[i] << ' ';
}
return 0;
}
2) Bubble Sort
Introduction: Bubble Sort is a comparison-based 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.
Time Complexity:
Best: O(N) Average: O(N^2) Worst: O(N^2)
Code:
int main()
{
int n = 5;
int arr[] = { 9, 1, 5, 6, 3 };
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
for (int i = 0; i < n; i++)
cout << arr[i] << ' ';
return 0;
}
3) Insertion Sort
Introduction: It iterates through the array, inserts each element into its correct position in the final sorted array, and increases the size of the sorted array after each insertion.
Time Complexity:
Best: O(N) Average: O(N^2) Worst: O(N^2) Code:
int main()
{
int n = 5;
int arr[] = { 9, 1, 5, 6, 3 };
for (int i = 1; i < n; i++) {
int position = i;
while (arr[position] < arr[position - 1]) {
swap(arr[position], arr[position - 1]);
position--;
if (position == 0)
break;
}
}
for (int i = 0; i < n; i++)
cout << arr[i] << ' ';
return 0;
}
4) Merge Sort
Introduction: Merge Sort is a divide-and-conquer algorithm that divides the array into two halves, recursively sorts them, and then merges the sorted halves.
Time Complexity:
Best: O(Nlog(N)) Average: O(Nlog(N)) Worst: O(Nlog(N))
Code:
void merge(int arr[], int l, int m, int r)
{
vector<int> tmp;
int left = l;
int right = m + 1;
while (left <= m && right <= r) {
if (arr[left] < arr[right]) {
tmp.push_back(arr[left]);
left++;
}
else {
tmp.push_back(arr[right]);
right++;
}
}
while (left <= m) {
tmp.push_back(arr[left]);
left++;
}
while (right <= r) {
tmp.push_back(arr[right]);
right++;
}
for (int i = l; i <= r; i++) {
arr[i] = tmp[i - l];
}
}
void mergeSort(int arr[], int l, int r)
{
if (r == l)
return;
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
int main()
{
int n = 5;
int arr[] = { 9, 1, 5, 6, 3 };
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << ' ';
}
return 0;
}
5) Quick Sort
Introduction: Quick Sort is a divide-and-conquer sorting algorithm that partitions the array into smaller segments, sorts them, and combines them to achieve the final sorted array.
Time Complexity:
Best: O(Nlog(N)) Average: O(Nlog(N)) Worst: O(N^2)
Code:
int partition(vector<int>& arr, int low, int high)
{
int pivot = arr[low];
int p1 = low;
int p2 = high;
while (p1 < p2) {
while (arr[p1] <= pivot && p1 <= high - 1) {
p1++;
}
while (arr[p2] > pivot && p2 >= low + 1) {
p2--;
}
if (p1 < p2)
swap(arr[p1], arr[p2]);
}
swap(arr[low], arr[p2]);
return p2;
}
void quickSort(vector<int>& arr, int low, int high)
{
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int main()
{
int n = 5;
vector<int> arr = { 9, 1, 5, 6, 3 };
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << ' ';
}
return 0;
}
Conclusion:
In conclusion, sorting is a fundamental operation in computer science, and understanding different sorting techniques is crucial for developing efficient algorithms and optimizing data manipulation tasks. You can visualize these sorting techniques on beautiful website Visualgo. Each sorting algorithm comes with its own set of advantages, disadvantages, and use cases. Let's recap the key takeaways from the discussed sorting techniques.
In conclusion, sorting is an fundamental operation in computer science, and it is essential to know how to sort in order to create effective algorithms. There are a variety of sorting algorithms available, each with its own set of pros, cons, and applications. The main points of the sorting techniques that were covered can be summarised as follows.
Selection Sort: Simple and intuitive, but inefficient for large datasets due to its quadratic time complexity (O(N^2).
Bubble Sort: Easy to implement but tends to be inefficient for large datasets, also with quadratic time complexity. Best-case scenario occurs when the array is nearly sorted (O(N)).
Insertion Sort: Efficient for small datasets and partially sorted data. It has quadratic time complexity (O(N^2)) but performs well in practice for small arrays.
Merge Sort: A divide-and-conquer algorithm with a stable O(N log N) time complexity. It is efficient for large datasets and guarantees consistent performance.
Quick Sort: Another divide-and-conquer algorithm with an average time complexity of O(N log N). It is widely used and efficient, but its performance can degrade to O(N^2) in the worst case.
