Straight Sort-
Comparison based Algorithm that swaps minimum element in place to achieve a
T(C) = O(n^2) _ and a _S(C) = O(1) as the swapping occurs in place.
Steps-
- Start with the first element as the minimum.
- Compare this element to the rest of the elements to find the smallest.
- Swap the smallest element with the first element.
- Move to the next element and repeat until the list is sorted.
Code-
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: \n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Special Points-
- Simplicity
- Unstable
- Inplace Sorting
- Might be beneficial for small number of cases
Heap Sort
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It's efficient and consistent.
Steps
- Build a Heap
- Sorting
1.Build a max heap from the input data.
2.The largest element is swapped with the last element of the heap and
removed from the heap.
- Heapify the root of the heap.
- Repeat the process until all elements are sorted.
Code-
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int 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) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements from heap one by one
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: \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Special Points:
- Binary Heap is used
- Non Stable Algorithm
- T(C) - O(nlogn)
- Sort in Place S(C) - O(1) {Constant}
Top comments (0)