Important Short Questions and Answers: Sorting and Searching

1. What is meant by Sorting and searching?

Sorting and searching are fundamentals operations in computer science. Sorting refers to the operation of arranging data in some given order

Searching refers to the operation of searching the particular record from the existing information

2. What are the types of sorting available in C?

Insertion sort

Merge Sort

Quick Sort

Radix Sort

Heap Sort

Selection sort

Bubble sort

3. Define Bubble sort.

Bubble sort is the one of the easiest sorting method. In this method each data item is compared with its neighbor and if it is an descending sorting , then the bigger number is moved to the top of all

The smaller numbers are slowly moved to the bottom position, hence it is also called as the exchange sort.

3.Mention the various types of searching techniques in C

Linear search

Binary search

5. What is linear search?

In Linear Search the list is searched sequentially and the position is returned if the key element to be searched is available in the list, otherwise -1 is returned. The search in Linear Search starts at the beginning of an array and move to the end, testing for a match at each item.

6. What is binary search?

Binary search is simpler and faster than linear search. Binary search the array to be searched is divided into two parts, one of which is ignored as it will not contain the required element

One essential condition for the binary search is that the array which is to be searched, should be arranged in order.

7. Define merge sort?

Merge sort is based on divide and conquer method. It takes the list to be stored and divide it in half to create two unsorted lists.

The two unsorted lists are then sorted and merge to get a sorted list.

8. Define insertion sort?

Successive element in the array to be sorted and inserted into its proper place with respect to the other already sorted element. We start with second element and put it in its correct place, so that the first and second elements of the array are in order.

9. Define selection sort?

It basically determines the minimum or maximum of the lists and swaps it with the element at the index where its supposed to be.

The process is repeated such that the n^th minimum or maximum element is swapped with the element at the n-1^th index of the list.

10. What is the basic idea of shell sort?

Shell sort works by comparing elements that are distant rather than adjacent elements in an array or list where adjacent elements are compared.

Shell sort uses an increment sequence. The increment size is reduced after each pass until increment size is 1.

11.            What is the purpose of quick sort and advantage?

The purpose of the quick sort is to move a data item in the correct direction, just enough for to reach its final place in the array.

Quick sort reduces unnecessary swaps and moves an item to a greater distance, in one  move.

12. Define quick sort?

The quicksort algorithm is fastest when the median of the array is chosen as the pivot value. That is because the resulting partitions are of very similar size.

Each partition splits itself in two and thus the base case is reached very quickly and it follow the divide and conquer strategy.

13. Advantage of quick sort?

Quick sort reduces unnecessary swaps and moves an item to a greater distance, in one move.

14. Define radix sort?

Radix sort the elements by processing its individual digits. Radix sort processing the digits either by least significant digit(LSD) method or by most significant digit(MSD) method.

Radix sort is a clever and intuitive little sorting algorithm, radix sort puts the elements in order by comparing the digits of the numbers.

15. List out the different types of hashing functions?

The different types of hashing functions are,

The division method

The mind square method

The folding method

Multiplicative hashing

Digit analysis

16.Define hashing?

  Search from that position for an empty location

  Use a second hash function.

  Use that array location as the header of a linked list of values that hash to this location

17. Define hash table?

All the large collection of data are stored in a hash table. The size of the hash table is usually fixed and it is bigger than the number of elements we are going to store.

The load factor defines the ration of the number of data to be stored to the size of the hash table

18.            What are the types of hashing?

Static hashing-In static hashing the process is carried out without the usage of an index structure.

Dynamic hashing- It allows dynamic allocation of buckets, i.e. according to the demand of database the buckets can be allocated making this approach more efficient.

19.            Define Rehashing?

Rehashing is technique also called as double hashing used in hash tables to resolve hash collisions, cases when two different values to be searched for produce the same hash key.

It is a popular collision-resolution technique in open-addressed hash tables.