5.1 Sorting Algorithms: Insertion Sort

Insertion Sort Using a for loop Mini Project Next Section

Insertion Sort

Insert the first element, and then compare the others to it accordingly. Then, insert new elements until the array is sorted.

Using a for loop

There are many ways to conduct an insertion sort. In the following example, we will walk through the “for loop method”. This method utilizes a for loop to insert an element, and then compare them to one another.


int main(){

	int a[] = {6, 5, 4, 3, 2, 1};
	//get the size of the array
	int length = sizeof(a) / sizeof(a[0]);

}
void sort(int a[], int length){
//code here
}

Above, we declare the sort method and accept a given array and the size of it as parameters. The length variable determines the maximum bounds of the sort.


int main(){

	int a[] = {6, 5, 4, 3, 2, 1};
	//get the size of the array
	int length = sizeof(a) / sizeof(a[0]);

}
void sort(int a[], int length){
//intializing variables
	int i, temp, j;
//assigns values to temp and j
	for (i = 1; i < length; i++){
		temp = a[i];
		j = i - 1;
//moves elements greater than j forward by one index
		while (j >= 0 && a[j] > temp){
	     a[j + 1] = a[j];
	     j = j - 1;
	   }
		   a[j + 1] = temp;
    }
}

Now, we have initialized the three variables that we will need in this sort: i, j, and temp. i is the variable iterated in our for loop, while j represents the new index of the elements after they are moved. The temp variable is where the new element being inserted is declared.

The actual bulk of the sort lies in the while loop. The while loop takes the newly assigned temp variable and the j variable, and checks whether or not the element before a[i] (represented by a[j]) is greater than a[i]. If it is, it is assigned to a[i]. After this sort is complete, simply print out the array, and it will be arranged from least to greatest.

Mini Project

Create an insertion sort to sort the contents of a given array, and then print it.

Array: {1, 2, 3, 4, 5}

Solution Code


int main(){

	int a[] = {1, 2, 3, 4, 5};
	//get the size of the array
	int length = sizeof(a) / sizeof(a[0]);

}
void sort(int a[], int length){
//intializing variables
	int i, temp, j;
//assigns values to temp and j
	for (i = 1; i < length; i++){
		temp = a[i];
		j = i - 1;
//moves elements greater than j forward by one index
		while (j >= 0 && a[j] > temp){
	     a[j + 1] = a[j];
	     j = j - 1;
	   }
		   a[j + 1] = temp;
    }
//print the array
	for (i = 0; i < n; i++) 
    {
        printf("%d\n", arr[i]);
    }
}

Next Section

2️⃣

5.2 Searching

⚖️

Copyright © 2021 Code 4 Tomorrow. All rights reserved. The code in this course is licensed under the MIT License. If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.