"Sorting And Searching"

Name: Pooja Sharma
Contact Info: psharma105@qc.cuny.edu
Math 213 W-- Mathematics with Mathematica, Fall 2009 
Prof. Christopher Hanusa
December 11, 2009

(* PLEASE DO NOT EVALUATE THIS FILE *)

Abstract
My project investigates the question about the methods we use in computer science to arrange the data and searching the particular kind of information from that organized data. By comparing the different type of methods, mathematica actually gives me different conclusions at different points and it tells me when to use which method to get the organized information in less time and in more efficient way.

Section 1. Introduction

1.1 Background

We all know what does sorting and searching mean, but still today sorting is so important and potentially so time- consuming, it has been the subject of research for programmers and some very sophisticated methods have been developed such as merge sort, insertion sort, selection sort, bubble sort etc. To arrange the data in certain order we commonly use linear search, hashing, binary search etc. to search particular kind of information. In computer science, we estimate the run times of these methods in terms of "little oh"  and "little omega", but I want to see that if mathematica can tell me the difference between their runtimes more clearly by giving me the results especially in seconds. This way I can see which method takes less seconds to sort and search the numbers.

1.2 Problem Statement

The problem statement I answer is:

When and which sorting and searching methods should I use to arrange my random data and to find an element (from sorted lists) in a less time?

1.3 Useful Commands

?Module
?While
?For
?Floor
?Flatten
?Break
?Timing

1.4 File Structure

In Section 2, I explain the code that I used to investigate my problem and in Section 3, I discuss my results, findings and mention topics for future work.

Section 2. Main Work

2.1  Random data:

To have a strong and clear conclusion, I created six lists which are differ by almost hundereds and thousands of random numbers. So I could get an idea that how fast my sorting methods can arrange them.

firstL= {11,9,3,8,1,6,0,4,2};
secondL= Table[Random[],{20}];
thirdL= Table[Random[],{50}];
fourthL= Table[Random[],{500}];
fifthL= Table[Random[],{1000}];
sixthL= Table[Random[],{10000}];

List1=Sort[RandomInteger[10000,5000]];

List2=Sort[RandomInteger[50000,10000]]

List3= Sort[RandomInteger[500000,100000]]

List4=Sort[RandomInteger[50000000,10000000]]

2.2 Finding the Last Digit

Swap:
In this file I will use the swap funciton many times. The purpose of swap function is to interchange the enteries of the list.

swap[list_,i_,j_]:= Module[{l=list},{l[[i]],l[[j]]}={l[[j]],l[[i]]};l](*Take the list as a input and intialize it to l and interchange the entries i and j in the list and print out the list.*)

Insertion Sort:
Insertion Sort is a simple sorting method. The first iteration of this algorithm takes the second element in the list, and if it is less that the first value of list, swap it with the first element using swap function (as explained above). Then the second iteration looks at the third element and inserts into the correct position with respect to the first two elements and so on.

insertionSort[list11_List]:= Module[{l11=list11, j,i,index,n=Length[list11]},(*intialize the list11 to l11,n to the length of the list and declare i,j and index as local variables.*)
For[i=1,i<n,i++;
index=l11[[i]];(* intialize location to place element *)
j=i;
While[j>0 && (l11[[j-1]]> index),(*search for place to put curret element*)l11[[j]]=l11[[j-1]];j--];(*shift element right one slot*)
l11[[j]]=index; (* place inserted element*)
];l11 (*print out the sorted list*)
]

insertionSort[firstL]

Timing[insertionSort[thirdL]];
Timing[insertionSort[fourthL]];
Timing[insertionSort[sixthL]];

Quick Sort:
The basic idea of quick sort is to divide the elements to be sorted into two roughly equal groups, sort the two groups by recursive calls, and combines the two sorted groups into a single list of sorted values.

quickSort[list_List]:= Module[{l=list},qSort[l,1,Length[l]];l]
(*intialize the list to l and call the another method qSort with parameters list, first index and last ndex *)
qSort[alist_,n1_,n2_]:= Module[{llist=alist,pivot=alist[[Floor[(n1+n2)/2]]],i=n1,j=n2},(*in this case, pivot is a middle number of the list, i is first index and n2 is last index*)
While[True,
While[llist[[i]]<pivot,i++];(*each number before the pivot should be less than the pivot*)
While[llist[[j]]>pivot,j--];
If[i≥ j,Break[]];(*and the numbers after the pivot should be greater than the middle value. If i becomes equal to j ,stop compairing*)
llist=swap[llist,i,j];(*otherwise call the swap function to exchange the values of i and j*)
i=n1;j=n2;pivot=llist[[Floor[(n1+n2)/2]]]];
Flatten[ If[n1≠n2,{If[n1==Floor[(n1+n2)/2],llist[[n1]],qSort[llist,n1,Floor[(n1+n2)/2]]],(*now after sorted the less values before the pivot and large values after the pivot, call the method qSort again to sort the list from first element to one less than the pivot value and list after the pivot value to the end of the list.*)
If[n2==Floor[(n1+n2)/2],llist[[n2]],qSort[llist,Floor[(n1+n2)/2]+1,n2]]},{llist[[n1]]}]]
]

qSort[firstL,1,Length[firstL]]

Timing[qSort[thirdL,1,Length[thirdL]]];

Timing[qSort[thirdL,1,Length[fourthL]]];
Timing[qSort[sixthL,1,Length[sixthL]]];

2.3 Find a number from Sorted List:

Linear Search:
Linear Search or Serial Search is the searching algorithm which steps through part of an array one element at a time looking for "desired number" and the search stops when the element is found.

linearsearch[lis_List,val_]:= Module[{lii=lis,i,n=Length[lis]},(*After intialize the list to lii and n to the length of the list, use a loop which goes over through every index.*)
For[i=0,i<n,i++;
If[val==lii[[i]],(*if the same value in the index of the list, then print out the statement otherwise dont print anything.*)Print[val "is in the list."]]]]

linearsearch[firstL,4]

Timing[linearsearch[List1,9485]];

Timing[linearsearch[List2,98521]];
Timing[linearsearch[List3,99951]];
Timing[linearsearch[List4,4999917]]

Binary Search:
Binary Search method, first of all, tests the middle element in the list. If this matches the search element (the value that is may or may not be present in the list.), the algorithm ends. If the search element is less than the middle element, the algorithm will search the search element in the first half of the list. If the search element is larger than the middle value, then the algorithm will search the element in the second half of the list.

binaryS[list_,val_]:= Module[{llist=list},binarySearch[llist,val,1,Length[llist]]];
(*In binaryS method, intialize the list to the llist and call the method binarySearch which takes parameters as llist, length of the list and the value that we want to find out from the list. To find out the value we will search the list from first number of list to the end of the list.*)

binarySearch[ist_,v_,l_,r_]:= Module[{middle= Floor[(l+r)/2],left=l,right=r},(*Now find out the middle index.*)
If[ist[[middle]]==v,True,(*Then see of the middle value of the list is equal to the information we are looking for; if it is then Print out true. *)If[left≥right,False,If [ist[[middle]]>v,(*If the value that we are looking for is less than middle number of list....*)binarySearch[ist,v,left,middle-1],(*..then look at the list in the first half of the list.*)
binarySearch[ist,v,middle+1,right]]](*otherwise, look at the list from next to the middle value to the end of the list.*)
]]

binaryS[firstL,4]

Timing[binaryS[List1,9485]];
Timing[binaryS[List2,98521]];
Timing[binaryS[List3,99951]];
Timing[binaryS[List4,4999917]];

Section 3. Conclusion and Future Work

3.1  Results

For Sorting :

After trying to sort the huge and different range of numbers, I get the following results in seconds :

data={{50,0.015,0.016},{100,0.032,0.046},{500,.546,.405},{1000,2.044,1.17},{10000,204.501,88.109}};

(*The results that I got after compairing the sorting methods.*)

Text@ (*to display the results in a plain text form*)Grid[Prepend[data,{"Range","Insertion Sort (in seconds) ","  Quick Sort (in seconds)"}],Background->{None,{Lighter[Yellow,.9],{White,Lighter[Blend[{Blue,Green}],.8]}}},Dividers->{{Darker[Gray,.6],{Lighter[Gray,.5]},Darker[Gray,.6]},{Darker[Gray,.6],Darker[Gray,.6],{False},Darker[Gray,.6]}},Alignment->{{Left,Right,{Left}}},ItemSize->{{5,8,8}},Frame->Darker[Gray,.6],ItemStyle->14,Spacings->{Automatic,.8}];

(*I put together the above results in a table under different columns.*)

Conclusion: To have your small range of data in sorted order, we could use insertion sort. But as we have seen that the run time becomes huge when we try to sort more than 10 000 numbers, so it is better to use quick sort to sort the data instead of insertion sort if we want to sort a very large number of lists.

Results after compairing the Binary Search and Linear Search Methods :

data1={{5000,0.047,"null"},{10000,0.078,9.3813× 10^-15},{50000,.281,2.492×10^-14},{10000000,40.919,2.15×10^-14}};

(*The data I collected after running these two mthods : Linear Search and Binary Search.*)

Text@Grid[Prepend[data1,{"Lists","Linear Search (in seconds) ","  Binary Search (in seconds)"}],Background->{None,{Lighter[Yellow,.9],{White,Lighter[Blend[{Blue,Green}],.8]}}},Dividers->{{Darker[Gray,.6],{Lighter[Gray,.5]},Darker[Gray,.6]},{Darker[Gray,.6],Darker[Gray,.6],{False},Darker[Gray,.6]}},Alignment->{{Left,Right,{Left}}},ItemSize->{{5,8,8}},Frame->Darker[Gray,.7],ItemStyle->14,Spacings->{Automatic,.9}]

(*I made the table and under the "Lists" I put the range of lists. Under the Linear search and Binary Search the results are given in seconds.*)

Conclusion: After looking at the above table, it is clear to me that binary search is definitely the best searching method to find any number even if we have thousands and thousands numbers in the list.

3.2 Discussion

The difference between all these methods is that binary search and quicksort are based on recursion idea whereas insertion sort and linear search work on the idea of iteration. I think that's why when I try to sort and find any number, recursive methods 'response is faster than the iterative methods. Recursion is always a good idea for large list because it breaks down the list into smaller lists and then rearrange them, whereas iteration works all the way up to the length of the list.

3.3 Future Work

If I had more time, I would like to show the difference between the above defined methods with animation. Moreover, I've heard that Binary Tree is much faster than quick sort in terms of sorting. So, may be I could compare the runtimes of Binary Tree and quick sort in future.

Section 4. References

Lafore, R. (1998). Data Structures & Algorithms in Java. Corte Madera: Waite Group Press.

Main, M. (1995). Data Structures and Other Objects in Java. New York: Pearson Addison Wesley.