Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Easy

Insertion Sort In Carbon

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

 

Insertion Sort in Carbon

 

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.

 

         {10,6,2,5,4}

 

  • 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.

 

{6,10,2,5,4}

 

  • 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.

 

{6,2,10,5,4}

 

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.

 

{2,6,10,5,4}

 

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

         

         {2,6,5,10,4}

 

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.

 

{2,5,6,10,4}

 

  • 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.

 

{2,5,6,4,10}

 

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

 

{2,5,4,6,10}

 

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.

 

{2,4,5,6,10} 

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).


Check out this problem - Maximum Product Subarray 

Conclusion 

In this article, we looked into what is carbon language, and insertion sort and learned how to write insertion sort code in the new carbon language.

 

Recommended reading

Also, check out some of the Guided PathsContests, and Interview Experiences to gain an edge only on Coding Ninjas Studio.

 

    

                          

Thank you

 

Topics covered
1.
Introduction
2.
Key features of insertion sort
3.
Working of Insertion Sort
4.
Algorithm
5.
Code for Insertion sort in Carbon
5.1.
Code
5.2.
Output
6.
Frequently Asked Questions
6.1.
What is the purpose of the Carbon language?
6.2.
Who developed carbon language?
6.3.
What is the time complexity of insertion sort?
7.
Conclusion