Posts Tagged ‘Algorithms’
Binary search in string array
Written by Codes Tips on May 10, 2009 – 2:04 pm -To search an string into an array of string you can iterate through all the strings one by one and test which is the string that we wanna search. Doing this you will have a complexity of O(n), where n is the number of the strings that array have.
To do search more efficient you should use binary search which have a complexity of O(log2(n)). To use the binary search method in an array of string we assume that we have a sorted array. To sort an array of string efficiently you can use for example Quicksort algorithm , that was previously described, to obtain a good complexity. Of course, you should use binary search algorithm when you are doing something complex that have a complexity bigger or equal to O(n^2).
So to search a string in an array the algorithm selects the middle element of the array and verify if it is equal to our string. If it is equal it stops, if not it sees if the string is bigger then our string and if it is, it searches in the right part of the array string, if not in left part, applying the same algorithm. So it uses a recursive function to search the string in the array.
We will use the following type of string and declare a variable:
type arraystrings=array[1..1000000] of string; var words:arraystrings;
Here is the binary search algorithm:
function BinSearch(word:string;l:integer;h:integer):integer; begin while (StrIComp(pchar(word),pchar(words[(l+h)div 2]))<>0)and(l<>h) do begin if strIcomp(pchar(word),pchar(words[(l+h)div 2]))>0 then l:=(l+h)div 2+1 else h:=(l+h)div 2-1; end; if l<>h then BinSearch:=(l+h)div 2 else BinSearch:=0; end;
It returns the position in the array where it was found. If not returns 0.
To call it you can use:
position:=BinSearch(word,1,nrwords);
where word is the string we search for and nrwords it’s the number of strings in the array.
Tags: Algorithms, Delphi
Posted in Algorithms, Codes, Delphi | No Comments »
Quicksort array of string
Written by Codes Tips on May 10, 2009 – 1:33 pm -Quicksort it’s an algorithm that it’s very efficient when you wanna sort an array of any type: string, integer, real. I will show you how to sort an array of string, it can be modified easily to sort other types of array.
Quicksort it’s efficient because it’s having a sorting complexity of O(n* log2(n)). An usual sorting algorithm like bubble sort or merge sort it’s taking O(n^2), which it’s very inefficient for array with over 5000 elements.
I will write an implementation of this algorithm in Delphi.
The Quicksort algorithm it’s very similar to divide and conquer algorithm because it splits the array into to sub arrays, sort those sub arrays and put them together after into 1 array sorted. For sorting those array it uses a pivot that it’s positioned in the middle of the array and put in the left, strings that are lower and in the right, the strings that are higher. So for doing this it uses a recursive function because for every sub array divides again in 2 sub array and sort them. So after sorting each sub array , we will have in the final step all the array sorted.
Here is an implementation of Quicksort array of string in Delphi.
First declare a type of array string:
type arraystrings=array[1..100000] of string;
Quicksort algorithm:
procedure QuickSort(var A: arraystrings; Lo, Hi: Integer); procedure Sort(l, r: Integer); var i, j,aux: integer; y,x:string; begin i := l; j := r; x := a[(l+r) DIV 2]; repeat while strIcomp(pchar(a[i]),pchar(x))<0 do i := i + 1; while StrIComp(pchar(x),pchar(a[j]))<0 do j := j - 1; if i <= j then begin y := a[i]; a[i] := a[j]; a[j] := y; i := i + 1; j := j - 1; end; until i > j; if l < j then Sort(l, j); if i < r then Sort(i, r); end; begin Sort(Lo,Hi); end;
Tags: Algorithms, Delphi
Posted in Algorithms, Codes, Delphi | 2 Comments »
Remove duplicates from file
Written by Codes Tips on March 27, 2009 – 8:33 am -I will show you how you can remove word duplicates form a file with an efficient algorithm. Say you are having a large file with words that are line by line in a file on your disk. If you want to remove word or phrases duplicates from file you should first read the entire file into an array of strings, sort it and after that remove duplicate phrases and write back to the file.
Why we sort the array?
Because if we would not sort the array of strings then the complexity of a normal algorithm like, taking each phrase and compare to all other phrases, will have the O(N^2) complexity.
Tip: you should use QuickSort algorithm because if you have over 5000 phrases or words, the application will freeze. The complexity of the QuickSort algorithm is O(n*log(n)), so if you have saying 100.000 phrases, the complexity of the QuickSort will be 5000*log(5000) which is lower then 5000*5000, that a normal sorting algorithm uses to sort an array.
After sorting the array you should go through the array from the first phrase to the last element and compare on each step if the previous phrase is equal with the current phrase. If the phrase is not equal we write it to the output file.
This is the description of an efficient remove duplicates phrases algorithm.This function will work even for 1 million phrases or words. Here is the source code of the procedure:
procedure RemoveDuplicates(pathtofile:string); var f:textfile; phrases:array[1..1000000] of string; nr,i,nrduplicates:integer; exists:boolean; s:string; begin nrduplicates:=0; nr:=0; exists:=false; assignfile(f,pathtofile); reset(f); while not eof(f) do begin inc(nr); readln(f,phrases[nr]); end; closefile(f); QuickSort(phrases,1,nr); assignfile(f,pathtofile); rewrite(f); s:=''; for i:=1 to nr do if strIcomp(pchar(s),pchar(phrases[i]))<>0 then begin writeln(f,phrases[i]); s:=phrases[i]; end else inc(nrduplicates); closefile(f); showmessage(inttostr(nrduplicates)+' duplicates removed'); end;
Tags: Algorithms, borland delphi, Delphi
Posted in Algorithms, Codes, Delphi | No Comments »
Convert shortint to bits and bits to shortint
Written by Codes Tips on March 18, 2009 – 3:22 am -A short int have 16 bits so we will need a vector of 16 bits:
short int bits[16]; // from 0 to 15
To convert a short int to bits you should divide the integer by 2 until he is 0.
void ShortIntToBits(int x) { int nr=-1,k1; for(k1=0;k1<=15;k1++) bits[k1]=0; while (x!=0) { nr++; bits[nr]=x%2; x=x/2; } }
To convert a vector of bits to shortint we should iterate to the vector of bits adding to integer a value that is 2(because we have bits) at power of the position of bit.
Here is an example that have a vector of 15 bits.
short int BitsToShortInt() { short int k1,p=1,x=0; for (k1=0;k1<=15;k1++) { x=x+bits[k1]*p; p=p*2; } return x; }
Tags: Algorithms, C/C++, Pascal
Posted in Algorithms | No Comments »
