{"id":34210,"date":"2024-11-01T09:25:33","date_gmt":"2024-11-01T09:25:33","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34210"},"modified":"2024-11-01T10:58:10","modified_gmt":"2024-11-01T10:58:10","slug":"c-coding-test-course-insertion-sort-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34210\/","title":{"rendered":"C++ Coding Test Course, Insertion Sort"},"content":{"rendered":"
\n

Hello! In this post, I will discuss Insertion Sort<\/strong>, which is one of the algorithms frequently asked in coding tests using C++. Insertion Sort is a very intuitive sorting algorithm that works by inserting new data into a sorted array. So, shall we get started?<\/p>\n

Problem Description<\/h2>\n

You have an array containing given integers. Output the result of sorting this array in ascending order using Insertion Sort.<\/p>\n

Input Format<\/h2>\n

The first line contains the size of the array N. (1 \u2264 N \u2264 1000)<\/p>\n

The second line contains N integers separated by spaces. (Each integer is -1000 \u2264 x \u2264 1000)<\/p>\n

Output Format<\/h2>\n

Output the sorted array in one line. Each element is separated by a space.<\/p>\n

Example<\/h2>\n
\n        Input:<\/strong>\n        5\n        3 2 1 5 4\n  \n        Output:<\/strong>\n        1 2 3 4 5\n    <\/pre>\n
Algorithm Explanation<\/h2>\n
Insertion Sort works by inserting new values into a sorted array. The algorithm proceeds in the following steps:<\/p>\n
    \n
  1. The first element is considered to be sorted.<\/li>\n
  2. Starting from the second element, find the position to insert it in the sorted array.<\/li>\n
  3. Shift the elements of the array to the right one step to find the position for the new element.<\/li>\n
  4. When the correct position is found, insert the new element.<\/li>\n
  5. Repeat this process for all elements in the array.<\/li>\n<\/ol>\n
    C++ Code Implementation<\/h2>\n
    Now let’s implement the above algorithm in C++. The code is as follows:<\/p>\n
    \n        \n        #include <iostream>\n        #include <vector>\n\n        using namespace std;\n\n        void insertionSort(vector<int>& arr) {\n            int n = arr.size();\n            for (int i = 1; i < n; i++) {\n                int key = arr[i];\n                int j = i - 1;\n\n                \/\/ Move elements greater than key one position ahead\n                while (j >= 0 && arr[j] > key) {\n                    arr[j + 1] = arr[j];\n                    j--;\n                }\n                arr[j + 1] = key; \/\/ Insert the key at the correct position\n            }\n        }\n\n        int main() {\n            int N;\n            cin >> N;\n            vector<int> arr(N);\n\n            for (int i = 0; i < N; i++) {\n                cin >> arr[i];\n            }\n\n            insertionSort(arr);\n\n            for (int i = 0; i < N; i++) {\n                cout << arr[i];\n                if (i < N - 1) cout << \" \"; \/\/ To avoid adding a space after the last element\n            }\n\n            return 0;\n        }\n        <\/code>\n    <\/pre>\n
    Code Explanation<\/h2>\n
    The above code is an implementation of the Insertion Sort algorithm in C++. Let’s take a look at the main parts:<\/p>\n