Selection Sort Algorithm

1. Algorithm Explanation

Selection Sort is an in-place comparison-based sorting algorithm. It divides the input array into two parts:

• The subarray which is already sorted (initially empty).
• The subarray which remains to be sorted.

On each pass, it selects the smallest (or largest, for descending order) element from the unsorted portion and swaps it with the first element of that portion, growing the sorted region by one.

procedure selectionSort(A : array of items, n : integer)
    for i ← 0 to n – 2 do
        // Find index of minimum element in A[i…n–1]
        minIndex ← i
        for j ← i + 1 to n – 1 do
            if A[j] < A[minIndex] then
                minIndex ← j
            end if
        end for
        // Swap the found minimum with A[i]
        swap A[i] and A[minIndex]
    end for
end procedure

Time Complexity

• Best case: O(n²) — the inner loop always runs full length, regardless of input order.
• Average case: O(n²)
• Worst case: O(n²)

Memory Complexity

• Auxiliary space: O(1) — only a few variables for indices and swapping.
• Not stable by default (equal elements may change relative order).

---

2. Easy Problems Solvable by Selection Sort

2.1. Sort an Array of Integers

Problem: Given an array of integers, sort it in ascending order.

// C++ Implementation
#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& A) {
    int n = A.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j)
            if (A[j] < A[minIndex])
                minIndex = j;
        swap(A[i], A[minIndex]);
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    selectionSort(arr);
    cout << "Sorted array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    return 0;
}

2.2. Sort Characters in a String

Problem: Given a string, sort its characters in alphabetical order.

// C++ Implementation
#include <iostream>
#include <string>
using namespace std;

void selectionSort(string &s) {
    int n = s.length();
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j)
            if (s[j] < s[minIndex])
                minIndex = j;
        swap(s[i], s[minIndex]);
    }
}

int main() {
    string str = "selectionsort";
    selectionSort(str);
    cout << "Sorted string: " << str << endl;
    return 0;
}

---

3. Intermediate Problems Solvable by Selection Sort

3.1. Find the k-th Smallest Element

Problem: Given an array and integer k, find the k-th smallest element using partial selection sort.

// C++ Implementation
#include <iostream>
#include <vector>
using namespace std;

// Perform only k passes of selection sort
int kthSmallest(vector<int>& A, int k) {
    int n = A.size();
    for (int i = 0; i < k; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j)
            if (A[j] < A[minIndex])
                minIndex = j;
        swap(A[i], A[minIndex]);
    }
    return A[k - 1];
}

int main() {
    vector<int> arr = {7, 10, 4, 3, 20, 15};
    int k = 3;
    cout << "3rd smallest element is "
         << kthSmallest(arr, k)
         << endl;
    return 0;
}

3.2. Sort a Singly Linked List

Problem: Given a singly linked list, sort its nodes in ascending order of value.

// C++ Implementation
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int v) : data(v), next(nullptr) {}
};

// Swap data fields of two nodes
void swapNodeData(Node* a, Node* b) {
    int temp = a->data;
    a->data = b->data;
    b->data = temp;
}

void selectionSortList(Node* head) {
    for (Node* i = head; i != nullptr; i = i->next) {
        Node* minNode = i;
        for (Node* j = i->next; j != nullptr; j = j->next) {
            if (j->data < minNode->data)
                minNode = j;
        }
        swapNodeData(i, minNode);
    }
}

void printList(Node* head) {
    while (head) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // 4 -> 2 -> 1 -> 3
    Node* head = new Node(4);
    head->next = new Node(2);
    head->next->next = new Node(1);
    head->next->next->next = new Node(3);

    selectionSortList(head);
    cout << "Sorted list: ";
    printList(head);
    return 0;
}

---

4. Hard Problem Solvable by Selection Sort

4.1. Sort a Deck of Cards by Suit and Rank (Stable)

Problem: You have a deck of cards, each with a suit (♣, ♦, ♥, ♠) and rank (1–13). Sort the deck first by suit in the order ♣, ♦, ♥, ♠, then by rank ascending, while preserving the relative order of cards with identical suit and rank (stable).

// C++ Implementation (Stable Selection Sort)
#include <iostream>
#include <vector>
using namespace std;

struct Card {
    char suit;   // 'C', 'D', 'H', 'S'
    int rank;    // 1–13
};

// Map suit to its order
int suitOrder(char s) {
    switch (s) {
        case 'C': return 0;
        case 'D': return 1;
        case 'H': return 2;
        case 'S': return 3;
    }
    return 4;
}

// Comparator for cards
bool lessCard(const Card &a, const Card &b) {
    if (suitOrder(a.suit) != suitOrder(b.suit))
        return suitOrder(a.suit) < suitOrder(b.suit);
    return a.rank < b.rank;
}

// Stable selection sort: extract & shift
void stableSelectionSort(vector<Card>& deck) {
    int n = deck.size();
    for (int i = 0; i < n; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j) {
            if (lessCard(deck[j], deck[minIdx]))
                minIdx = j;
        }
        // Extract deck[minIdx] and shift right
        Card key = deck[minIdx];
        for (int j = minIdx; j > i; --j)
            deck[j] = deck[j - 1];
        deck[i] = key;
    }
}

int main() {
    vector<Card> deck = {
        {'H', 12}, {'C', 5}, {'D', 5}, {'H', 1},
        {'S', 13}, {'C', 12}, {'D', 1}, {'S', 1}
    };
    stableSelectionSort(deck);
    cout << "Sorted deck:\n";
    for (auto &c : deck) {
        cout << c.suit << c.rank << "  ";
    }
    cout << endl;
    return 0;
}