31-10-2012, 05:56 PM
SEARCHING AND SORTING CONCEPTS- PARTICIPANT GUIDE
SEARCHING AND SORTING.doc (Size: 120 KB / Downloads: 24)
Overview
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly.
A search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer scientists that solve problems are kinds of search algorithms.
Here we discuss about some of the searching and sorting algorithms and and analysis of algorithms with respect to time and space requirements.
Searching concept
• Searching is Locating a particular data item in a list of data elements is known as searching.
• Search takes a problem as input and returns a solution to the problem
• Search is the process of locating data like a word, a file etc
• There are different Types of search- Few of them are
o Linear Search
o Binary Search
Linear Search
• linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value.
• It operates by checking every element of a list until a match is found. Linear search runs in O(N). (this will be explained later in the module) If the data are distributed randomly, on average N/2 comparisons will be needed.
• The best case is that the value is equal to the first element tested, in which case only 1 comparison is needed. The worst case is that the value is not in the list, in which case N comparisons are needed.
Sort Concept
• Sorting is the process of arranging data items in a particular order (Ascending or descending).
• Sorting is a feature in which the elements of a list are put in certain order
• There are different Types of search- Few of them are
o Selection sort
o Bubble sort
Selection Sort
• In Selection sort it selects the smallest unsorted item remaining in the list, and then swapping it with the item in the next position to be filled.
• It Beginning with the first element in the array, a search is performed to locate the element which has the smallest key. When the element is found it is interchanged with the first element. This process is continued for all the elements in the array.
• It is mainly used with small list of elements