Leveraging ChatGPT - GenAI as a Microsoft Data Expert

Speaker

Prerita Agarwal

Data Specialist @

23 Jul, 2024 @ 01:30 PM

Introduction

Insertion sort is a sorting algorithm in which an array is split into two parts, one sorted and another unsorted, at every iteration; an unsorted value is taken and placed at its suitable position within the sorted part of the array.

Itâ€™s a lot like how one sorts playing cards.

In this article, we will look at how to write the code for insertion sort in the carbon language.

Carbon language is a new programming language developed by google, which is a successor to the C++ language.

Key features of insertion sort

One of the easiest sorting algorithms with a very simple implementation.

It works well for small data values.

It works best for datasets that are initially partially sorted.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Working of Insertion Sort

Letâ€™s take an example to understand the working of insertion sort.

Consider the following array.

In the first pass, compare the first two elements of the array Since 10 is greater than 6 we swap 10 and 6. Now, 6 is in the sorted sub-array.

In the second pass, we move to the following two elements of the modified array. We will compare 10 and 2. Since 10 is greater, we swap 10 and 2.

Now we see that 6 and 2 are also not in ascending order, so we again swap 6 and 2. Again we got our sorted sub-array on the left.

In the third pass, the next two elements 10 and 5 are compared, and as they are not in ascending order, they are swapped.

Now we see that 6 and 5 are also not in the proper order, so we swap 6 and 5 and get the sorted sub-array on the left.

In the Fourth pass, the next two elements are picked, i.e., 10 and 4; as they are not in the correct order, we swap them.

Then we have 6 and 4 which are also not in right order, so we swap again.

Then we get 5 and 4 which is again not in ascending order, so we swap again. And we get the array in sorted order because there arenâ€™t any more elements to traverse in the array.

Algorithm

Letâ€™s say the size of the array to be sorted is N.

Traverse the array from the first element to the last (1 to N).

Compare the current element with the predecessor element.

If the current element is smaller than its predecessor, compare it with elements before it and move the greater element to one index ahead to make space for swapped element.

Code for Insertion sort in Carbon

Code

package sample api;
fn Main() -> 132 {
var arr: [i32;9] = (2, -10, 7, -7, -3, 8, -2, 12, 5);
var idx: i32 = 1;
var pred: i32; var key: i32;
while(idx < 9) {
key = arr[idx];
pred = idx-1;
while (pred>=0 and arr[pred]>key) {
arr[pred+1] = arr[pred];
pred = pred-1;
}
arr [pred+1] = key;
idx = idx+1;
}
var i: i32 = 0;
Print("Sorted array after performing insertion sort :");
while(i < 9) {
Print("{0}", arr[i]);
i=i+1;
}
return 0;
}

Output

sorted array after performing insertion sort :
-10,-7,-3,-2,2,5,7,8,12

Frequently Asked Questions

What is the purpose of the Carbon language?

Carbon is a general-purpose programming language that is still under development. As of now, it is intended to be a successor to C++. It will be used along with C++ in game development and GUI.

Who developed carbon language?

Carbon language is an open-source project started by Google.

What is the time complexity of insertion sort?

the time complexity for the insertion sort algorithm is O(N^2).