{"id":11470,"date":"2026-02-02T23:10:16","date_gmt":"2026-02-02T17:40:16","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=11470"},"modified":"2026-02-06T22:26:10","modified_gmt":"2026-02-06T16:56:10","slug":"quick-sort","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/quick-sort\/","title":{"rendered":"Quick Sort"},"content":{"rendered":"\n<!-- PrismJS for Syntax Highlighting -->\n<link\n    href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\"\n    rel=\"stylesheet\"\n\/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\">\n            <button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n\n<h1 class=\"wp_blog_main-heading\"><\/h1>\n\n<div class=\"wp_blog_explanation\">\n    <h2>Quick Sort (Divide and Conquer)<\/h2>\n    <ul>\n        <li>[8, 3, 1, 7, 0, 10, 2]<\/li>\n        <li>[1, 0, 2, 7, 3, 10, 8]<\/li>\n        <p>Now, Choose <code>8<\/code> as pivot:<\/p>\n        <li>[0, 1, 2, 7, 3, 8, 10]<\/li>\n        <p>Now Choose <code>3<\/code> as pivot<\/p>\n        <li>[0, 1, 2, 3, 7, 8, 10]: SORTED ARRAY<\/li>\n    <\/ul>\n    <p><strong>\n        We can choose any element as the pivot, but for simplicity, we select the last element since it makes the algorithm easier to implement.\n    <\/strong><\/p>\n    <h2>Algorithm Steps<\/h2>\n    <ul>\n        <li><strong>Choose a pivot element<\/strong>\n            <code>\n                Select one element from the array (commonly first, last, middle, or random).\n            <\/code>\n        <\/li>\n\n        <li><strong>Partition the array<\/strong>\n            Rearrange elements so that:\n            <code>\n                Elements smaller than the pivot go to the left.\n            <\/code>\n        <\/br>\n            <code>\n                Elements greater than the pivot go to the right.\n            <\/code>\n        <\/li>\n\n        <li><strong>Place the pivot in its correct position<\/strong>\n        <code>\n            After partitioning, the pivot is in its final sorted place.\n        <\/code>\n        <\/li>\n\n        <li><strong>Recursively apply Quick Sort<\/strong>\n            <code>Apply Quick Sort to the left sub-array.<\/code>\n        <br\/>\n            <code>Apply Quick Sort to the right sub-array.<\/code>\n        <\/li>\n\n        <li><strong>Stop condition (Base Case)<\/strong>\n        <code>\n            If the sub-array has 0 or 1 element, it is already sorted.\n        <\/code>\n        <\/li>\n    <\/ul>\n\n        <h2>Time Complexity:<\/h2>\n        <ul>\n            <li><strong>Best Case: <\/strong><code>O(n log n)<\/code><\/li>\n            <li><strong>Average Case: <\/strong><code>O(n log n)<\/code><\/li>\n            <li><strong>Worst Case: <\/strong><code>O(n<sup>2<\/sup>)<\/code>\n            <i>Already sorted + Bad Pivot (choose)<\/i>\n            <\/li>\n        <\/ul>     \n            \n        <h2>Space Complexity:<\/h2>\n        <ul>\n            <li>O(log n)<\/li>\n            <li>Only <code>Recursion<\/code> stack takes a space.<\/li>\n            <li><strong>Very efficient with space Complexity.<\/strong><\/li>\n        <\/ul>\n             \n        <h2>Importance of Quick Sort<\/h2>\n        <ul>\n            <li>No extra <code>memory allocation<\/code>.<\/li>\n            <li>Cache friendly.<\/li>\n            <li><code>Partitioning<\/code> is efficient. <strong>(log n)<\/strong><\/li>\n            <li>Randomize pivots avoid worst case.<\/li>\n            <li>Most standard <code>libraries<\/code> still rely on <strong>Quick Sort<\/strong> and variant.<\/li>\n        <\/ul>\n<h2>Dry Run<\/h2>\n\n<div style=\"background: var(--light-bg); border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0; color: var(--text-dark);\">\n\n  <p><strong>Input:<\/strong><\/p>\n\n  <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\">\nArray: [8, 3, 1, 7, 0, 10, 2]\n  <\/pre>\n\n  <p><strong>State Transitions:<\/strong><\/p>\n\n  <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\">\nInitial Array:\n[8, 3, 1, 7, 0, 10, 2]\n\nquickSort(0, 6)\nPivot = 2\n\nAfter partition:\n[1, 0, 2, 7, 3, 10, 8]\nPivot index = 2\n\nquickSort(0, 1)\nPivot = 0\n\nAfter partition:\n[0, 1, 2, 7, 3, 10, 8]\nPivot index = 0\n\nquickSort(3, 6)\nPivot = 8\n\nAfter partition:\n[0, 1, 2, 7, 3, 8, 10]\nPivot index = 5\n\nquickSort(3, 4)\nPivot = 3\n\nAfter partition:\n[0, 1, 2, 3, 7, 8, 10]\nPivot index = 3\n  <\/pre>\n\n  <p><strong>Final State:<\/strong><br>\n    Sorted Array:\n    <code>[0, 1, 2, 3, 7, 8, 10]<\/code>\n  <\/p>\n\n<\/div>\n\n<\/div>\n\n<div class=\"wp_blog_code-tabs-container\">\n    <div class=\"wp_blog_code-tabs-header\">\n        <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">\n            JavaScript\n        <\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n       \n<pre><code class=\"language-javascript\">\nfunction findPivotIndex(arr, startIndex, endIndex) {\n    let pivot = arr[endIndex];\n    let pos = startIndex - 1;\n\n    \/\/ moving all smaller elements to the left\n    for (let i = startIndex; i < endIndex; i++) {\n        if (arr[i] < pivot) {\n            pos++;\n            [arr[i], arr[pos]] = [arr[pos], arr[i]];\n        }\n    }\n\n    \/\/ moving pivot to correct position\n    [arr[pos + 1], arr[endIndex]] = [arr[endIndex], arr[pos + 1]];\n    return pos + 1;\n}\n\nfunction quickSort(arr, startIndex, endIndex) {\n    if (startIndex < endIndex) {\n        let pivotIndex = findPivotIndex(arr, startIndex, endIndex);\n\n        \/\/ calling quickSort for left part\n        quickSort(arr, startIndex, pivotIndex - 1);\n\n        \/\/ calling quickSort for right part\n        quickSort(arr, pivotIndex + 1, endIndex);\n\n        return arr;\n    }\n}\n\nlet nums = [8, 3, 1, 7, 0, 10, 2];\nlet startIndex = 0;\nlet endIndex = nums.length - 1;\n\nconsole.log(quickSort(nums, startIndex, endIndex));\n<\/code><\/pre>\n\n<\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n        <pre><code class=\"language-python\">\ndef findPivotIndex(arr, startIndex, endIndex):\n    pivot = arr[endIndex]\n    pos = startIndex - 1\n\n    for i in range(startIndex, endIndex):\n        if arr[i] < pivot:\n            pos += 1\n            arr[i], arr[pos] = arr[pos], arr[i]\n\n    arr[pos + 1], arr[endIndex] = arr[endIndex], arr[pos + 1]\n    return pos + 1\n\n\ndef quickSort(arr, startIndex, endIndex):\n    if startIndex < endIndex:\n        pivotIndex = findPivotIndex(arr, startIndex, endIndex)\n        quickSort(arr, startIndex, pivotIndex - 1)\n        quickSort(arr, pivotIndex + 1, endIndex)\n        return arr\n\n\nnums = [8, 3, 1, 7, 0, 10, 2]\nprint(quickSort(nums, 0, len(nums) - 1))\n\n    <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n        <pre><code class=\"language-java\">\npublic class QuickSortExample {\n\n    static int findPivotIndex(int[] arr, int startIndex, int endIndex) {\n        int pivot = arr[endIndex];\n        int pos = startIndex - 1;\n\n        for (int i = startIndex; i < endIndex; i++) {\n            if (arr[i] < pivot) {\n                pos++;\n                int temp = arr[i];\n                arr[i] = arr[pos];\n                arr[pos] = temp;\n            }\n        }\n\n        int temp = arr[pos + 1];\n        arr[pos + 1] = arr[endIndex];\n        arr[endIndex] = temp;\n\n        return pos + 1;\n    }\n\n    static void quickSort(int[] arr, int startIndex, int endIndex) {\n        if (startIndex < endIndex) {\n            int pivotIndex = findPivotIndex(arr, startIndex, endIndex);\n            quickSort(arr, startIndex, pivotIndex - 1);\n            quickSort(arr, pivotIndex + 1, endIndex);\n        }\n    }\n\n    public static void main(String[] args) {\n        int[] nums = {8, 3, 1, 7, 0, 10, 2};\n        quickSort(nums, 0, nums.length - 1);\n\n        for (int num : nums) {\n            System.out.print(num + \" \");\n        }\n    }\n}\n\n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n        <pre><code class=\"language-cpp\">\n#include &lt;iostream&gt;\n\nusing namespace std;\n\nint findPivotIndex(int arr[], int startIndex, int endIndex) {\n    int pivot = arr[endIndex];\n    int pos = startIndex - 1;\n\n    for (int i = startIndex; i < endIndex; i++) {\n        if (arr[i] < pivot) {\n            pos++;\n            swap(arr[i], arr[pos]);\n        }\n    }\n\n    swap(arr[pos + 1], arr[endIndex]);\n    return pos + 1;\n}\n\nvoid quickSort(int arr[], int startIndex, int endIndex) {\n    if (startIndex < endIndex) {\n        int pivotIndex = findPivotIndex(arr, startIndex, endIndex);\n        quickSort(arr, startIndex, pivotIndex - 1);\n        quickSort(arr, pivotIndex + 1, endIndex);\n    }\n}\n\nint main() {\n    int nums[] = {8, 3, 1, 7, 0, 10, 2};\n    int n = sizeof(nums) \/ sizeof(nums[0]);\n\n    quickSort(nums, 0, n - 1);\n\n    for (int i = 0; i < n; i++) {\n        cout << nums[i] << \" \";\n    }\n    return 0;\n}\n    <\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n        <pre><code class=\"language-c\">\n#include &lt;stdio.h&gt;\n\nint findPivotIndex(int arr[], int startIndex, int endIndex) {\n    int pivot = arr[endIndex];\n    int pos = startIndex - 1;\n\n    for (int i = startIndex; i < endIndex; i++) {\n        if (arr[i] < pivot) {\n            pos++;\n            int temp = arr[i];\n            arr[i] = arr[pos];\n            arr[pos] = temp;\n        }\n    }\n\n    int temp = arr[pos + 1];\n    arr[pos + 1] = arr[endIndex];\n    arr[endIndex] = temp;\n\n    return pos + 1;\n}\n\nvoid quickSort(int arr[], int startIndex, int endIndex) {\n    if (startIndex < endIndex) {\n        int pivotIndex = findPivotIndex(arr, startIndex, endIndex);\n        quickSort(arr, startIndex, pivotIndex - 1);\n        quickSort(arr, pivotIndex + 1, endIndex);\n    }\n}\n\nint main() {\n    int nums[] = {8, 3, 1, 7, 0, 10, 2};\n    int n = sizeof(nums) \/ sizeof(nums[0]);\n\n    quickSort(nums, 0, n - 1);\n\n    for (int i = 0; i < n; i++) {\n        printf(\"%d \", nums[i]);\n    }\n    return 0;\n}\n    <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n        <pre><code class=\"language-csharp\">\nusing System;\n\nclass Program {\n    static int FindPivotIndex(int[] arr, int startIndex, int endIndex) {\n        int pivot = arr[endIndex];\n        int pos = startIndex - 1;\n\n        for (int i = startIndex; i < endIndex; i++) {\n            if (arr[i] < pivot) {\n                pos++;\n                int temp = arr[i];\n                arr[i] = arr[pos];\n                arr[pos] = temp;\n            }\n        }\n\n        int temp2 = arr[pos + 1];\n        arr[pos + 1] = arr[endIndex];\n        arr[endIndex] = temp2;\n\n        return pos + 1;\n    }\n\n    static void QuickSort(int[] arr, int startIndex, int endIndex) {\n        if (startIndex < endIndex) {\n            int pivotIndex = FindPivotIndex(arr, startIndex, endIndex);\n            QuickSort(arr, startIndex, pivotIndex - 1);\n            QuickSort(arr, pivotIndex + 1, endIndex);\n        }\n    }\n\n    static void Main() {\n        int[] nums = { 8, 3, 1, 7, 0, 10, 2 };\n        QuickSort(nums, 0, nums.Length - 1);\n\n        Console.WriteLine(string.Join(\" \", nums));\n    }\n}\n  <\/code><\/pre>\n    <\/div>\n<\/div>\n<\/div>\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Quick Sort (Divide and Conquer) [8, 3, 1, 7, 0, 10, 2] [1, 0, 2, 7, 3, 10, 8] Now, Choose 8 as pivot: [0, 1, 2, 7, 3, 8, 10] Now Choose 3 as pivot [0, 1, 2, 3, 7, 8, 10]: SORTED ARRAY We can choose any element as the pivot, but<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[210,322,260,176,175,211,811,810,174,172,173],"tags":[],"class_list":["post-11470","post","type-post","status-publish","format-standard","category-algorithms","category-algorithms-and-data-structures","category-c-c-plus-plus","category-csharp","category-cplusplus","category-data-structures","category-data-structures-and-algorithms","category-dsa","category-java","category-javascript","category-python"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/11470","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=11470"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/11470\/revisions"}],"predecessor-version":[{"id":11471,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/11470\/revisions\/11471"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=11470"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=11470"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=11470"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}