Stats: 3,191,748 members, 7,945,331 topics. Date: Tuesday, 10 September 2024 at 02:45 PM |
Nairaland Forum / Science/Technology / Programming / Simple Algorithm Implementation (2274 Views)
Simple Algorithm Exercise / Simple Algorithm Challenge / Pls Programmers Help With Similarities Of Pseudocode & Algorithm (2) (3) (4)
Simple Algorithm Implementation by Laolballs: 7:16am On Jun 07, 2016 |
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}
|
Re: Simple Algorithm Implementation by Laolballs: 7:24am On Jun 07, 2016 |
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 |
Re: Simple Algorithm Implementation by teampregar(m): 10:15am On Jun 07, 2016 |
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 |
Re: Simple Algorithm Implementation by Fulaman198(m): 5:28pm On Jun 07, 2016 |
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. 1 Like |
Re: Simple Algorithm Implementation by Fulaman198(m): 8:55pm On Jun 07, 2016 |
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 |
Re: Simple Algorithm Implementation by larisoft: 9:54pm On Jun 07, 2016 |
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; } } } |
Re: Simple Algorithm Implementation by larisoft: 9:59pm On Jun 07, 2016 |
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; } |
Re: Simple Algorithm Implementation by larisoft: 10:00pm On Jun 07, 2016 |
larisoft: 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. |
Re: Simple Algorithm Implementation by Fulaman198(m): 11:58pm On Jun 07, 2016 |
@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)
|
Re: Simple Algorithm Implementation by Nobody: 12:14am On Jun 08, 2016 |
.SPACEBOOKED |
Re: Simple Algorithm Implementation by Fulaman198(m): 12:23am On Jun 08, 2016 |
crotonite: What is spacebooked sir? Does that mean bookmarked? |
Re: Simple Algorithm Implementation by Nobody: 1:14am On Jun 08, 2016 |
Fulaman198:Yea. it simply means i will be back ![]() BTW, are you on a night shift? 1 Like |
Re: Simple Algorithm Implementation by Fulaman198(m): 1:18am On Jun 08, 2016 |
crotonite: LOL no, I'm just someone who works ridiculous hours on and off the clock ![]() |
Re: Simple Algorithm Implementation by larisoft: 2:41am On Jun 08, 2016 |
Fulaman198: 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. |
Re: Simple Algorithm Implementation by Nobody: 6:24am On Jun 08, 2016 |
Fulaman198: very funny. ![]() |
Re: Simple Algorithm Implementation by Laolballs: 8:43am On Jun 08, 2016 |
larisoft: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 |
Re: Simple Algorithm Implementation by larisoft: 10:40am On Jun 08, 2016 |
Laolballs: 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. |
Re: Simple Algorithm Implementation by Laolballs: 11:40am On Jun 08, 2016 |
larisoft: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. |
Re: Simple Algorithm Implementation by larisoft: 12:57pm On Jun 08, 2016 |
Laolballs: 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. |
Re: Simple Algorithm Implementation by ugo2016: 1:02pm On Jun 08, 2016 |
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. |
Re: Simple Algorithm Implementation by larisoft: 1:10pm On Jun 08, 2016 |
ugo2016: Thanks my brother. |
Re: Simple Algorithm Implementation by Laolballs: 6:21pm On Jun 09, 2016 |
larisoft: @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 |
Re: Simple Algorithm Implementation by larisoft: 4:57am On Jun 10, 2016 |
Laolballs: its alright, bro. |
(1) (Reply)
My Experience Using An AMD Based System / Please Help On This Topic 2 Pass Assembler / Programming Challenge.
(Go Up)
Sections: politics (1) business autos (1) jobs (1) career education (1) romance computers phones travel sports fashion health religion celebs tv-movies music-radio literature webmasters programming techmarket Links: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Nairaland - Copyright © 2005 - 2024 Oluwaseun Osewa. All rights reserved. See How To Advertise. 56 |