{"id":140,"date":"2026-07-14T08:27:24","date_gmt":"2026-07-14T08:27:24","guid":{"rendered":"https:\/\/blog.csfree.org\/?p=140"},"modified":"2026-07-15T15:07:04","modified_gmt":"2026-07-15T15:07:04","slug":"selection-sort-a-step-by-step-guide","status":"publish","type":"post","link":"https:\/\/blog.csfree.org\/index.php\/2026\/07\/14\/selection-sort-a-step-by-step-guide\/","title":{"rendered":"Selection Sorting – How does it work internally?"},"content":{"rendered":"\n

Selection Sorting – How does it work internally?<\/h2>\n\n\n\n

If we HAVE to speak about Sorting Techniques<\/strong>, Selection Sorting <\/strong>is another important sorting<\/strong>–algorithm<\/strong>.<\/p>\n\n\n\n

But first things first-<\/p>\n\n\n\n

What is Sorting?<\/h3>\n\n\n\n

At its core, sorting<\/strong> is just the process of arranging <\/strong>a messy collection of items into a specific, meaningful order.<\/p>\n\n\n\n

Here are two examples of sorting, we go through every day life:<\/p>\n\n\n\n

    \n
  • Numerical Order:<\/strong> Arranging numbers from smallest to largest (1, 2, 3\u2026) or largest to smallest (99, 98, 97\u2026).<\/li>\n\n\n\n
  • Alphabetical Order:<\/strong> Arranging words or strings from A to Z (like a phonebook contact list) or Z to A.<\/li>\n<\/ul>\n\n\n\n

    <\/p>\n\n\n\n

    What is Selection Sorting?<\/h3>\n\n\n\n

    Imagine you are holding a handful of unsorted playing cards, and you want to arrange them from smallest to largest. What\u2019s your natural instinct? You scan through all the cards, find the absolute lowest one, and pull it to the very front. Then, you look at the remaining cards, find the next lowest one, and place it right behind the first.<\/p>\n\n\n\n

    That is exactly how Selection Sort<\/strong> works. In computer science, Selection Sort<\/strong> is a fundamental, comparison-based sorting algorithm that operates on a direct, scanning principle. Instead of continuously swapping adjacent elements, it repeatedly steps through the unorganized portion of a data structure, scans the remaining elements to identify the absolute minimum (or maximum) value, and performs a single swap to place it into its final, correct position.<\/p>\n\n\n\n

    By maintaining a growing, sorted subarray at the beginning of the structure and shrinking the unsorted boundary with each pass, it systematically organizes data with a highly predictable, deterministic execution pattern.<\/p>\n\n\n\n

    Why it\u2019s better than Bubble Sort:<\/strong> While Bubble Sort <\/strong>frantically swaps elements constantly as it walks through the array, Selection Sort <\/strong>stays calm. It only makes one swap per pass<\/strong>, drastically reducing unnecessary memory writes!<\/p>\n\n\n\n

    Its characters include:<\/p>\n\n\n\n

      \n
    • In-Place Memory Execution<\/strong><\/li>\n<\/ul>\n\n\n\n

      Selection Sort requires an auxiliary (extra) space complexity of O(1)<\/strong>. It performs all its element swapping directly within the original array without needing to replicate or spawn temporary storage arrays.<\/p>\n\n\n\n

        \n
      • Predictable, Deterministic Performance<\/strong><\/li>\n<\/ul>\n\n\n\n

        Unlike Bubble Sort <\/strong>or Insertion Sort<\/strong>, Selection Sort <\/strong>does not care if your data is already perfectly sorted, completely reversed, or totally random. Because it is forced to scan the entire remaining unsorted section every single time just to ensure it has found the true minimum, its time complexity is always fixed:<\/p>\n\n\n\n

          \n
        • Best Case:<\/strong> O(n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/li>\n\n\n\n
        • Average Case:<\/strong> O(n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/li>\n\n\n\n
        • Worst Case:<\/strong> O(n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/li>\n<\/ul>\n\n\n\n
            \n
          • Highly Efficient for Memory Writes<\/strong><\/li>\n<\/ul>\n\n\n\n

            While its comparison count is high O(n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>), its swap count is exceptionally low. It performs a maximum of (n – 1) swaps<\/strong> in total. It only swaps data once per full pass, making it structurally superior to Bubble Sort if you are working on old flash memory hardware where writing to memory is drastically more expensive than reading from it.<\/p>\n\n\n\n

            Step-By-Step Example<\/h3>\n\n\n\n

            Let’s see how Selection Sort algorithm <\/strong>works on using a array: [7, 3, 9, 2, 6, 4]<\/code><\/strong>.<\/p>\n\n\n\n

            Note: <\/p>\n\n\n\n

              \n
            • The |<\/code><\/strong> bar separates the sorted section<\/strong> (left) from the unsorted section<\/strong> (right).<\/li>\n\n\n\n
            • In each pass, we scan the unsorted section to find the minimum<\/strong>, then swap it to the front of that section.<\/li>\n<\/ul>\n\n\n\n

              <\/p>\n\n\n\n

                \n
              • Step 1: The First Big Scan<\/strong><\/li>\n<\/ul>\n\n\n\n

                Starting array:<\/strong> [7, 3, 9, 2, 6, 4]<\/code><\/p>\n\n\n\n

                We assume the first element (7<\/code>) is our temporary minimum. Now we scan the rest to find something smaller:<\/p>\n\n\n\n

                  \n
                • Compare current min (7) with 3 : Is 3 < 7? Yes<\/strong> -> New tracked min = 3<\/strong><\/li>\n\n\n\n
                • Compare current min (3) with 9 : Is 9 < 3? No<\/strong> -> Keep tracked min = 3<\/strong><\/li>\n\n\n\n
                • Compare current min (3) with 2 : Is 2 < 3? Yes<\/strong> -> New tracked min = 2<\/strong><\/li>\n\n\n\n
                • Compare current min (2) with 6 : Is 6 < 2? No<\/strong> -> Keep tracked min = 2<\/strong><\/li>\n\n\n\n
                • Compare current min (2) with 4 : Is 4 < 2? No<\/strong> -> Keep tracked min = 2<\/strong><\/li>\n<\/ul>\n\n\n\n

                  End of Pass 1:<\/strong> The scan is complete. The absolute minimum found is 2<\/strong>. We make our one single swap<\/strong> for this pass, exchanging 2<\/strong> with the first element (7<\/code>).<\/p>\n\n\n\n

                  Array State :<\/em> [2 | 3, 9, 7, 6, 4]<\/code> (The 2 is now locked in place).<\/em><\/p>\n\n\n\n

                    \n
                  • Step 2: Finding the Next Smallest<\/strong><\/li>\n<\/ul>\n\n\n\n

                    Active boundary:<\/strong> [3, 9, 7, 6, 4]<\/code> (We ignore index 0 where 2 is)<\/em> <\/p>\n\n\n\n

                    We assume the first element of this section (3<\/code>) is our temporary minimum:<\/em><\/p>\n\n\n\n

                      \n
                    • Compare current min (3) with 9 : Is 9 < 3? No<\/strong> -> Keep tracked min = 3<\/strong><\/li>\n\n\n\n
                    • Compare current min (3) with 7 : Is 7 < 3? No<\/strong> -> Keep tracked min = 3<\/strong><\/li>\n\n\n\n
                    • Compare current min (3) with 6 : Is 6 < 3? No<\/strong> -> Keep tracked min = 3<\/strong><\/li>\n\n\n\n
                    • Compare current min (3) with 4 : Is 4 < 3? No<\/strong> -> Keep tracked min = 3<\/strong><\/li>\n<\/ul>\n\n\n\n

                      End of Pass 2:<\/strong> The scan is complete. The absolute minimum in this section is 3<\/strong>. Since it’s already at the front of the active boundary, no actual swap changes its position.<\/p>\n\n\n\n

                      Array State:<\/em> [2, 3 | 9, 7, 6, 4]<\/code> (The 3 is now locked in place).<\/em><\/p>\n\n\n\n

                        \n
                      • Step 3: Shrinking the Window<\/strong><\/li>\n<\/ul>\n\n\n\n

                        Active boundary:<\/strong> [9, 7, 6, 4]<\/code> (We now ignore 2 and 3)<\/em><\/p>\n\n\n\n

                        We assume the first element of this section (9<\/code>) is our temporary minimum:<\/em><\/p>\n\n\n\n

                          \n
                        • Compare current min (9) with 7 : Is 7 < 9? Yes<\/strong> -> New tracked min = 7<\/strong><\/li>\n\n\n\n
                        • Compare current min (7) with 6 : Is 6 < 7? Yes<\/strong> -> New tracked min = 6<\/strong><\/li>\n\n\n\n
                        • Compare current min (6) with 4 : Is 4 < 6? Yes<\/strong> -> New tracked min = 4<\/strong><\/li>\n<\/ul>\n\n\n\n

                          End of Pass 3:<\/strong> The scan is complete. The absolute minimum found is 4<\/strong>. Swap 4<\/strong> with the first element of this section (9<\/code>).<\/p>\n\n\n\n

                          Array State:<\/em> [2, 3, 4 | 7, 6, 9]<\/code> (The 4 is now locked in place).<\/em><\/p>\n\n\n\n

                            \n
                          • Step 4: Getting Closer<\/strong><\/li>\n<\/ul>\n\n\n\n

                            Active boundary:<\/strong> [7, 6, 9]<\/code><\/p>\n\n\n\n

                            We assume the first element of this section (7<\/code>) is our temporary minimum:<\/p>\n\n\n\n

                              \n
                            • Compare current min (7) with 6 : Is 6 < 7? Yes<\/strong> -> New tracked min = 6<\/strong><\/li>\n\n\n\n
                            • Compare current min (6) with 9 : Is 9 < 6? No<\/strong> -> Keep tracked min = 6<\/strong><\/li>\n<\/ul>\n\n\n\n

                              End of Pass 4:<\/strong> The scan is complete. The absolute minimum found is 6<\/strong>. Swap 6<\/strong> with the first element of this section (7<\/code>).<\/p>\n\n\n\n

                              Array State:<\/em> [2, 3, 4, 6 | 7, 9]<\/code> (The 6 is now locked in place).<\/em><\/p>\n\n\n\n

                                \n
                              • Step 5: The Final Matchup<\/strong><\/li>\n<\/ul>\n\n\n\n

                                Active boundary:<\/strong> [7, 9]<\/code><\/p>\n\n\n\n

                                We assume the first element of this section (7<\/code>) is our temporary minimum:<\/em><\/p>\n\n\n\n

                                  \n
                                • Compare current min (7) with 9 : Is 9 < 7? No<\/strong> -> Keep tracked min = 7<\/strong><\/li>\n<\/ul>\n\n\n\n

                                  End of Pass 5:<\/strong> The scan is complete. The absolute minimum is 7<\/strong>. It is already in place.<\/p>\n\n\n\n

                                    \n
                                  • Array State:<\/em> [2, 3, 4, 6, 7 | 9]<\/code> (The 7 is now locked in place).<\/em><\/li>\n<\/ul>\n\n\n\n
                                      \n
                                    • Step 6: The Last Element standing<\/strong><\/li>\n<\/ul>\n\n\n\n

                                      Active boundary:<\/strong> [9]<\/code><\/p>\n\n\n\n

                                      The algorithm looks at the final remaining element. Because an array of size n only requires (n-1) passes to fully organize, the final item (9<\/code>) is automatically in its correct position by default.<\/p>\n\n\n\n

                                      Final Sorted Array:<\/strong> [2, 3, 4, 6, 7, 9]<\/code><\/p>\n\n\n\n

                                      <\/p>\n\n\n\n

                                      Following is a program of the general Selection Sorting<\/strong>. (in C++)<\/p>\n\n\n\n

                                      #include <iostream>
                                      #include <vector>
                                      #include <utility> \/\/ Required for std::swap

                                      void selectionSort(std::vector<int>& arr) {
                                          int n = arr.size();
                                          
                                          \/\/ Outer loop: shifts the boundary of the sorted section
                                          for (int i = 0; i < n - 1; i++) {
                                              \/\/ Assume the current first element of the unsorted section is the minimum
                                              int minIndex = i;
                                              
                                              \/\/ Inner loop: scans the remaining unsorted elements to find the true minimum
                                              for (int j = i + 1; j < n; j++) {
                                                  if (arr[j] < arr[minIndex]) {
                                                      minIndex = j; \/\/ Update index of the smallest element found
                                                  }
                                              }
                                              
                                              \/\/ Optimization: Only swap if a smaller element was actually found
                                              if (minIndex != i) {
                                                  std::swap(arr[i], arr[minIndex]);
                                              }
                                          }
                                      }

                                      \/\/ Helper function to print the vector layout
                                      void printVector(const std::vector<int>& arr) {
                                          for (int num : arr) {
                                              std::cout << num << \" \";
                                          }
                                          std::cout << \"\\n\";
                                      }

                                      int main() {
                                          \/\/ Using the 6-digit array from our walkthrough example
                                          std::vector<int> numbers = {7, 3, 9, 2, 6, 4 };
                                          
                                          std::cout << \"Original Array: \";
                                          printVector(numbers);
                                          
                                          selectionSort(numbers);
                                          
                                          std::cout << \"Sorted Array:   \";
                                          printVector(numbers);
                                          
                                          return 0;
                                      }<\/strong><\/pre>\n\n\n\n
                                      Just like with Bubble Sort<\/strong>, switching your Selection Sort <\/strong>from ascending (smallest to largest) to descending order<\/strong> (largest to smallest) requires changing one single character<\/strong> in your code logic.<\/p>\n\n\n\n
                                      The updated code in Descending order will be:<\/p>\n\n\n\n
                                      void selectionSortDescending(std::vector<int>& arr) {\n    int n = arr.size();\n    \n    \/\/ Outer loop: shifts the boundary of the sorted section\n    for (int i = 0; i < n - 1; i++) {\n        \/\/ Assume the current first element is the largest (maximum)\n        int maxIndex = i;\n        \n        \/\/ Inner loop: scans the remaining elements to find the true maximum\n        for (int j = i + 1; j < n; j++) {\n            \/\/ FLIPPED: Change '<' to '>' to find the largest remaining number\n            if (arr[j] > arr[maxIndex]) {\n                maxIndex = j; \/\/ Update index of the largest element found\n            }\n        }\n        \n        \/\/ Only swap if a larger element was actually found down the line\n        if (maxIndex != i) {\n            std::swap(arr[i], arr[maxIndex]);\n        }\n    }\n}<\/strong><\/code><\/pre>\n\n\n\n
                                      <\/p>\n\n\n\n
                                      How is it different from Bubble Sort<\/strong>?<\/p>\n\n\n\n
                                      Feature\/Trait<\/th>Bubble Sort<\/th>Selection Sort<\/th><\/tr><\/thead>
                                      Core Concept<\/strong><\/td>Consistently compares and swaps adjacent elements<\/strong> if they are out of order, forcing values to drift to the end.<\/td>Scans the entire remaining array<\/strong> to find the absolute minimum value, then drops it into place with a single swap.<\/td><\/tr>
                                      Number of Swaps<\/strong><\/td>High (O(<\/strong>n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)):<\/strong> Continuous swapping throughout every pass. Memory-heavy on writes.<\/td>Low (O(n)):<\/strong> Performs at most (n – 1)<\/strong> total swaps (maximum 1 swap per pass). Excellent for low-write memory.<\/td><\/tr>
                                      Algorithm Stability<\/strong><\/td>Stable:<\/strong> Identical elements retain their original relative positioning because adjacent elements are only swapped if one is strictly greater\/less than the other.<\/td>Unstable:<\/strong> Long-distance swaps can easily bypass identical elements, destroying their original order.<\/td><\/tr>
                                      Adaptive Optimization<\/strong><\/td>Highly Adaptive:<\/strong> Can be optimized with a swapped<\/code> flag to exit early if the array becomes sorted mid-execution, giving it a Best-Case Time Complexity of O(n)<\/strong>.<\/td>Non-Adaptive:<\/strong> Cannot look ahead or stop early. It is blindly forced to run all passes and comparisons regardless of whether the array is already sorted, keeping its Best Case at O(<\/strong>n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/strong><\/td><\/tr>
                                      Time Complexity<\/strong><\/td>Best: O<\/strong>(n) (Optimized)

                                      Avg: O(<\/strong>n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/strong>

                                      Worst: O(<\/strong>n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/strong><\/td>                                      		Best: O(<\/strong>n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/strong>

                                      Avg: O(<\/strong>n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/strong>

                                      Worst: O(<\/strong>n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/strong><\/td><\/tr>
                                      Space Complexity<\/strong><\/td>O(1)<\/strong> (In-place)<\/td>O(1) <\/strong>(In-place)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
                                      <\/p>\n\n\n\n
                                      Selection Sort <\/strong>introduces a completely different philosophy to basic sorting. While it shares the exact same O(<\/strong>n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/strong> time complexity as Bubble Sort, it replaces chaotic, adjacent swapping with a patient, scanning approach\u2014making only one decisive move per pass.<\/p>\n\n\n\n
                                      Although it isn’t designed for massive datasets, its strict constraint of a maximum of (n-1) swaps makes it highly efficient for specialized hardware where reducing memory writes is critical.<\/p>\n\n\n\n
                                      <\/p>\n","protected":false},"excerpt":{"rendered":"
                                      Selection Sorting – How does it work internally? If we HAVE to speak about Sorting Techniques, Selection Sorting is another […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"disabled","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[66,49,50],"tags":[59,65,60,53,64,35,62,56],"class_list":["post-140","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-data-structures","category-sorting","tag-big-o-notation","tag-c","tag-data-structures","tag-dsa","tag-learning-to-code","tag-programming","tag-selection-sorting","tag-sorting-algorithms"],"_links":{"self":[{"href":"https:\/\/blog.csfree.org\/index.php\/wp-json\/wp\/v2\/posts\/140","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.csfree.org\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.csfree.org\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.csfree.org\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.csfree.org\/index.php\/wp-json\/wp\/v2\/comments?post=140"}],"version-history":[{"count":6,"href":"https:\/\/blog.csfree.org\/index.php\/wp-json\/wp\/v2\/posts\/140\/revisions"}],"predecessor-version":[{"id":178,"href":"https:\/\/blog.csfree.org\/index.php\/wp-json\/wp\/v2\/posts\/140\/revisions\/178"}],"wp:attachment":[{"href":"https:\/\/blog.csfree.org\/index.php\/wp-json\/wp\/v2\/media?parent=140"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.csfree.org\/index.php\/wp-json\/wp\/v2\/categories?post=140"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.csfree.org\/index.php\/wp-json\/wp\/v2\/tags?post=140"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}