Member Avatar for nurulshidanoni

How to do a selection sort?
Which I want to sort in descending order this data

1 50
2 90
3 40

  • 3 Contributors
  • 2 Replies
  • 105 Views
  • 10 Hours Discussion Span
  • Latest Post Latest Post by Laiq Ahmed

Dani AI

Generated

There’s a mix-up in the replies: ’s step-by-step is describing insertion-style shifting (key + moves), not selection sort. Selection sort instead repeatedly finds the largest (or smallest) remaining element and swaps it into the next position. The code below shows a plain selection-sort implementation in C++ that sorts an array of (id, value) pairs in descending order by the value while keeping the ids paired.

#include <iostream>
#include <vector>
#include <utility>

int main() {
    std::vector<std::pair<int,int>> a = {{1,50}, {2,90}, {3,40}};
    int n = (int)a.size();
    for (int i = 0; i < n - 1; ++i) {
        int max_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j].second > a[max_idx].second)
                max_idx = j;
        }
        if (max_idx != i)
            std::swap(a[i], a[max_idx]);
    }
    for (const auto &p : a)
        std::cout << p.first << '\t' << p.second << '\n';
}

Notes and troubleshooting:

  • Selection sort is in-place and simple but O(n^2) in all cases; fine for tiny arrays, not for large data.
  • By default selection sort is not stable (swapping can change the relative order of equal keys). To preserve order, extract the chosen item and shift the block right instead of swapping; that is stable but still O(n^2).
  • Common mistakes: wrong loop bounds (use i < n-1), comparing the wrong field (compare .second when sorting by value), or swapping only the value instead of the whole pair.
  • For practical code use std::sort with a comparator for performance, or std::stable_sort if stability is required.

This clarifies the difference from ’s insertion-style explanation and gives a direct selection-sort sample tailored to the (id,value) data asked for by .

Recommended Answers

All 2 Replies

Member Avatar for Nick Evan
Member Avatar for Laiq Ahmed

agreed with niek_e he has given you the good resource for selection sort.

let me discuss what I know about selection sort.

selection sort is simple it just select the element and put the selected element in correct position.
in your case the data is 50, 90, 40.

if you want to sort in descending order.
i) loop on i through the array from 2nd element to end ( make sure your array size is greater than 1).
ii) pick the ith element in key (i.e. 90 in this case its the selected element).
iii) loop on j from (i-1)st element down to zero.
iv) check if key > jth element.
v) yes ! then move jth element to j+1st position. (i.e. making room for 90 in your case).
vi) no! break.
vii). set the key at (j+1)st position.

lets run on your data.
Pass 1.
key = 90.
we start looping on j=1.
checking 90 > 50
yes! moving 50 to 2nd position
j=0, breaks the above loop.
setting key at 1st position.
now array = 90, 50, 40

Pass 2.
key = 40.
we start looping on j = 2.
check 40 > 50.
no ! break.

setting key at 3rd position. (which already was 40).

Pass three, the parent loop breaks. as i == size of array.

so the sorted array is 90, 50, 40.
Hope this helps.
check whether its stable sort or not ?. what about inplace ?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.