Implement this insertion sort algorithm in any programming language of your choice. Show case your talent here.
The insersion sort algorithm rearrages an unordered array in either ascending or descending order . For the problem, ascending order is preferred. Let say we have a sequence of numbers. A={2, 6,,3, 5, 8, 4, 5, 0} what the algorithm does is to rearrange it well like A={0, 2, 3, 4, 5, 5, 8}

A sequence of n numbers A = { a1, a2.... an} and a value
v
Implement a linear search algorithm in any programming langauage of choice to search for an index i such that A[i]=v

Where are the algorithm guys, this should be bread and butter, test you algorithmic skill

Understanding a problem is the first principle of algorithm, we cannot solve the problem if we dont understand what we are solving, you should explain waht d algorithm does better, wheter it is a needle in haystack algorithm (used to iterate a loop for a match) or something else, explain better maybe i can give it a try

Linear search is very inefficient for large data sets as algorithmically speaking it is O(n). Whereas a binary search (which requires a data set to be pre-sorted is O(log base 2 n). Thus a much more efficient and quicker algorithm for searching. For sorting however, selection sort is quite slow merge sort, quick sort, etc are much faster and efficient.

Even for a large data set, insertion sort is a much more powerful algorithm than selection sort, but still slow in comparison to other sorts

public class insertion_sort{

static int[] test;

public static void main(String[] args){
test = new int[] {10,22,21,23,2,1} ;

print_a(test) ;

sort(test) ;

print_a(test) ;

}

private static void print_a(int[] a){

for(int i : a){

System.out.print(i + " " ) ;
}

System.out.println() ;
}


private static void sort(int[] arr) {

//loop through the array
for (int i = 1; i < arr.length; i++) {

//get the current element
int current = arr[i];
int j = i;

//compare this element with every element before it
//if you meet an element smaller than it;
//create space there in preparation to insert it there.
//do not insert immediately though. keep moving down till this current element is greater than the ones before it
//after which you now place the element in the last space created...
while (j > 0 && arr[j - 1] > current) {
//this(j-1) element is greater than our current element and yet is located before it
//copy this(j-1) element to the element after it; thereby making this element eligible for replacement
arr[j] = arr[j - 1];
j--;
}

//place this element where it belongs in the array and move on to repeat this process on the element after it
arr[j] = current;
}
}

}

larisoft:
public class insertion_sort{

static int[] test;

public static void main(String[] args){
test = new int[] {10,22,21,23,2,1} ;

print_a(test) ;

sort(test) ;

print_a(test) ;

}

private static void print_a(int[] a){

for(int i : a){

System.out.print(i + " " ) ;
}

System.out.println() ;
}


private static void sort(int[] arr) {

//loop through the array
for (int i = 1; i < arr.length; i++) {

//get the current element
int current = arr[i];
int j = i;

//compare this element with every element before it
//if you meet an element smaller than it;
//create space there in preparation to insert it there.
//do not insert immediately though. keep moving down till this current element is greater than the ones before it
//after which you now place the element in the last space created...
while (j > 0 && arr[j - 1] > current) {
//this(j-1) element is greater than our current element and yet is located before it
//copy this(j-1) element to the element after it; thereby making this element eligible for replacement
arr[j] = arr[j - 1];
j--;
}

//place this element where it belongs in the array and move on to repeat this process on the element after it
arr[j] = current;
}
}

}

thats the implementation of a insertion_sort algorithm.

for the linear search

public int search(arr[], int v){

//loop through array
for(int i =0; i< arr.length; i++){


if(arr[i] == v) return i;
}

return -1;
}

larisoft:
public class insertion_sort{

static int[] test;

public static void main(String[] args){
test = new int[] {10,22,21,23,2,1} ;

print_a(test) ;

sort(test) ;

print_a(test) ;

}

private static void print_a(int[] a){

for(int i : a){

System.out.print(i + " " ) ;
}

System.out.println() ;
}


private static void sort(int[] arr) {

//loop through the array
for (int i = 1; i < arr.length; i++) {

//get the current element
int current = arr[i];
int j = i;

//compare this element with every element before it
//if you meet an element smaller than it;
//create space there in preparation to insert it there.
//do not insert immediately though. keep moving down till this current element is greater than the ones before it
//after which you now place the element in the last space created...
while (j > 0 && arr[j - 1] > current) {
//this(j-1) element is greater than our current element and yet is located before it
//copy this(j-1) element to the element after it; thereby making this element eligible for replacement
arr[j] = arr[j - 1];
j--;
}

//place this element where it belongs in the array and move on to repeat this process on the element after it
arr[j] = current;
}
}

}

thats the implementation of an insertion_sort algorithm.

for the linear search

public int search(arr[], int v){

//loop through array
for(int i =0; i< arr.length; i++){

//if this element is equal to the value we are searching for, stop search here and return the index
if(arr[i] == v) return i;
}

//if we got here, this value does not exist in this array. return -1
return -1;
}

Didnt test it but I suppose it will work.

@larisoft, in Java an insertion sort would resemble something like this (swap method not implemented here, but this is written to give you an idea)

public class InsertionSort {
	public static void theInsertionSort (int[] values) {
		int currentIndex;
		for (int pos = 1; pos < values.length; pos++) {
			currentIndex = pos;
			while (currentIndex > 0 && values[currentIndex] < values[currentIndex - 1]) {
				//perform a swap method/function here in the values array to switch value in
				//current index with value in the index before it
				//swap(values, currentIndex, currentIndex - 1);
				currentIndex = currentIndex - 1;
			}
		}
	}
}

.SPACEBOOKED

crotonite:
.SPACEBOOKED

What is spacebooked sir? Does that mean bookmarked?

Fulaman198:

What is spacebooked sir? Does that mean bookmarked?

Yea. it simply means i will be back .

BTW, are you on a night shift?

crotonite:

Yea. it simply means i will be back .


BTW, are you on a night shift?

LOL no, I'm just someone who works ridiculous hours on and off the clock (personal projects/tutorials + work). I will soon go to sleep. It's just that it is Ramadan and I ate late so I have to digest the food.

Fulaman198:
@larisoft, in Java an insertion sort would resemble something like this (swap method not implemented here, but this is written to give you an idea)

public class InsertionSort {
	public static void theInsertionSort (int[] values) {
		int currentIndex;
		for (int pos = 1; pos < values.length; pos++) {
			currentIndex = pos;
			while (currentIndex > 0 && values[currentIndex] < values[currentIndex - 1]) {
				//perform a swap method/function here in the values array to switch value in
				//current index with value in the index before it
				//swap(values, currentIndex, currentIndex - 1);
				currentIndex = currentIndex - 1;
			}
		}
	}
}

that , my dear, is an insertion sort. The swap happens there where j becomes j-1.

if your still certain that it isn't, I ll be glad to know why.

Fulaman198:


LOL no, I'm just someone who works ridiculous hours on and off the clock (personal projects/tutorials + work). I will soon go to sleep. It's just that it is Ramadan and I ate late so I have to digest the food.

very funny.

larisoft:


thats the implementation of a insertion_sort algorithm.

for the linear search

public int search(arr[], int v){

//loop through array
for(int i =0; i< arr.length; i++){


if(arr[i] == v) return i;
}

return -1;
}

This is not an effective way of implementing linear search on an ordered array , because even if the element been searched for is in the first array index , the algorith woukd still search through all the array before returning the result, it would waste resources.. Can you make it such that the loop stops as soon as the element is found?? That woukd be more efficient

Laolballs:

This is not an effective way of implementing linear search on an ordered array , because even if the element been searched for is in the first array index , the algorith woukd still search through all the array before returning the result, it would waste resources.. Can you make it such that the loop stops as soon as the element is found?? That woukd be more efficient

kindly read the code very well, dear. see the part where I wrote

if(arr[i] == v ) return i;


With the level of experience you guys seem to be showing about algorithms; I'm starting to regret answering the questions in the first place. I hope I dont sound rude; but its just the way I feel sha.

larisoft:


kindly read the code very well, dear. see the part where I wrote

if(arr[i] == v ) return i;


With the level of experience you guys seem to be showing about algorithms; I'm starting to regret answering the questions in the first place. I hope I dont sound rude; but its just the way I feel sha.

Am not saying your implentation is wrong but
Have you tried running your code ? What the if statement does is to return array index i if its content is equivalent to the value v . it does not stop the loop from running through the remining array list.

Laolballs:

Am not saying your implentation is wrong but
Have you tried running your code ? What the if statement does is to return array index i if its content is equivalent to the value v . it does not stop the loop from running through the remining array list.

I understood your confusion. That was why I said what I said about your level of experience.

In java, and just about every other oop langauge, the return statement in a method terminates that method, including any loop that might have been executing within the method.

The only exception I know of is when there is a try, finally clause.

I was angry because you could have asked questions or used google; rather than speak authoritatively as though you know what you are saying.

Badoo don dey vex oo.

@laoballs, you are just yanning rubbish by the way. Every method terminates once it encounters the return statement. Except your compiler dey special, that method up there will terminate the moment it sees 'return'.

oga larisoft, Easy ooo. I dey feel you from background since.

ugo2016:
Badoo don dey vex oo.

@laoballs, you are just yanning rubbish by the way. Every method terminates once it encounters the return statement. Except your compiler dey special, that method up there will terminate the moment it sees 'return'.

oga larisoft, Easy ooo. I dey feel you from background since.

Thanks my brother.

larisoft:


Thanks my brother.

@larrisoft , y u dey vex, you dont need it, just want to be sure you know what you are saying , it just some confirmation tease. Yu think sey me wey post sometin no sabi d answer?huh...na joke i dey ooh..no vex

Laolballs:


@larrisoft , y u dey vex, you dont need it, just want to be sure you know what you are saying , it just some confirmation tease. Yu think sey me wey post sometin no sabi d answer?huh...na joke i dey ooh..no vex

its alright, bro.