DEV Community

Cover image for Selection Sorts
Harsh Bhardwaj
Harsh Bhardwaj

Posted on

Selection Sorts

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-

  1. Start with the first element as the minimum.
  2. Compare this element to the rest of the elements to find the smallest.
  3. Swap the smallest element with the first element.
  4. 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;
}

Enter fullscreen mode Exit fullscreen mode

Special Points-

  1. Simplicity
  2. Unstable
  3. Inplace Sorting
  4. Might be beneficial for small number of cases

Image description

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It's efficient and consistent.

Steps

  1. Build a Heap
  2. 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.
    1. Heapify the root of the heap.
    2. 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;
}

Enter fullscreen mode Exit fullscreen mode

Special Points:

  1. Binary Heap is used
  2. Non Stable Algorithm
  3. T(C) - O(nlogn)
  4. Sort in Place S(C) - O(1) {Constant}

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more

Top comments (0)

nextjs tutorial video

Youtube Tutorial Series 📺

So you built a Next.js app, but you need a clear view of the entire operation flow to be able to identify performance bottlenecks before you launch. But how do you get started? Get the essentials on tracing for Next.js from @nikolovlazar in this video series 👀

Watch the Youtube series