Fundamentals of Computer Algorithms Essay

Searching and sorting are two classes of basic algorithms which influence heavily the productivity and speed of software. These algorithms are most widely used in software and web applications. Though main methods of searching and sorting have been closely examined, new methods offering original ways of optimization emerge. The aim of this essay is to discuss one method of sorting (bubble sort) and one method of searching (binary search), set an example of realization of these algorithms and estimate their efficiency in terns of big O notation with regard to a set of N elements. This notation describes the behavior of the function when the argument tends to infinity.

1. Sorting algorithms

Generally, sorting is a process of putting elements of some list in a given order. Main sorting algorithms are (Horowitz, 1993):

ü    Bubble sort

ü    Insertion sort

ü    Shell sort

ü    Merge sort

ü    Heap sort

ü    Quick sort

ü    Bucket sort

ü    Radix sort

ü    Distribution sort

ü    Shuffle sort

1.1. Bubble sort

This sorting works by repeatedly stepping through the list to be sorted. It compares two items at a time and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed; this indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list (Sedgewick, 2001).

1.2. Example

int array[n];

void swap (int a, int b)

{

int c;

c = array[a];

array[a] = array[b];

array[b] = c;

}

int main ()

{

for (int i = 1; i < n; i++) {

for (int j = 0; j < n-1; j++) {

if (array[j] > array[j + 1])

swap (j, j + 1);

}

}

return (0);

}

1.3. Efficiency

In the procedure, we perform n(n-1) comparisons (Sedgewick, 2001); therefore, the execution time of bubble sort in its classical realization is estimated as O(n2).

2. Search algorithms

A search task is when an input is given and evaluation of the number of possible occurrences of the input in a given dataset (and their places) should be given. The set of all possible solutions to a problem is called the search space. Here we will regard the case where we search for one occurrence of the input only, and return its position in the dataset.

The most popular search algorithms are (Knuth, 1973):

ü    uniformed search

ü    list search

ü    binary search

ü    informed search

ü    adversarial search

2.1. Binary search

This method can only be applied to sorted arrays of data. The method of binary search searches the location of the sought value by selecting the middle element in the span (which, because the list is in sorted order, is the median value), compares its value to the target value, and determines if it is greater than, less than, or equal to the target value. A guessed index whose value turns out to be too high becomes the new upper bound of the span, and if its value is too low that index becomes the new lower bound (Knuth, 1973). Pursuing this strategy iteratively, the method reduces the search span by a factor of two each time, and soon finds the target value or else determines that it is not in the list at all.

2.2. Example

int binary_search(int a[], int low, int high, int target) {

if (high < low)

return -1;

int middle = (low + high)/2;

if (target < a[middle])

return binary_search(a, low, middle-1, target);

else if (target > a[middle])

return binary_search(a, middle+1, high, target);

else if (target == a[middle])

return middle;

}

 

2.3. Efficiency

Let us suggest that search is successful. Then, the search may happen early, or happen later. Generally, for good cases efficiency may be estimated as , and for the worst ones as  (Sedgewick, 2001). For the case when element is not in list, we also obtain. Therefore, binary search is a logarithmic algorithm and its execution time is estimated as

Conclusion

We have analyzed the idea, implementation and execution time of a sorting algorithm (bubble sort) and of a search algorithm (binary search). The efficiency of bubble sort is one of the lowest for all sorting of algorithms (though it work quite good on several types of sets).

The efficiency of binary search is very high, and it is one of the most popular methods. The disadvantage of binary search is the demand to search in a previously sorted list.



Leave a Reply