{"id":4765,"date":"2025-09-02T22:26:30","date_gmt":"2025-09-02T20:26:30","guid":{"rendered":"https:\/\/mariusbancila.ro\/blog\/?p=4765"},"modified":"2025-09-02T22:26:32","modified_gmt":"2025-09-02T20:26:32","slug":"what-is-the-cpp-nth_element-algorithm","status":"publish","type":"post","link":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/","title":{"rendered":"What is the C++ nth_element algorithm?"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">The C++ standard library provides an algorithm called <code>nth_element()<\/code> that is a useful tool for partial sorting. But how does it work and where is it useful?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">First of all, the algorithm is defined as follows: given a range <code>[first, last)<\/code> and an <em>n<\/em>th element within the range, the algorithm partially sorts the range so that:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>the <em>n<\/em>th element is changed to whatever element would appear in that position if the range <code>[first, last)<\/code> was sorted<\/li><li>all the elements before it are smaller than or equal to it, although their order is unspecified<\/li><li>all the elements after it are greater than or equal to it, although their order is also unspecified<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Keep in mind that in C++ indexes are zero based. So <em>n<\/em>th = 0 means first element, <em>n<\/em>th = 1 means second element, <em>n<\/em>th = 5 means 6th element, and so on.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Here is a quick example:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">#include &lt;iostream>\n#include &lt;vector>\n#include &lt;print>\n#include &lt;algorithm>\n\nint main()\n{\n    std::vector&lt;int> v {9, 4, 3, 8, 1, 2, 1, 8, 7, 6};\n    auto mid = v.begin() + v.size() \/ 2;\n    std::nth_element(v.begin(), mid, v.end());\n\n    for(auto const &amp; e : v) \n        std::print(\"{} \", e);\n    std::println();\n}<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">The output of this program is:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">2 4 3 1 1 6 8 8 7 9<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">The vector <code>v<\/code> has 10 elements. Therefore, <code>mid<\/code>, is the 6th element (the one at index 5 &#8211; half the vector size). After partial sorting, the first 5 elements (2 4 3 1 1) are smaller than the 6th element (which incidentally is the value 6), and the last 4 elements (8 8 7 9) are greater than the 6th element, although neither are in a sorted order.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">You can also use the range algorithm <code>std::ranges::nth_element()<\/code> as follows:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">std::ranges::nth_element(v, mid);<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Now that we&#8217;ve seen how the algorithm works, let&#8217;s look at its uses cases.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Computing the median efficiently<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The <em>median<\/em> is the middle value in a sorted dataset. If the size of the dataset is odd, then the median is at the (zero-based) index <code>n\/2<\/code>. If the size of the dataset is even, then the median is the average (mean) value of the two middle values, at the (zero-based) indexes <code>n\/2 - 1<\/code> and <code>n\/2<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The median, should not be confused with the <em>mean<\/em> (or average, which is the sum of all the elements of the dataset divided by their number). The median is more useful than the mean in various scenarios because it&#8217;s not influenced by outliers. Here is an example: the monthly income of 10 households on a street is (in sorted order) 2500, 2700, 3100, 3200, 3300, 4500, 4900, 5100, 5500, 25000. The mean is 5980 because there is an outlier in the set, but the median is only 3900, which is very close to the mean value of the first 9 values in the dataset (3866).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Here is a C++ function that computes the median of a vector of integers:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">double compute_median(std::vector&lt;int> data) \n{\n   size_t mid = n \/ 2;\n\n   if (data.size() % 2 == 1) \n   {\n      std::nth_element(data.begin(), data.begin() + mid, data.end());\n      return data[mid];\n   }\n   else \n   {\n      std::nth_element(data.begin(), data.begin() + mid - 1, data.end());\n      int val1 = data[mid - 1];\n      std::nth_element(data.begin(), data.begin() + mid, data.end());\n      int val2 = data[mid];\n      return (val1 + val2) \/ 2.0;\n   }\n}<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Using the <code>nth_element()<\/code> algorithm to compute the median avoids sorting the dataset completely (with <code>O(n log n)<\/code> complexity) and runs in average <code>O(n)<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">There are various practical uses for the median such as the following:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>data analysis and statistics (income distribution such as in the previous mentioned example) where the median is more robust than the mean when data contains outliers<\/li><li>image processing: the median filter is a technique to reduce noise by replacing each pixel&#8217;s value with the median of its neighboring pixels within a defined window (for instance 3&#215;3)<\/li><li>sensors reading: the median of several readings can be used to reduce noise from environmental sensors<\/li><li>real time systems: for quick estimates of typical latency, response time, and other metrics<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Percentiles<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Percentiles are basically a generalized median. A percentile is a way to describe the relative position of a value in a dataset. The <em>p<\/em>th percentile is the value bellow which p% of the data falls. Examples:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>25th percentile: 25% of the values in a dataset are smaller than this value, the other 75% are greater<\/li><li>50th percentile: 50% of the values in a dataset are smaller than this value, the other 50% are greater; this is the median<\/li><li>99th percentile: 99% of the values in a dataset are smaller than this value, and only 1% are greater<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Common examples for percentiles:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>in education: &#8220;you score in the 95th percentile&#8221; means you are better than 95% of the students<\/li><li>in finance: &#8220;the 90th percentile loss&#8221; means only 10% of losses are larger<\/li><li>in system monitoring: &#8220;99th percentile response time request&#8221; means slowest 1% of requests<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">You can easily determine the percentile using <code>nth_element()<\/code> as shown in the following snippet:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">template &lt;typename Iter>\nvoid partial_percentile_sort(Iter first, Iter last, double const percentile) \n{\n   size_t n = std::distance(first, last);\n   if (n == 0 || percentile == 0.0) return;\n\n   size_t k = static_cast&lt;size_t>(percentile * n);\n   if (k == 0) k = 1;\n\n   std::nth_element(first, first + k, last);\n}\n\nint main()\n{\n   std::vector&lt;int> v{ 9, 1, 8, 2, 7, 3, 6, 4, 5 };\n\n   double percentile = 0.6; \/\/ smallest 60% of elements\n   partial_percentile_sort(v.begin(), v.end(), percentile);\n\n   std::print(\"First 60% smallest elements (unordered): \");\n   size_t k = static_cast&lt;size_t>(percentile * v.size());\n   for (size_t i = 0; i &lt; k; ++i)\n   {\n      std::print(\"{} \", v[i]);\n   }\n   std::println();\n}<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">Finding the smallest\/largest n elements<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The <code>nth_element()<\/code> algorithm is useful for determining the smaller or largest <code>n<\/code> elements in a sequence, without having to sort it entirely. If you do need the elements sorted, you can call <code>std::sort()<\/code> afterwards but only for the first <code>n<\/code> elements of the (partially sorted) range.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Here is how to determine the smallest n elements in a range:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">std::vector&lt;int> v {9, 4, 3, 8, 1, 2, 1, 8, 7, 6};\nauto n = n;\n\nstd::nth_element(v.begin(), v.begin() + n, v.end());\nstd::sort(v.begin(), v.begin() + n);<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Here is how to determine the largest n elements in a range:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">std::vector&lt;int> v {9, 4, 3, 8, 1, 2, 1, 8, 7, 6};\nauto n = n;\n\nstd::nth_element(v.begin(), v.begin() + n, v.end(), std::greater&lt;>{});\nstd::sort(v.begin(), v.begin() + n);<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">As you can see, the only difference is the use of <code>std::greater&lt;>{}<\/code> for comparing the elements.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Practical use cases for the smallest \/ largest n elements include the following:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>leaderboards \/ rankings: you need to determine the first 10\/25\/100\/etc. players in a tournament with a large number of participants; using <code>nth_element()<\/code> allows you to only sort the small number of elements you need not the entire data set<\/li><li>search results: fetching the most relevant search results ranked by a score<\/li><li>resource monitoring: find the processes with the largest memory consumption on a server<\/li><li>data analysis and statistics: find the top earning individuals in a group, find the least performing students in a school, etc.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Quicksort and pivot selection<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Quicksort is a commonly used algorithm for sorting that works by selecting a pivot from the sequence of elements to sort, then partition the sequence into elements less than the pivot, the pivot, and elements greater than the pivot, and then recursively apply quicksort on the two partitions. However, its efficiency depends on the value of the pivot:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>if the pivot is near the median, the partitioning is balanced and the performance is <code>O(n log n)<\/code><\/li><li>if the pivot is the min or max value, the partitioning is unbalanced and the worst case scenario occurs with performance of <code>O(n^2)<\/code><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Therefore, the selection of the pivot is very important in the performance of the algorithm:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>random pivot gives god average behavior, but not always<\/li><li>median of 3 or 5 random elements is more robust and avoids worst case scenarios<\/li><li>median of the whole array degrades performance to <code>O(n log^2 n)<\/code> because you must partially sort the array at every recursion step<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Here is an example for how to compute the median of three random elements in a sequence of integers:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int median_of_three(std::vector&lt;int> const &amp; v)\n{\n    std::array&lt;int,3> sample = { v.front(), v[v.size()\/2], v.back() };\n    auto mid = sample.begin() + 1;\n    std::nth_element(sample.begin(), mid, sample.end());\n    return *mid;\n}<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">The following snippet shows an implementation of quicksort using a median of three values for the pivot:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">#include &lt;iostream>\n#include &lt;vector>\n#include &lt;print>\n#include &lt;algorithm>\n\ntemplate &lt;typename Iter>\nIter median_of_three(Iter first, Iter last)\n{\n   Iter mid = first + (last - first) \/ 2;\n   Iter last_elem = last - 1;\n\n   if (*mid &lt; *first) \n      std::iter_swap(mid, first);\n   if (*last_elem &lt; *first) \n      std::iter_swap(last_elem, first);\n   if (*last_elem &lt; *mid) \n      std::iter_swap(last_elem, mid);\n\n   return mid;\n}\n\ntemplate &lt;typename Iter>\nvoid quicksort(Iter first, Iter last)\n{\n   if (last - first &lt;= 1) return;\n\n   \/\/ Choose pivot using median of three and move it to the end\n   Iter pivot_iter = median_of_three(first, last);\n   std::iter_swap(pivot_iter, last - 1);\n   auto pivot = *(last - 1);\n\n   Iter left = first;\n   Iter right = last - 2;\n\n   while (true)\n   {\n      while (left &lt;= right &amp;&amp; *left &lt; pivot) ++left;\n      while (left &lt;= right &amp;&amp; *right > pivot) --right;\n      if (left >= right) break;\n      std::iter_swap(left, right);\n      ++left;\n      --right;\n   }\n\n   \/\/ put pivot back in place\n   std::iter_swap(left, last - 1);\n\n   \/\/ recurse on strict subranges\n   quicksort(first, left);\n   quicksort(left + 1, last);\n}\n\nint main()\n{\n   std::vector&lt;int> v{ 9, 1, 8, 2, 7, 3, 6, 4, 5 };\n\n   quicksort(v.begin(), v.end());\n\n   for (int x : v)\n      std::print(\"{} \", x);\n   std::println();\n}<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">The <code>nth_element()<\/code> algorithm has many applications with some typical cases presented here. Remember that, even though all the examples here used iterators-based algorithm, you can also use the ranges equivalent. More about the algorithm can be found <a href=\"https:\/\/en.cppreference.com\/w\/cpp\/algorithm\/nth_element.html\" target=\"_blank\" rel=\"noopener\" title=\"\">here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The C++ standard library provides an algorithm called nth_element() that is a useful tool for partial sorting. But how does it work and where is it useful? First of all, the algorithm is defined as follows: given a range [first, last) and an nth element within the range, the algorithm partially sorts the range so &#8230; <a title=\"What is the C++ nth_element algorithm?\" class=\"read-more\" href=\"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/\" aria-label=\"Read more about What is the C++ nth_element algorithm?\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[7],"tags":[557,451,649],"class_list":["post-4765","post","type-post","status-publish","format-standard","hentry","category-c","tag-algorithms","tag-c","tag-nth_element"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.1.1 - aioseo.com -->\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Marius Bancila\"\/>\n\t<meta name=\"keywords\" content=\"algorithms,c++,nth_element\" \/>\n\t<link rel=\"canonical\" href=\"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.1.1\" \/>\n\t\t<meta property=\"og:locale\" content=\"en_US\" \/>\n\t\t<meta property=\"og:site_name\" content=\"Marius Bancila&#039;s Blog | About code. Mostly on C++\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"What is the C++ nth_element algorithm?\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2025-09-02T20:26:30+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2025-09-02T20:26:32+00:00\" \/>\n\t\t<meta name=\"twitter:card\" content=\"summary\" \/>\n\t\t<meta name=\"twitter:title\" content=\"What is the C++ nth_element algorithm?\" \/>\n\t\t<script type=\"application\/ld+json\" class=\"aioseo-schema\">\n\t\t\t{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2025\\\/09\\\/02\\\/what-is-the-cpp-nth_element-algorithm\\\/#article\",\"name\":\"What is the C++ nth_element algorithm?\",\"headline\":\"What is the C++ nth_element algorithm?\",\"author\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"publisher\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\"},\"datePublished\":\"2025-09-02T22:26:30+02:00\",\"dateModified\":\"2025-09-02T22:26:32+02:00\",\"inLanguage\":\"en-US\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2025\\\/09\\\/02\\\/what-is-the-cpp-nth_element-algorithm\\\/#webpage\"},\"isPartOf\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2025\\\/09\\\/02\\\/what-is-the-cpp-nth_element-algorithm\\\/#webpage\"},\"articleSection\":\"C++, algorithms, C++, nth_element\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2025\\\/09\\\/02\\\/what-is-the-cpp-nth_element-algorithm\\\/#breadcrumblist\",\"itemListElement\":[{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog#listItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"name\":\"IT\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"position\":2,\"name\":\"IT\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"name\":\"Software\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog#listItem\",\"name\":\"Home\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"position\":3,\"name\":\"Software\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"name\":\"C++\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"name\":\"IT\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"position\":4,\"name\":\"C++\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2025\\\/09\\\/02\\\/what-is-the-cpp-nth_element-algorithm\\\/#listItem\",\"name\":\"What is the C++ nth_element algorithm?\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"name\":\"Software\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2025\\\/09\\\/02\\\/what-is-the-cpp-nth_element-algorithm\\\/#listItem\",\"position\":5,\"name\":\"What is the C++ nth_element algorithm?\",\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"name\":\"C++\"}}]},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\",\"name\":\"Marius Bancila's Blog\",\"description\":\"About code. Mostly on C++\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/\",\"name\":\"Marius Bancila\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2025\\\/09\\\/02\\\/what-is-the-cpp-nth_element-algorithm\\\/#authorImage\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a84dd2831d955c38355ddea55df4df260809b88f36408bc14fd4eab8f7f131c9?s=96&d=mm&r=g\",\"width\":96,\"height\":96,\"caption\":\"Marius Bancila\"}},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2025\\\/09\\\/02\\\/what-is-the-cpp-nth_element-algorithm\\\/#webpage\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2025\\\/09\\\/02\\\/what-is-the-cpp-nth_element-algorithm\\\/\",\"name\":\"What is the C++ nth_element algorithm?\",\"inLanguage\":\"en-US\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#website\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2025\\\/09\\\/02\\\/what-is-the-cpp-nth_element-algorithm\\\/#breadcrumblist\"},\"author\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"creator\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"datePublished\":\"2025-09-02T22:26:30+02:00\",\"dateModified\":\"2025-09-02T22:26:32+02:00\"},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\",\"name\":\"Marius Bancila's Blog\",\"description\":\"About code. Mostly on C++\",\"inLanguage\":\"en-US\",\"publisher\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\"}}]}\n\t\t<\/script>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"What is the C++ nth_element algorithm?","description":"","canonical_url":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/","robots":"max-image-preview:large","keywords":"algorithms,c++,nth_element","webmasterTools":{"miscellaneous":""},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/#article","name":"What is the C++ nth_element algorithm?","headline":"What is the C++ nth_element algorithm?","author":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"publisher":{"@id":"https:\/\/mariusbancila.ro\/blog\/#organization"},"datePublished":"2025-09-02T22:26:30+02:00","dateModified":"2025-09-02T22:26:32+02:00","inLanguage":"en-US","mainEntityOfPage":{"@id":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/#webpage"},"isPartOf":{"@id":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/#webpage"},"articleSection":"C++, algorithms, C++, nth_element"},{"@type":"BreadcrumbList","@id":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/#breadcrumblist","itemListElement":[{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog#listItem","position":1,"name":"Home","item":"https:\/\/mariusbancila.ro\/blog","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","name":"IT"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","position":2,"name":"IT","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","name":"Software"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog#listItem","name":"Home"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","position":3,"name":"Software","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","name":"C++"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","name":"IT"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","position":4,"name":"C++","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/#listItem","name":"What is the C++ nth_element algorithm?"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","name":"Software"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/#listItem","position":5,"name":"What is the C++ nth_element algorithm?","previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","name":"C++"}}]},{"@type":"Organization","@id":"https:\/\/mariusbancila.ro\/blog\/#organization","name":"Marius Bancila's Blog","description":"About code. Mostly on C++","url":"https:\/\/mariusbancila.ro\/blog\/"},{"@type":"Person","@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author","url":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/","name":"Marius Bancila","image":{"@type":"ImageObject","@id":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/#authorImage","url":"https:\/\/secure.gravatar.com\/avatar\/a84dd2831d955c38355ddea55df4df260809b88f36408bc14fd4eab8f7f131c9?s=96&d=mm&r=g","width":96,"height":96,"caption":"Marius Bancila"}},{"@type":"WebPage","@id":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/#webpage","url":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/","name":"What is the C++ nth_element algorithm?","inLanguage":"en-US","isPartOf":{"@id":"https:\/\/mariusbancila.ro\/blog\/#website"},"breadcrumb":{"@id":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/#breadcrumblist"},"author":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"creator":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"datePublished":"2025-09-02T22:26:30+02:00","dateModified":"2025-09-02T22:26:32+02:00"},{"@type":"WebSite","@id":"https:\/\/mariusbancila.ro\/blog\/#website","url":"https:\/\/mariusbancila.ro\/blog\/","name":"Marius Bancila's Blog","description":"About code. Mostly on C++","inLanguage":"en-US","publisher":{"@id":"https:\/\/mariusbancila.ro\/blog\/#organization"}}]},"og:locale":"en_US","og:site_name":"Marius Bancila's Blog | About code. Mostly on C++","og:type":"article","og:title":"What is the C++ nth_element algorithm?","og:url":"https:\/\/mariusbancila.ro\/blog\/2025\/09\/02\/what-is-the-cpp-nth_element-algorithm\/","article:published_time":"2025-09-02T20:26:30+00:00","article:modified_time":"2025-09-02T20:26:32+00:00","twitter:card":"summary","twitter:title":"What is the C++ nth_element algorithm?"},"aioseo_meta_data":{"post_id":"4765","title":null,"description":null,"keywords":null,"keyphrases":{"focus":{"keyphrase":"","score":0,"analysis":{"keyphraseInTitle":{"score":0,"maxScore":9,"error":1}}},"additional":[]},"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":"","og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"Article","isEnabled":true},"graphs":[]},"schema_type":"default","schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":"-1","robots_max_videopreview":"-1","robots_max_imagepreview":"large","priority":null,"frequency":"default","location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"ai":null,"created":"2025-08-27 19:33:31","updated":"2025-12-12 07:59:22","seo_analyzer_scan_date":null,"focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"author_meta":{"display_name":"Marius Bancila","author_link":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/"},"featured_img":null,"jetpack_publicize_connections":[],"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false},"uagb_author_info":{"display_name":"Marius Bancila","author_link":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/"},"uagb_comment_info":0,"uagb_excerpt":"The C++ standard library provides an algorithm called nth_element() that is a useful tool for partial sorting. But how does it work and where is it useful? First of all, the algorithm is defined as follows: given a range [first, last) and an nth element within the range, the algorithm partially sorts the range so&hellip;","coauthors":[],"tax_additional":{"categories":{"linked":["<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">C++<\/a>"],"unlinked":["<span class=\"advgb-post-tax-term\">C++<\/span>"]},"tags":{"linked":["<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">algorithms<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">C++<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">nth_element<\/a>"],"unlinked":["<span class=\"advgb-post-tax-term\">algorithms<\/span>","<span class=\"advgb-post-tax-term\">C++<\/span>","<span class=\"advgb-post-tax-term\">nth_element<\/span>"]}},"comment_count":"0","relative_dates":{"created":"Posted 1 year ago","modified":"Updated 1 year ago"},"absolute_dates":{"created":"Posted on September 2, 2025","modified":"Updated on September 2, 2025"},"absolute_dates_time":{"created":"Posted on September 2, 2025 10:26 pm","modified":"Updated on September 2, 2025 10:26 pm"},"featured_img_caption":"","series_order":"","jetpack_shortlink":"https:\/\/wp.me\/pYNdv-1eR","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/4765","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/comments?post=4765"}],"version-history":[{"count":9,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/4765\/revisions"}],"predecessor-version":[{"id":4774,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/4765\/revisions\/4774"}],"wp:attachment":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/media?parent=4765"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/categories?post=4765"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/tags?post=4765"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}