|
Data Structure Sorting - August 22, 2008 at 13:10 PM by Rajmeet
Ghai
What is linear search?
Answer
Linear search is the simplest form of search. It searches for the element
sequentially starting from the first element. This search has a disadvantage if
the element is located at the end. Advantage lies in the simplicity of the
search. Also it is most useful when the elements are arranged in a random
order.
What is binary search?
Answer
Binary search is most useful when the list is sorted. In binary search, element
present in the middle of the list is determined. If the key (number to search)
is smaller than the middle element, the binary search is done on the first
half. If the key (number to search) is greater than the middle element, the
binary search is done on the second half (right). The first and the last half
are again divided into two by determining the middle element.
Explain the bubble sort algorithm.
Answer
Bubble sort algorithm is used for sorting a list. It makes use of a temporary
variable for swapping. It compares two numbers at a time and swaps them if they
are in wrong order. This process is repeated until no swapping is needed. The
algorithm is very inefficient if the list is long.
E.g. List: - 7 4 5 3
1. 7 and 4 are compared
2. Since 4 < 7, 4 is stored in a temporary variable.
3. the content of 7 is now stored in the variable which was holding 4
4. Now, the content of temporary variable and the variable previously holding 7
are swapped.
What is quick sort?
Answer
Quick sort is one the fastest sorting algorithm used for sorting a list. A
pivot point is chosen. Remaining elements are portioned or divided such that
elements less than the pivot point are in left and those greater than the pivot
are on the right. Now, the elements on the left and right can be recursively
sorted by repeating the algorithm.
|