c++ code for insertion sort
Certainly! Here's a C++ code example for insertion sort, along with explanations for each step:
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "Sorted array: \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
Explanation for each step:
- The
insertionSort
function takes an arrayarr
and its sizen
as parameters. - Inside the function, we declare variables
i
,key
, andj
.i
is used as a loop counter,key
is used to store the current element being sorted, andj
is used to compare and shift elements. - The outer
for
loop starts from the second element (i = 1
) and iterates up to the last element (i < n
). - Inside the loop, we assign
arr[i]
tokey
andi - 1
toj
. - The inner
while
loop checks ifj
is greater than or equal to 0 and if the element atarr[j]
is greater thankey
. - If the condition is true, we shift the element at
arr[j]
one position ahead (arr[j + 1] = arr[j]
) and decrementj
. - We repeat the while loop until
j
becomes less than 0 or the element atarr[j]
is not greater thankey
. - Finally, we assign
key
toarr[j + 1]
to place thekey
element in its correct sorted position. - The main function initializes an array
arr
with values and calculates the sizen
of the array. - It calls the
insertionSort
function passing the array and its size. - After sorting, it prints the sorted array using a
for
loop. - The program then ends by returning 0.
I hope this code example and explanation are helpful! Let me know if you need further assistance.