Sorting and Searching Technique

Searching is an operation or a technique that helps finds the place of a given element or value in
the list. Any search is said to be successful or unsuccessful depending upon whether the element
that is being searched is found or not. Some of the standard searching technique that is being
followed in data structure is listed below:

1. Linear Search

2. Binary Search

SORTING Preliminaries:
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 that require sorted lists to work correctly and for producing human -
readable input. Sorting algorithms are often classified by :

* Computational complexity (worst, average and best case) in terms of the size of the list (N).

For typical sorting algorithms good behaviour is O(NlogN) and worst case behaviour is O(N2 )
and the average case behaviour is O(N).

* Memory Utilization

* Stability - Maintaining relative order of records with equal keys.

* No. of comparisions. * Methods applied like Insertion, exchange, selection, merging etc.

Sorting is a process of linear ordering of list of objects.

Sorting techniques are categorized into

 Internal Sorting
 External Sorting

Internal Sorting takes place in the main memory of a computer.

eg : - Bubble sort, Insertion sort, Shell sort, Quick sort, Heap sort, etc.

External Sorting, takes place in the secondary memory of a computer, Since the number of
objects to be sorted is too large to fit in main memory.

eg : - Merge Sort, Multiway Merge, Polyphase merge.

Elementary Sorting Techniques:

The general sorting problem is simple enough to describe: Given an

initially unordered array of N records, with one field distinguished as the
key, rearrange the records so they are sorted into increasing (or
decreasing) order, according to each record's key.

Sorting algorithms are used in all kinds of applications and are necessary,
for instance, if we plan to use efficient searching algorithms like Binary
Search or Interpolation Search, since these require their data to be
sorted.

Sorting algorithms are often subdivided into "elementary" algorithms that

are simple to implement compared to more complex algorithms that, while
more efficient, are also more difficult to understand, implement, and
debug.

It is not always true that the more complex algorithms are the preferred
ones. Elementary algorithms are generally more appropriate in the following
situations:

* less than 100 values to be sorted

* the values will be sorted just once
* special cases such as:
 the input data are "almost sorted"
 there are many equal keys

In general, elementary sorting methods require O(N2) steps for N random key
values. The more complex methods can often sort the same data in just O(N
log N) steps. Although it is rather difficult to prove, it can be shown
that roughly N log N comparisons are required, in the general case.

Example- Bubble Sort, Insertion Sort, Selection Sort, Merge Sort

Internal vs. External Sorting

Normally, when considering a sorting problem, we will assume that the
number of records to be sorted is small enough that we can fit the entire
data set in the computer's memory (RAM) all at once. When this is true, we
can make use of an internal sorting algorithm, which assumes that any key
or record can be accessed or moved at any time. That is, we have "random
access" to the data.

Sometimes, when sorting an extremely large data set such as Canada's Census
Data, there are simply too many records for them to all fit in memory at
once. In this case, we have to resort to external sorting algorithms that
don't assume we have random access to the data. Instead, these algorithms
assume the data is stored on magnetic tapes or disks and only portions of
the data will fit in memory. These algorithms use "sequential access" to
the data and proceed by reading in, processing, and writing out blocks of
records at a time. These partially sorted blocks need to be combined or
merged in some manner to eventually sort the entire list.

Bubble sort Algorithm:

Bubble sort works on the repeatedly swapping of adjacent elements until they are not in the
intended order. It is called bubble sort because the movement of array elements is just like the
movement of air bubbles in the water. Bubbles in water rise up to the surface; similarly, the array
elements in bubble sort move to the end in each iteration.

Bubble short is majorly used where –

o complexity does not matter

o simple and short code is preferred

Algorithm
In the algorithm given below, suppose arr is an array of n elements. The assumed swap function
in the algorithm will swap the values of given array elements.

begin BubbleSort(arr)
for all array elements
if arr[i] > arr[i+1]
swap(arr[i], arr[i+1])
end if
end for
return arr
end BubbleSort

Working of Bubble sort Algorithm

Now, let's see the working of Bubble sort Algorithm.

To understand the working of bubble sort algorithm, let's take an unsorted array. We are
taking a short and accurate array, as we know the complexity of bubble sort is O(n2).

Let the elements of array are -

First Pass
Sorting will start from the initial two elements. Let compare them to check which is greater.

Here, 32 is greater than 13 (32 > 13), so it is already sorted. Now, compare 32 with 26.

Here, 26 is smaller than 36. So, swapping is required. After swapping new array will look
like -

Now, compare 32 and 35.

Here, 35 is greater than 32. So, there is no swapping required as they are already sorted.

Now, the comparison will be in between 35 and 10.

Here, 10 is smaller than 35 that are not sorted. So, swapping is required. Now, we reach at
the end of the array. After first pass, the array will be -

Now, move to the second iteration.

Second Pass
The same process will be followed for second iteration.
Here, 10 is smaller than 32. So, swapping is required. After swapping, the array will be -

Now, move to the third iteration.

Third Pass
The same process will be followed for third iteration.

Here, 10 is smaller than 26. So, swapping is required. After swapping, the array will be -

Now, move to the fourth iteration.

Fourth pass
Similarly, after the fourth iteration, the array will be -
 Hence, there is no swapping required, so the array is completely sorted.

1. Time Complexity
Case Case Time Time Complexity Complexity

Best Case O(n)

Average Case O(n2)

Worst Case O(n2)

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array is
already sorted. The best-case time complexity of bubble sort is O(n).
o Average Case Complexity - It occurs when the array elements are in jumbled order that
is not properly ascending and not properly descending. The average case time complexity
of bubble sort is O(n2).
o Worst Case Complexity - It occurs when the array elements are required to be sorted in
reverse order. That means suppose you have to sort the array elements in ascending order,
but its elements are in descending order. The worst-case time complexity of bubble sort
is O(n2).

2. Space Complexity
Space Complexity O(1)
Stable YES

o The space complexity of bubble sort is O(1). It is because, in bubble sort, an extra
variable is required for swapping.
o The space complexity of optimized bubble sort is O(2). It is because two extra variables
are required in optimized bubble sort.