Unit 2

Searching and Sorting

2.1 Need of searching and sorting

Introduction to Searching

Searching in data structure refers to the process of finding location LOC of an element in a list. This is one of the important parts of many data structures algorithms, as one operation can be performed on an element if and only if we find it. Various algorithms have been defined to find whether an element is present in the collection of items or not. This algorithm can be executed on both internal as well as external data structures. The efficiency of searching an element increases the efficiency of any algorithm.

Searching Techniques in Data Structure

The most famous techniques of searching in data structures are:

1. Sequential Search

This is the traditional technique for searching an element in a collection of elements. In this type of search, all the elements of the list are traversed one by one to find if the element is present in the list or not. One example of such an algorithm is a linear search. This is a very simple and basic algorithm. Suppose ARR is an array of n elements, and we need to find location LOC of element ITEM in ARR. For this, LOC is assigned to -1 which indicates that ITEM is not present in ARR. While comparing ITEM with data at each location of ARR, and once ITEM == ARR[N], LOC is updated with location N+1. Hence we found the ITEM in ARR.

Algorithm:

LSEARCH(ARR, N, ITEM, LOC) Here ARR Is the array of N number of elements, ITEM holds the value we need to search in the array and algorithm returns LOC, the location where ITEM is present in the ARR. Initially, we have to set LOC = -1.

1. Set LOC = -1,i=1
2. Repeat while DATA[i] != ITEM:
i=i+1
3. If i=N+1 ,then Set LOC =0
Else LOC = N+1
4. Exit.

Let’s say, below is the ARR with 10 elements. And we need to find whether ITEM= 18 is present in this array or not. 

In the start, LOC =-1

Step 1: ITEM != 77 thus we move to next element.

Step 2: ITEM != 56 thus we move to next element.

Step 3: ITEM != 14 thus we move to next element.

Step 4: ITEM != 7 thus we move to the next element.

Step 5: Hence ITEM == ARR[4] thus LOC updated to 5.

Complexity of Sequential Search

Here are the complexities of the linear search given below.

Space complexity

As linear search algorithm does not use any extra space thus its space complexity = O(n) for an array of n number of elements.

Time Complexity

• Worst case complexity: O(n) – This case occurs when the element to search is not present in the array.
• Best case complexity: O(1) – This case occurs when the first element is the element to be searched.
• Average complexity: O(n) – This means when an element is present somewhere in the middle of the array.

2. Binary Search

This is a technique to search an element in the list using the divide and conquer technique. This type of technique is used in the case of sorted lists. Instead of searching an element one by one in the list, it directly goes to the middle element of the list and divides the array into 2 parts, and decides element lies in which sub-array does the element exist.

Suppose ARR is an array with sorted n number of elements present in increasing order. With every step of this algorithm, the searching is confined within BEG and END, which are the beginning and ending index of sub-arrays. The index MID defines the middle index of the array where,

MID = INT(beg + end )/2

And then, it needs to be checked if ITEM < ARR[N} where ITEM is the element that we need to search in ARR.

• If ITEM = ARR[MID] then LOC = MID and exit .
• If ITEM < ARR[MID} then ITEM can appear in the left sub-array, then BEG will be the same and END = MID -1 and repeat.
• If ITEM > ARR[MID] then ITEM can appear in the right subarray then BEG = MID+1 and END will be the same and repeat.

After this MID is again calculated for respective sub-arrays. In case we didn’t find the ITEM, the algorithm returns -1 otherwise LOC = MID.

Algorithm:

BSEARCH(ARR, LB, UB, ITEM, LOC) Here, ARR is a sorted list of elements, with LB and UB are lower and upper bounds for the array. ITEM needs to be searched in the array and algorithm returns location LOC, index at which ITEM is present else return -1.

1. Set BEG = LB, END = UB and MID = INT([BEG+END]/2)
2. Repeat step 3 and 4 while BEG <= END and ARR[MID] != ITEM
3. IF ITEM< ARR[MID] then:
Set END = MID-1
Else:
Set BEG = MID+1
4. Set MID = INT(BEG+END)/2
5. IF ARR[MID] = ITEM then:
Set LOC = MID
Else:
Set LOC = NULL
6. Exit.

Let’s say here, ITEM = 62

BEG = 1 and END =9 Hence MID = (1+9)/2 = 5
ARR[MID] = 52

Step 1: ARR[MID] < ITEM : thus END =9 and BEG = MID +1 = 6. Thus our new sub-array is,

Step 2: Now BEG =6 and END =9 thus MID = INT([6+9]/2)= 6
NOW ARR[6] =ITEM. Thus LOC = MID
Thus LOC = 6

Complexity of Binary Search

Here are the complexities of the binary search given below.

• Worst Case: O(nlogn)
• Best Case: O(1)
• Average Case: O(nlogn)

Conclusion

Searching refers to finding the location of one element in the array of n elements. There are 2 types of search linear and binary Search, Linear search algorithm is very simple and has O(n) of complexity whereas Binary Search is a very fast searching algorithm having the complexity of (logn) but can only be used in case of the sorted list of elements. In case the size of the array is large, it is preferable to use binary search instead of linear search. Binary search is used in many searching data structures. In the case of mid-size arrays, the linear search algorithm is more preferred.

Sorting Techniques

Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.

The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Following are some of the examples of sorting in real-life scenarios −

• Telephone Directory − The telephone directory stores the telephone numbers of people sorted by their names, so that the names can be searched easily.
• Dictionary − The dictionary stores words in an alphabetical order so that searching of any word becomes easy.

In-place Sorting and Not-in-place Sorting

Sorting algorithms may require some extra space for comparison and temporary storage of few data elements. These algorithms do not require any extra space and sorting is said to happen in-place, or for example, within the array itself. This is called in-place sorting. Bubble sort is an example of in-place sorting.

However, in some sorting algorithms, the program requires space which is more than or equal to the elements being sorted. Sorting which uses equal or more space is called not-in-place sorting. Merge-sort is an example of not-in-place sorting.

Stable and Not Stable Sorting

If a sorting algorithm, after sorting the contents, does not change the sequence of similar content in which they appear, it is called stable sorting.

If a sorting algorithm, after sorting the contents, changes the sequence of similar content in which they appear, it is called unstable sorting.

Stability of an algorithm matters when we wish to maintain the sequence of original elements, like in a tuple for example.

Adaptive and Non-Adaptive Sorting Algorithm

A sorting algorithm is said to be adaptive, if it takes advantage of already 'sorted' elements in the list that is to be sorted. That is, while sorting if the source list has some element already sorted, adaptive algorithms will take this into account and will try not to re-order them.

A non-adaptive algorithm is one which does not take into account the elements which are already sorted. They try to force every single element to be re-ordered to confirm their sortedness.

Important Terms

Some terms are generally coined while discussing sorting techniques, here is a brief introduction to them −

Increasing Order

A sequence of values is said to be in increasing order, if the successive element is greater than the previous one. For example, 1, 3, 4, 6, 8, 9 are in increasing order, as every next element is greater than the previous element.

Decreasing Order

A sequence of values is said to be in decreasing order, if the successive element is less than the current one. For example, 9, 8, 6, 4, 3, 1 are in decreasing order, as every next element is less than the previous element.

Non-Increasing Order

A sequence of values is said to be in non-increasing order, if the successive element is less than or equal to its previous element in the sequence. This order occurs when the sequence contains duplicate values. For example, 9, 8, 6, 3, 3, 1 are in non-increasing order, as every next element is less than or equal to (in case of 3) but not greater than any previous element.

Non-Decreasing Order

A sequence of values is said to be in non-decreasing order, if the successive element is greater than or equal to its previous element in the sequence. This order occurs when the sequence contains duplicate values. For example, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next element is greater than or equal to (in case of 3) but not less than the previous one.

2.2 Concept of internal and external sorting

Sorting is a technique through which we arrange the data in such a manner so that the searching of the data becomes easy. A lot of sorting techniques has been implemented till now to cope up the faster execution of the result and to manage the data comfortably . Sorting and Searching are fundamental 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. Normally, the information retrieval involves searching, sorting and merging. In this chapter we will discuss the searching and sorting techniques in detail.Sorting is very important in every computer application. Sorting refers to arranging of data elements in some given order. Many Sorting algorithms are available to sort the given set of elements.

Let get to know about two sorting techniques and analyze their performance. The two techniques are:

Internal Sorting

External Sorting

Internal Sorting takes place in the main memory of a computer. The internal sorting methods are applied to small collection of data. It means that, the entire collection of data to be sorted in small enough that the sorting can take place within main memory. We will study the following methods of internal sorting

1. Insertion sort

2. Selection sort

3. Merge Sort

4. Radix Sort

5. Quick Sort

6. Heap Sort

7. Bubble Sort

Also a lot of algorithms are involved in sorting . Hence we should understand first that what is an algorithm .

Informally, an algorithm is any well-defined computational procedure that takes some value,

Or set of values, as input and produces some value, or set of values, as output. An algorithm is

Thus a sequence of computational steps that transform the input into the output.

We can also view an algorithm as a tool for solving a well-specified computational problem.

The statement of the problem specifies in general terms the desired input/output relationship.

The algorithm describes a specific computational procedure for achieving that input/output

Relationship.

For example, one might need to sort a sequence of numbers into non decreasing order. This

Problem arises frequently in practice and provides fertile ground for introducing many

Standard design techniques and analysis tools. Here is how we formally define the sorting problem.

Insertion Sort

This is a naturally occurring sorting method exemplified by a card player arranging the cards dealt to him. He picks up the cards as they are dealt and inserts them into the required position. Thus at every step, we insert an item into its proper place in an already ordered list.

We will illustrate insertion sort with an example (refer to Figure 10.1) before presenting the formal algorithm.

Sort the following list using the insertion sort method:

Thus to find the correct position search the list till an item just greater than the target is found. Shift all the items from this point one down the list. Insert the target in the vacated slot. Repeat this process for all the elements in the list. This results in sorted list.

Bubble Sort

In this sorting algorithm, multiple swappings take place in one pass. Smaller elements move or ‘bubble’ up to the top of the list, hence the name given to the algorithm.

In this method, adjacent members of the list to be sorted are compared.If the item on top is greater than the item immediately below it, then they are swapped. This process is carried on till the list is sorted.

The detailed algorithm follows:

Algorithm: BUBBLE SORT 6

1. Begin

2. Read the n elements

3. For i=1 to n

For j=n downto i+1

If a[j] <= a[j-1]

Swap(a[j],a[j-1])

4. End // of Bubble Sort

Total number of comparisons in Bubble sort :

= (N-1) +(N-2) . . . + 2 + 1

= (N-1)*N / 2 =O(N2)

This inefficiency is due to the fact that an item moves only to the next position in each pass.

Quick Sort

This is the most widely used internal sorting algorithm. In its basic form, it was invented by C.A.R. Hoare in 1960. Its popularity lies in the ease of implementation, moderate use of resources and acceptable behaviour for a variety of sorting cases. The basis of quick sort is the divide and conquer strategy i.e. Divide the problem [list to be sorted] into sub-problems [sub-lists], until solved sub problems [sorted sub-lists] are found. This is implemented as follows:

Choose one item A[I] from the list A[ ].

Rearrange the list so that this item is in the proper position, i.e., all preceding items have a lesser value and all succeeding items have a greater value than this item.

1. Place A[0], A[1] .. A[I-1] in sublist 1

2. A[I]

3. Place A[I + 1], A[I + 2] … A[N] in sublist 2

Repeat steps 1 & 2 for sublist1 & sublist2 till A[ ] is a sorted list.

As can be seen, this algorithm has a recursive structure.

The divide’ procedure is of utmost importance in this algorithm. This is usually implemented as follows:

1. Choose A[I] as the dividing element.

2. From the left end of the list (A[O] onwards) scan till an item A[R] is found whose value is greater than A[I].

3. From the right end of list [A[N] backwards] scan till an item A[L] is found whose value is less than A[1].

4. Swap A[R] & A[L].

5. Continue steps 2, 3 & 4 till the scan pointers cross. Stop at this stage.

6. At this point, sublist1 & sublist are ready.

7. Now do the same for each of sublist1 & sublist2.

C:UserssaurabhDesktopbubble-sort-3.pngC:UserssaurabhDesktopbubble_sort.jpg

EXTERNAL SORT GENERAL

Merging Lists Outline

1.Load the next sorted runs R1and R2into main memory buffers B1and B2 a page-at-a-time (i.e., initially first page from each run) (see left figure)

•Obviously R1>=B1 and R2>=B2 (a Run might be larger than a Buffer)

•The rest pages will be loaded to main memory during subsequent steps.

2.Initialize indices i, j to the head of each list (i.e., i=j=0)

3.Compare B1[i] with B2[j] and move smallest item to OUTPUT buffer.

•If B1[i] was smallest item then i++ else j++ (see right figure)

•If OUTPUT gets full, it is appended to the end of a file on DISK and cleared in RAM.

4.Repeat the above until either index i or j reaches the end of its buffer.

•At this point write the remaining records to OUTPUT, flush it to disk and finish.

5.Repeat procedure from 1-4 until all runs have been traversed.

A new sort algorithm, called AlphaSort, demonstrates that commodity processors and disks can handle commercial batch workloads. Using commodity processors, memory, and arrays of SCSI disks, AlphaSort runs the industry-standard sort benchmark in seven seconds. This beats the best published record on a 32-CPU 32-disk Hypercube by 8:1. On another benchmark, AlphaSort sorted more than a gigabyte in one minute. AlphaSort is a cache-sensitive, memory-intensive sort algorithm. We argue that modern architectures require algorithm designers to re-examine their use of the memory hierarchy. AlphaSort uses clustered data structures to get good cache locality, file striping to get high disk bandwidth, QuickSort to generate runs, and replacement-selection to merge the runs. It uses shared memory multiprocessors to break the sort into subsort chores. Because startup times are becoming a significant part of the total time, we propose two new benchmarks: (1) MinuteSort: how much can you sort in one minute, and (2) PennySort: how much can you sort for one penny.

Internal or External?

In an internal sort, the list of records is small enough to be maintained entirely in

Physical memory for the duration of the sort.

In an external sort, the list of records will not fit entirely into physical memory at once.

In that case, the records are kept in disk files and only a selection of them are resident

In physical memory at any given time.

The records stored in the list may be simple (e.g., string or int) or they may be

Complex structures. In any case, we will assume that:

– there is an implicit conversion of a record into its key value,

– key values may be compared using the usual relational operators (<, >, etc.).

The first assumption requires that the record type implementation provides an

Appropriate conversion operator.

The second assumption requires that the key type implementation provides an

Overloading of the relational operators.

None of these features are difficult for a client of the sortable list to implement, and the

Assumptions will make the implementation of the sortable list considerably simpler and

More elegant.

Sorting a list requires accessing the data elements stored in the list. For efficiency this

Suggests that the sort capability should be provided via member functions of the list

Class in question. We will follow that approach here, although the alternative is

Certainly feasible.

Building upon the LinkListT or ArrayT classes discussed earlier, we could derive

Sorted variants, overriding some member functions of the base class and adding new

Member functions for sorting.

If we do that, what base member functions must be overridden?

– The insertion functions must now take into account the ordering of the list

Elements, placing each new element in the proper location.

– A number of the base member functions are unsuitable for a sorted list type

And must be disabled.

– The search functions may now take advantage of the list element ordering.

Template class LinkListT {

Protected:

LinkNodeT* Head; // points to head node in list

LinkNodeT* Tail; // points to tail node in list

LinkNodeT* Curr; // points to “current” node in list

Public:

LinkListT();

LinkListT(const LinkListT& Source);

LinkListT& operator=(const LinkListT& Source);

~LinkListT();

Bool isEmpty() const;

Bool inList() const;

Bool PrefixNode(Item newData);

Bool AppendNode(Item newData);

Bool InsertAfterCurr(Item newData);

Bool Advance();

Void gotoHead();

Void gotoTail();

Bool MakeEmpty();

Bool DeleteCurrentNode();

Bool DeleteValue(Item Target);

Item getCurrentData() const;

Void PrintList(ostream& Out);

Inserting a new record into an ordered list requires:

– searching the list until the appropriate location is found

– creating an empty “slot” in the list to hold the new record

– placing the new record into that “slot”

The search phase is essentially trivial, aside from the issue of ties.

Naturally, a binary search should be used.

The creation of an empty “slot” depends upon the type of list:

– For a contiguous list, the tail of the list must be shifted to make room for the

New element.

– For a linked list, a new list node must be allocated and inserted.

Placing the record into the “slot” is trivial.

The approach described so far maintains the list in sorted order at all times, by placing

Each new element in the appropriate location when it is inserted to the list.

For a list containing N elements, whether contiguous or linked, the average cost of

Ordered insertion of a single new element is Θ(N). When an exact analysis is done,

Performance is worse, of course, for a contiguous list.

Greater efficiency can be obtained if the list elements are inserted and then an efficient

Sort algorithm is applied to the list.

Which approach is preferred depends upon how often the list receives insertions, and

Whether those insertions tend to be grouped or isolated (in time).

2.3 Sort stability

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array.

Some Sorting Algorithm is stable by nature like Insertion Sort, Merge Sort and Bubble Sort etc.

Sorting Algorithm is not stable like Quick Sort, Heap Sort etc.

Another Definition of Stable Sorting:

A Stable Sort is one which preserves the original order of input set, where the comparison algorithm does not distinguish between two or more items. A Stable Sort will guarantee that the original order of data having the same rank is preserved in the output.

In Place Sorting Algorithm:

1. An In-Place Sorting Algorithm directly modifies the list that is received as input instead of creating a new list that is then modified.
2. In this Sorting, a small amount of extra space it uses to manipulate the input set. In other Words, the output is placed in the correct position while the algorithm is still executing, which means that the input will be overwritten by the desired output on run-time.
3. In-Place, Sorting Algorithm updates input only through replacement or swapping of elements.
4. An algorithm which is not in-place is sometimes called not-in-Place or out of Place.
5. An Algorithm can only have a constant amount of extra space, counting everything including function call and Pointers, Usually; this space is O (log n).

Note:

1. Bubble sort, insertion sort, and selection sort are in-place sorting algorithms. Because only swapping of the element in the input array is required.
2. Bubble sort and insertion sort can be applying as stable algorithms but selection sort cannot (without significant modifications).
3. Merge sort is a stable algorithm but not an in-place algorithm. It requires extra array storage.
4. Quicksort is not stable but is an in-place algorithm.
5. Heap sort is an in-place algorithm but is not stable.

2.4 Searching methods: Linear and binary search algorithms, Fibonacci Series

Searching

Searching is the process of finding some particular element in the list. If the element is present in the list, then the process is called successful and the process returns the location of that element, otherwise the search is called unsuccessful.

There are two popular search methods that are widely used in order to search some item into the list. However, choice of the algorithm depends upon the arrangement of the list.

• Linear Search
• Binary Search

Linear Search

Linear search is the simplest search algorithm and often called sequential search. In this type of searching, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match found then location of the item is returned otherwise the algorithm return NULL.

Linear search is mostly used to search an unordered list in which the items are not sorted. The algorithm of linear search is given as follows.

Algorithm

• LINEAR_SEARCH(A, N, VAL)
• Step 1: [INITIALIZE] SET POS = -1
• Step 2: [INITIALIZE] SET I = 1
• Step 3: Repeat Step 4 while I<=N
• Step 4: IF A[I] = VAL
  SET POS = I
  PRINT POS
  Go to Step 6
  [END OF IF]
  SET I = I + 1
  [END OF LOOP]
• Step 5: IF POS = -1
  PRINT " VALUE IS NOT PRESENTIN THE ARRAY "
  [END OF IF]
• Step 6: EXIT

Complexity of algorithm

C Program

1. #include<stdio.h>   
2. Void main ()  
3. {  
4.    Int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};  
5.    Int item, i,flag;  
6.    Printf("\nEnter Item which is to be searched\n");  
7.    Scanf("%d",&item);  
8.    For (i = 0; i< 10; i++)  
9.    {  
10.        If(a[i] == item)   
11.        {  
12.            Flag = i+1;  
13.            Break;  
14.        }   
15.        Else   
16.        Flag = 0;  
17.    }   
18.    If(flag != 0)  
19.    {  
20.        Printf("\nItem found at location %d\n",flag);  
21.    }  
22.    Else  
23.    {  
24.        Printf("\nItem not found\n");   
25.    }  
26. }   

Output:

Enter Item which is to be searched

20

Item not found

Enter Item which is to be searched

23

Item found at location 2

Java Program

1. Import java.util.Scanner;  
2.  
3. Public class Leniear_Search {  
4. Public static void main(String[] args) {  
5.    Int[] arr = {10, 23, 15, 8, 4, 3, 25, 30, 34, 2, 19};  
6.    Int item,flag=0;   
7.    Scanner sc = new Scanner(System.in);  
8.    System.out.println("Enter Item ?");  
9.    Item = sc.nextInt();  
10.    For(int i = 0; i<10; i++)  
11.    {  
12.        If(arr[i]==item)  
13.        {  
14.            Flag = i+1;  
15.            Break;  
16.        }  
17.        Else   
18.            Flag = 0;   
19.    }  
20.    If(flag != 0)  
21.    {  
22.        System.out.println("Item found at location" + flag);  
23.    }  
24.    Else   
25.        System.out.println("Item not found");  
26.      
27. }  
28. }  

Output:

Enter Item ?

23

Item found at location 2

Enter Item ?

22

Item not found

C# Program

1. Using System;  
2.                  
3. Public class LinearSearch  
4. {  
5.    Public static void Main()  
6.    {  
7.        Int item, flag = 0;  
8.        Int[]  a= {10, 23, 5, 90, 89, 34, 12, 34, 1, 78};   
9.        Console.WriteLine("Enter the item value");  
10.        Item = Convert.ToInt32(Console.ReadLine());  
11.        For(int i=0;i<10;i++)  
12.        {  
13.            If(item == a[i])  
14.            {  
15.                Flag = i+1;  
16.                Break;  
17.            }  
18.            Else   
19.                Flag = 0;   
20.        }  
21.        If(flag != 0 )   
22.        {  
23.            Console.WriteLine("Item Found at Location " + flag);  
24.        }  
25.        Else   
26.            Console.WriteLine("Item Not Found");  
27.          
28.    }  
29. }  

Output:

Enter the item value

78

Item Found at Location 10

Enter the item value

22

Item not found

Python Program

1. Arr = [10,2,3,4,23,5,21,45,90,100];  
2. Item = int(input("Enter the item which you want to search "));  
3. For i in range (0,len(arr)):  
4.    If arr[i] == item:  
5.        Flag = i+1;  
6.        Break;  
7.    Else:   
8.        Flag = 0;   
9. If flag != 0:   
10.    Print("Item found at location %d" % (flag));  
11. Else :   
12.    Print("Item not found");  

Output:

Enter the item which you want to search 2

Item found at location 2

Enter the item which you want to search 101

Item not found

Binary Search

Binary search is the search technique which works efficiently on the sorted lists. Hence, in order to search an element into some list by using binary search technique, we must ensure that the list is sorted.

Binary search follows divide and conquer approach in which, the list is divided into two halves and the item is compared with the middle element of the list. If the match is found then, the location of middle element is returned otherwise, we search into either of the halves depending upon the result produced through the match.

Binary search algorithm is given below.

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

• Step 1: [INITIALIZE] SET BEG = lower_bound
  END = upper_bound, POS = - 1
• Step 2: Repeat Steps 3 and 4 while BEG <=END
• Step 3: SET MID = (BEG + END)/2
• Step 4: IF A[MID] = VAL
  SET POS = MID
  PRINT POS
  Go to Step 6
  ELSE IF A[MID] > VAL
  SET END = MID - 1
  ELSE
  SET BEG = MID + 1
  [END OF IF]
  [END OF LOOP]
• Step 5: IF POS = -1
  PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
  [END OF IF]
• Step 6: EXIT

Complexity

Example

Let us consider an array arr = {1, 5, 7, 8, 13, 19, 20, 23, 29}. Find the location of the item 23 in the array.

In 1st step :

1. BEG = 0   
2. END = 8ron  
3. MID = 4   
4. a[mid] = a[4] = 13 < 23, therefore  

In Second step:

1. Beg = mid +1 = 5   
2. End = 8  
3. Mid = 13/2 = 6    
4. a[mid] = a[6] = 20 < 23, therefore;   

In third step:

1. Beg = mid + 1 = 7   
2. End = 8   
3. Mid = 15/2 = 7  
4. a[mid] = a[7]   
5. a[7] = 23 = item;   
6. Therefore, set location = mid;   
7. The location of the item will be 7.   

Binary Search Program using Recursion

C program

1. #include<stdio.h>  
2. Int binarySearch(int[], int, int, int);  
3. Void main ()  
4. {  
5.    Int arr[10] = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};  
6.    Int item, location=-1;   
7.    Printf("Enter the item which you want to search ");  
8.    Scanf("%d",&item);  
9.    Location = binarySearch(arr, 0, 9, item);  
10.    If(location != -1)   
11.    {  
12.        Printf("Item found at location %d",location);  
13.    }  
14.    Else  
15.    {  
16.        Printf("Item not found");  
17.    }  
18. }   
19. Int binarySearch(int a[], int beg, int end, int item)  
20. {  
21.    Int mid;  
22.    If(end >= beg)   
23.    {     
24.        Mid = (beg + end)/2;  
25.        If(a[mid] == item)  
26.        {  
27.            Return mid+1;  
28.        }  
29.        Else if(a[mid] < item)   
30.        {  
31.            Return binarySearch(a,mid+1,end,item);  
32.        }  
33.        Else   
34.        {  
35.            Return binarySearch(a,beg,mid-1,item);  
36.        }  
37.      
38.    }  
39.    Return -1;   
40. }  

Output:

Enter the item which you want to search

19

Item found at location 2

Java

1. Import java.util.*;  
2. Public class BinarySearch {  
3. Public static void main(String[] args) {  
4.    Int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};  
5.    Int item, location = -1;  
6.    System.out.println("Enter the item which you want to search");  
7.    Scanner sc = new Scanner(System.in);  
8.    Item = sc.nextInt();  
9.    Location = binarySearch(arr,0,9,item);  
10.    If(location != -1)  
11.    System.out.println("the location of the item is "+location);  
12.    Else   
13.        System.out.println("Item not found");  
14.    }  
15. Public static int binarySearch(int[] a, int beg, int end, int item)  
16. {  
17.    Int mid;  
18.    If(end >= beg)   
19.    {     
20.        Mid = (beg + end)/2;  
21.        If(a[mid] == item)  
22.        {  
23.            Return mid+1;  
24.        }  
25.        Else if(a[mid] < item)   
26.        {  
27.            Return binarySearch(a,mid+1,end,item);  
28.        }  
29.        Else   
30.        {  
31.            Return binarySearch(a,beg,mid-1,item);  
32.        }  
33.      
34.    }  
35.    Return -1;   
36. }  
37. }  

Output:

Enter the item which you want to search

45

The location of the item is 5

C#

1. Using System;  
2.                  
3. Public class LinearSearch  
4. {  
5.    Public static void Main()  
6.    {  
7.    Int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};  
8.    Int location=-1;   
9.    Console.WriteLine("Enter the item which you want to search ");  
10.    Int item = Convert.ToInt32(Console.ReadLine());  
11.    Location = binarySearch(arr, 0, 9, item);  
12.    If(location != -1)   
13.    {  
14.        Console.WriteLine("Item found at location "+ location);  
15.    }  
16.    Else  
17.    {  
18.        Console.WriteLine("Item not found");  
19.    }  
20. }   
21. Public static int binarySearch(int[] a, int beg, int end, int item)  
22. {  
23.    Int mid;  
24.    If(end >= beg)   
25.    {     
26.        Mid = (beg + end)/2;  
27.        If(a[mid] == item)  
28.        {  
29.            Return mid+1;  
30.        }  
31.        Else if(a[mid] < item)   
32.        {  
33.            Return binarySearch(a,mid+1,end,item);  
34.        }  
35.        Else   
36.        {  
37.            Return binarySearch(a,beg,mid-1,item);  
38.        }  
39.      
40.    }  
41.    Return -1;   
42.  
43.    }  
44. }  

Output:

Enter the item which you want to search

20

Item found at location 3

Python

1. Def binarySearch(arr,beg,end,item):  
2.    If end >= beg:  
3.        Mid = int((beg+end)/2)  
4.        If arr[mid] == item :  
5.            Return mid+1  
6.        Elif arr[mid] < item :   
7.            Return binarySearch(arr,mid+1,end,item)  
8.        Else:   
9.            Return binarySearch(arr,beg,mid-1,item)  
10.    Return -1  
11.      
12.  
13. Arr=[16, 19, 20, 23, 45, 56, 78, 90, 96, 100];  
14. Item = int(input("Enter the item which you want to search ?"))  
15. Location = -1;   
16. Location = binarySearch(arr,0,9,item);  
17. If location != -1:   
18.    Print("Item found at location %d" %(location))  
19. Else:   
20.    Print("Item not found")  

Output:

Enter the item which you want to search ?

96

Item found at location 9

Enter the item which you want to search ?

101

Item not found

Binary Search function using Iteration

1. Int binarySearch(int a[], int beg, int end, int item)  
2. {  
3.    Int mid;  
4.    While(end >= beg)   
5.    {     
6.        Mid = (beg + end)/2;  
7.        If(a[mid] == item)  
8.        {  
9.            Return mid+1;  
10.        }  
11.        Else if(a[mid] < item)   
12.        {  
13.            Beg = mid + 1;  
14.        }  
15.        Else   
16.        {  
17.            End = mid - 1;   
18.        }  
19.      
20.    }  
21.    Return -1;   
22. }   

Fibonacci Series

Fibonacci series generates the subsequent number by adding two previous numbers. Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively.

Fibonacci series satisfies the following conditions −

Fn = Fn-1 + Fn-2

Hence, a Fibonacci series can look like this −

F8 = 0 1 1 2 3 5 8 13

Or, this −

F8 = 1 1 2 3 5 8 13 21

For illustration purpose, Fibonacci of F8 is displayed as −

Fibonacci Iterative Algorithm

First we try to draft the iterative algorithm for Fibonacci series.

Procedure Fibonacci(n)

Declare f0, f1, fib, loop

Set f0 to 0

Set f1 to 1

Display f0, f1

For loop ← 1 to n

Fib ← f0 + f1  

f0 ← f1

f1 ← fib

Display fib

End for

End procedure

Fibonacci Recursive Algorithm

Let us learn how to create a recursive algorithm Fibonacci series. The base criteria of recursion.

START

Procedure Fibonacci(n)

Declare f0, f1, fib, loop

Set f0 to 0

Set f1 to 1

Display f0, f1

For loop ← 1 to n

Fib ← f0 + f1  

f0 ← f1

f1 ← fib

Display fib

End for

END

2.5 Sorting methods: Bubble, insertion, Quick, Merge, shell and comparison of all sorting methods

Bubble Sort

In Bubble sort, Each element of the array is compared with its adjacent element. The algorithm processes the list in passes. A list with n elements requires n-1 passes for sorting. Consider an array A of n elements whose elements are to be sorted by using Bubble sort. The algorithm processes like following.

1. In Pass 1, A[0] is compared with A[1], A[1] is compared with A[2], A[2] is compared with A[3] and so on. At the end of pass 1, the largest element of the list is placed at the highest index of the list.
2. In Pass 2, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the end of Pass 2 the second largest element of the list is placed at the second highest index of the list.
3. In pass n-1, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the end of this pass. The smallest element of the list is placed at the first index of the list.

Algorithm :

• Step 1: Repeat Step 2 For i = 0 to N-1
• Step 2: Repeat For J = i + 1 to N - I
• Step 3: IF A[J] > A[i]
  SWAP A[J] and A[i]
  [END OF INNER LOOP]
  [END OF OUTER LOOP
• Step 4: EXIT

Complexity

C Program

1. #include<stdio.h>  
2. Void main ()  
3. {  
4.    Int i, j,temp;   
5.    Int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
6.    For(i = 0; i<10; i++)  
7.    {  
8.        For(j = i+1; j<10; j++)  
9.        {  
10.            If(a[j] > a[i])  
11.            {  
12.                Temp = a[i];  
13.                a[i] = a[j];  
14.                a[j] = temp;   
15.            }   
16.        }   
17.    }   
18.    Printf("Printing Sorted Element List ...\n");  
19.    For(i = 0; i<10; i++)  
20.    {  
21.        Printf("%d\n",a[i]);  
22.    }  
23. }  

Output:

Printing Sorted Element List . . .

7

9

10

12

23

34

34

44

78

101

C++ Program

1. #include<iostream>  
2. Using namespace std;  
3. Int main ()  
4. {  
5.    Int i, j,temp;   
6.    Int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
7.    For(i = 0; i<10; i++)  
8.    {  
9.        For(j = i+1; j<10; j++)  
10.        {  
11.            If(a[j] < a[i])  
12.            {  
13.                Temp = a[i];  
14.                a[i] = a[j];  
15.                a[j] = temp;   
16.            }   
17.        }   
18.    }   
19.    Cout <<"Printing Sorted Element List ...\n";  
20.    For(i = 0; i<10; i++)  
21.    {  
22.        Cout <<a[i]<<"\n";  
23.    }  
24.    Return 0;  
25. }  

Output:

Printing Sorted Element List ...

7

9

10

12

23

23

34

44

78

101

Java Program

1. Public class BubbleSort {  
2.    Public static void main(String[] args) {  
3.    Int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
4.    For(int i=0;i<10;i++)  
5.    {  
6.        For (int j=0;j<10;j++)  
7.        {  
8.            If(a[i]<a[j])  
9.            {  
10.                Int temp = a[i];  
11.                a[i]=a[j];  
12.                a[j] = temp;   
13.            }  
14.        }  
15.    }  
16.    System.out.println("Printing Sorted List ...");  
17.    For(int i=0;i<10;i++)  
18.    {  
19.        System.out.println(a[i]);  
20.    }  
21. }  
22. }  

Output:

Printing Sorted List . . .

7

9

10

12

23

34

34

44

78

101

C# Program

1. Using System;  
2.                      
3. Public class Program  
4. {  
5.    Public static void Main()  
6.    {  
7.        Int i, j,temp;   
8.    Int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
9.    For(i = 0; i<10; i++)  
10.    {  
11.        For(j = i+1; j<10; j++)  
12.        {  
13.            If(a[j] > a[i])  
14.            {  
15.                Temp = a[i];  
16.                a[i] = a[j];  
17.                a[j] = temp;   
18.            }   
19.        }   
20.    }   
21.    Console.WriteLine("Printing Sorted Element List ...\n");  
22.    For(i = 0; i<10; i++)  
23.    {  
24.        Console.WriteLine(a[i]);  
25.    }  
26.    }  
27. }  

Output:

Printing Sorted Element List . . .

7

9

10

12

23

34

34

44

78

101

Python Program

1. a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]  
2. For i in range(0,len(a)):  
3.    For j in range(i+1,len(a)):  
4.        If a[j]<a[i]:  
5.            Temp = a[j]  
6.            a[j]=a[i]  
7.            a[i]=temp  
8. Print("Printing Sorted Element List...")  
9. For i in a:   
10.    Print(i)  

Output:

Printing Sorted Element List . . .

7

9

10

12

23

34

34

44

78

101

Rust Program

1. Fn main()  
2. {  
3.    Let mut temp;  
4. Let mut a: [i32; 10] = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];  
5.    For i in 0..10  
6.    {  
7.        For j in (i+1)..10  
8.        {  
9.            If a[j] < a[i]  
10.            {  
11.                Temp = a[i];  
12.                a[i] = a[j];  
13.                a[j] = temp;   
14.            }  
15.        }   
16.    }   
17.    Println!("Printing Sorted Element List ...\n");  
18.    For i in &a  
19.    {  
20.        Println!("{} ",i);  
21.    }  
22. }  

Output:

Printing Sorted Element List . . .

7

9

10

12

23

34

34

44

78

101

4

JavaScript Program

1. <html>  
2. <head>  
3. <title>   
4. Bubble Sort   
5. </title>   
6. </head>   
7. <body>  
8. <script>   
9.    Var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];  
10.    For(i=0;i<10;i++)  
11.    {  
12.        For (j=0;j<10;j++)  
13.        {  
14.            If(a[i]<a[j])  
15.            {  
16.                 Temp = a[i];  
17.                a[i]=a[j];  
18.                a[j] = temp;   
19.            }  
20.        }  
21.    }  
22.    Txt = "<br>";  
23.    Document.writeln("Printing Sorted Element List ..."+txt);  
24.    For(i=0;i<10;i++)  
25.    {  
26.        Document.writeln(a[i]);  
27.        Document.writeln(txt);  
28.    }  
29.    </script>   
30.    </body>  
31. </html>  

Output:

Printing Sorted Element List ...

7

9

10

12

23

23

34

44

78

101

PHP Program

1. <html>  
2. <head>  
3. <title>Bubble Sort</title>  
4. </head>  
5. <body>  
6. <?php  
7.    $a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);  
8.    For($i=0;$i<10;$i++)  
9.    {  
10.        For ($j=0;$j<10;$j++)  
11.        {  
12.            If($a[$i]<$a[$j])  
13.            {  
14.                 $temp = $a[$i];  
15.                $a[$i]=$a[$j];  
16.                $a[$j] = $temp;   
17.            }  
18.        }  
19.    }  
20.    Echo "Printing Sorted Element List ...\n";  
21.    For($i=0;$i<10;$i++)  
22.    {  
23.        Echo $a[$i];  
24.        Echo "\n";  
25.    }  
26. ?>  
27. </body>  
28. </html>  

Output:

Printing Sorted Element List ...

7

9

10

12

23

23

34

44

78

101

Insertion Sort

Insertion sort is the simple sorting algorithm which is commonly used in the daily lives while ordering a deck of cards. In this algorithm, we insert each element onto its proper place in the sorted array. This is less efficient than the other sort algorithms like quick sort, merge sort, etc.

Technique

Consider an array A whose elements are to be sorted. Initially, A[0] is the only element on the sorted set. In pass 1, A[1] is placed at its proper index in the array.

In pass 2, A[2] is placed at its proper index in the array. Likewise, in pass n-1, A[n-1] is placed at its proper index into the array.

To insert an element A[k] to its proper index, we must compare it with all other elements i.e. A[k-1], A[k-2], and so on until we find an element A[j] such that, A[j]<=A[k].

All the elements from A[k-1] to A[j] need to be shifted and A[k] will be moved to A[j+1].

Complexity

Algorithm

• Step 1: Repeat Steps 2 to 5 for K = 1 to N-1
• Step 2: SET TEMP = ARR[K]
• Step 3: SET J = K - 1
• Step 4: Repeat while TEMP <=ARR[J]
  SET ARR[J + 1] = ARR[J]
  SET J = J - 1
  [END OF INNER LOOP]
• Step 5: SET ARR[J + 1] = TEMP
  [END OF LOOP]
• Step 6: EXIT

C Program

1. #include<stdio.h>  
2. Void main ()  
3. {  
4.    Int i,j, k,temp;  
5.    Int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
6.    Printf("\nprinting sorted elements...\n");  
7.    For(k=1; k<10; k++)   
8.    {  
9.        Temp = a[k];  
10.        j= k-1;  
11.        While(j>=0 && temp <= a[j])  
12.        {  
13.            a[j+1] = a[j];   
14.            j = j-1;  
15.        }  
16.        a[j+1] = temp;  
17.    }  
18.    For(i=0;i<10;i++)  
19.    {  
20.        Printf("\n%d\n",a[i]);  
21.    }  
22. }  

Output:

Printing Sorted Elements . . .

7

9

10

12

23

23

34

44

78

101

C++ Program

1. #include<iostream>  
2. Using namespace std;  
3. Int main ()  
4. {  
5.    Int i,j, k,temp;  
6.    Int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
7.    Cout<<"\nprinting sorted elements...\n";  
8.    For(k=1; k<10; k++)   
9.    {  
10.        Temp = a[k];  
11.        j= k-1;  
12.        While(j>=0 && temp <= a[j])  
13.        {  
14.            a[j+1] = a[j];   
15.            j = j-1;  
16.        }  
17.        a[j+1] = temp;  
18.    }  
19.    For(i=0;i<10;i++)  
20.    {  
21.        Cout <<a[i]<<"\n";  
22.    }  
23. }  

Output:

Printing sorted elements...

7

9

10

12

23

23

34

44

78

101

Java Program

1. Public class InsertionSort {  
2. Public static void main(String[] args) {  
3.    Int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
4.    For(int k=1; k<10; k++)   
5.    {  
6.        Int temp = a[k];  
7.        Int j= k-1;  
8.        While(j>=0 && temp <= a[j])  
9.        {  
10.            a[j+1] = a[j];   
11.            j = j-1;  
12.        }  
13.        a[j+1] = temp;  
14.    }  
15.    System.out.println("printing sorted elements ...");  
16.    For(int i=0;i<10;i++)  
17.    {  
18.        System.out.println(a[i]);  
19.    }  
20. }  
21. }  

Output:

Printing sorted elements . . .

7

9

10

12

23

23

34

44

78

101

C# Program

1. Using System;  
2.                      
3. Public class Program  
4. {  
5.      
6.    Public static void Main()  
7.    {  
8.        Int i,j, k,temp;  
9.        Int[] a = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
10.    Console.WriteLine("\nprinting sorted elements...\n");  
11.    For(k=1; k<10; k++)   
12.    {  
13.        Temp = a[k];  
14.        j= k-1;  
15.        While(j>=0 && temp <= a[j])  
16.        {  
17.            a[j+1] = a[j];   
18.            j = j-1;  
19.        }  
20.        a[j+1] = temp;  
21.    }  
22.    For(i=0;i<10;i++)  
23.    {  
24.        Console.WriteLine(a[i]);  
25.    }  
26. }  
27. }  

Output:

Printing sorted elements . . .

7

9

10

12

23

23

34

44

78

101

Python Program

1. a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]  
2. For k in range(1,10):  
3.    Temp = a[k]   
4.    j = k-1  
5.    While j>=0 and temp <=a[j]:  
6.        a[j+1]=a[j]  
7.        j = j-1  
8.    a[j+1] = temp   
9. Print("printing sorted elements...")  
10. For i in a:  
11.    Print(i)  

Output:

Printing sorted elements . . .

7

9

10

12

23

23

34

44

78

101

Swift Program

1. Import Foundation  
2. Import Glibc  
3.    Var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];   
4.    Print("\nprinting sorted elements...\n");  
5.    For k in 1...9  
6.    {  
7.        Let temp = a[k];  
8.        Var j = k-1;  
9.        While j>=0 && temp <= a[j]  
10.        {  
11.            a[j+1] = a[j];   
12.            j = j-1;  
13.        }  
14.          
15.        a[j+1] = temp;  
16.    }  
17.    For i in a  
18.    {  
19.        Print(i);  
20.    }     

Output:

Printing sorted elements...

7

9

10

12

23

23

34

44

78

101

JavaScript Program

1. <html>  
2. <head>  
3. <title>   
4.    Insertion Sort   
5. </title>   
6.    </head>  
7.    <body>   
8.        <script>   
9.                Var txt = "<br>";  
10.            Var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];  
11.            Document.writeln("printing sorted elements ... "+txt);  
12.            For(k=0;k<10;k++)  
13.            {  
14.                Var temp = a[k]  
15.                j=k-1;  
16.                While (j>=0 && temp <= a[j])  
17.                {  
18.                    a[j+1] = a[j];   
19.                    jj = j-1;  
20.                }  
21.                a[j+1] = temp;  
22.            }  
23.          
24.            For(i=0;i<10;i++)  
25.            {  
26.                Document.writeln(a[i]);  
27.                Document.writeln(txt);  
28.            }  
29.        </script>   
30.    </body>  
31. </html>  

Output:

Printing sorted elements ...

7

9

10

12

23

23

34

44

78

101

PHP Program

1. <html>  
2. <head>  
3. <title>Insertion Sort</title>  
4. </head>  
5. <body>  
6. <?php  
7. $a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);  
8.            Echo("printing sorted elements ... \n");  
9.            For($k=0;$k<10;$k++)  
10.            {  
11.                $temp = $a[$k];  
12.                $j=$k-1;  
13.                While ($j>=0 && $temp <= $a[$j])  
14.                {  
15.                    $a[$j+1] = $a[$j];   
16.                    $j = $j-1;  
17.                }  
18.                $a[$j+1] = $temp;  
19.            }  
20.            For($i=0;$i<10;$i++)  
21.            {  
22.                Echo $a[$i];  
23.                Echo "\n";  
24.            }  
25. ?>  
26. </body>  
27. </html>  

Output:

Printing sorted elements ...

7

9

10

12

23

23

34

44

78

101

Quick Sort

Quick sort is the widely used sorting algorithm that makes n log n comparisons in average case for sorting of an array of n elements. This algorithm follows divide and conquer approach. The algorithm processes the array in the following way.

1. Set the first index of the array to left and loc variable. Set the last index of the array to right variable. i.e. left = 0, loc = 0, en d = n - 1, where n is the length of the array.
2. Start from the right of the array and scan the complete array from right to beginning comparing each element of the array with the element pointed by loc.

Ensure that, a[loc] is less than a[right].

1. If this is the case, then continue with the comparison until right becomes equal to the loc.
2. If a[loc] > a[right], then swap the two values. And go to step 3.
3. Set, loc = right

1. Start from element pointed by left and compare each element in its way with the element pointed by the variable loc. Ensure that a[loc] > a[left]
   1. If this is the case, then continue with the comparison until loc becomes equal to left.
   2. [loc] < a[right], then swap the two values and go to step 2.
   3. Set, loc = left.

Complexity

Algorithm

PARTITION (ARR, BEG, END, LOC)

• Step 1: [INITIALIZE] SET LEFT = BEG, RIGHT = END, LOC = BEG, FLAG =
• Step 2: Repeat Steps 3 to 6 while FLAG =
• Step 3: Repeat while ARR[LOC] <=ARR[RIGHT]
  AND LOC != RIGHT
  SET RIGHT = RIGHT - 1
  [END OF LOOP]
• Step 4: IF LOC = RIGHT
  SET FLAG = 1
  ELSE IF ARR[LOC] > ARR[RIGHT]
  SWAP ARR[LOC] with ARR[RIGHT]
  SET LOC = RIGHT
  [END OF IF]
• Step 5: IF FLAG = 0
  Repeat while ARR[LOC] >= ARR[LEFT] AND LOC != LEFT
  SET LEFT = LEFT + 1
  [END OF LOOP]
• Step 6:IF LOC = LEFT
  SET FLAG = 1
  ELSE IF ARR[LOC] < ARR[LEFT]
  SWAP ARR[LOC] with ARR[LEFT]
  SET LOC = LEFT
  [END OF IF]
  [END OF IF]
• Step 7: [END OF LOOP]
• Step 8: END

QUICK_SORT (ARR, BEG, END)

• Step 1: IF (BEG < END)
  CALL PARTITION (ARR, BEG, END, LOC)
  CALL QUICKSORT(ARR, BEG, LOC - 1)
  CALL QUICKSORT(ARR, LOC + 1, END)
  [END OF IF]
• Step 2: END

C Program

1. #include <stdio.h>  
2. Int partition(int a[], int beg, int end);  
3. Void quickSort(int a[], int beg, int end);  
4. Void main()  
5. {  
6.    Int i;  
7.    Int arr[10]={90,23,101,45,65,23,67,89,34,23};  
8.    QuickSort(arr, 0, 9);  
9.    Printf("\n The sorted array is: \n");  
10.    For(i=0;i<10;i++)  
11.    Printf(" %d\t", arr[i]);  
12. }  
13. Int partition(int a[], int beg, int end)  
14. {  
15.      
16.    Int left, right, temp, loc, flag;     
17.    Loc = left = beg;  
18.    Right = end;  
19.    Flag = 0;  
20.    While(flag != 1)  
21.    {  
22.        While((a[loc] <= a[right]) && (loc!=right))  
23.        Right--;  
24.        If(loc==right)  
25.        Flag =1;  
26.        Else if(a[loc]>a[right])  
27.        {  
28.            Temp = a[loc];  
29.            a[loc] = a[right];  
30.            a[right] = temp;  
31.            Loc = right;  
32.        }  
33.        If(flag!=1)  
34.        {  
35.            While((a[loc] >= a[left]) && (loc!=left))  
36.            Left++;  
37.            If(loc==left)  
38.            Flag =1;  
39.            Else if(a[loc] <a[left])  
40.            {  
41.                Temp = a[loc];  
42.                a[loc] = a[left];  
43.                a[left] = temp;  
44.                Loc = left;  
45.            }  
46.        }  
47.    }  
48.    Return loc;  
49. }  
50. Void quickSort(int a[], int beg, int end)  
51. {  
52.      
53.    Int loc;  
54.    If(beg<end)  
55.    {  
56.        Loc = partition(a, beg, end);  
57.        QuickSort(a, beg, loc-1);  
58.        QuickSort(a, loc+1, end);  
59.    }  
60. }  

Output:

The sorted array is:

23

23

23

34

45

65

67

89

90

101

Java Program

1. Public class QuickSort {  
2. Public static void main(String[] args) {  
3.        Int i;  
4.        Int[] arr={90,23,101,45,65,23,67,89,34,23};  
5.        QuickSort(arr, 0, 9);  
6.        System.out.println("\n The sorted array is: \n");  
7.        For(i=0;i<10;i++)  
8.        System.out.println(arr[i]);  
9.    }  
10.    Public static int partition(int a[], int beg, int end)  
11.    {  
12.          
13.        Int left, right, temp, loc, flag;     
14.        Loc = left = beg;  
15.        Right = end;  
16.        Flag = 0;  
17.        While(flag != 1)  
18.        {  
19.            While((a[loc] <= a[right]) && (loc!=right))  
20.            Right--;  
21.            If(loc==right)  
22.            Flag =1;  
23.            Elseif(a[loc]>a[right])  
24.            {  
25.                Temp = a[loc];  
26.                a[loc] = a[right];  
27.                a[right] = temp;  
28.                Loc = right;  
29.            }  
30.            If(flag!=1)  
31.            {  
32.                While((a[loc] >= a[left]) && (loc!=left))  
33.                Left++;  
34.                If(loc==left)  
35.                Flag =1;  
36.                Elseif(a[loc] <a[left])  
37.                {  
38.                    Temp = a[loc];  
39.                    a[loc] = a[left];  
40.                    a[left] = temp;  
41.                    Loc = left;  
42.                }  
43.            }  
44.        }  
45.        Returnloc;  
46.    }  
47.    Static void quickSort(int a[], int beg, int end)  
48.    {  
49.          
50.        Int loc;  
51.        If(beg<end)  
52.        {  
53.            Loc = partition(a, beg, end);  
54.            QuickSort(a, beg, loc-1);  
55.            QuickSort(a, loc+1, end);  
56.        }  
57.    }  
58. }  

Output:

The sorted array is:

23

23

23

34

45

65

67

89

90

101

C# Program

1. Using System;  
2. Public class QueueSort{  
3. Public static void Main() {  
4.        Int i;  
5.        Int[] arr={90,23,101,45,65,23,67,89,34,23};  
6.        QuickSort(arr, 0, 9);  
7.        Console.WriteLine("\n The sorted array is: \n");  
8.        For(i=0;i<10;i++)  
9.        Console.WriteLine(arr[i]);  
10.    }  
11.    Public static int partition(int[] a, int beg, int end)  
12.    {  
13.          
14.        Int left, right, temp, loc, flag;     
15.        Loc = left = beg;  
16.        Right = end;  
17.        Flag = 0;  
18.        While(flag != 1)  
19.        {  
20.            While((a[loc] <= a[right]) && (loc!=right))  
21.            Right--;  
22.            If(loc==right)  
23.            Flag =1;  
24.            Else if(a[loc]>a[right])  
25.            {  
26.                Temp = a[loc];  
27.                a[loc] = a[right];  
28.                a[right] = temp;  
29.                Loc = right;  
30.            }  
31.            If(flag!=1)  
32.            {  
33.                While((a[loc] >= a[left]) && (loc!=left))  
34.                Left++;  
35.                If(loc==left)  
36.                Flag =1;  
37.                Else if(a[loc] <a[left])  
38.                {  
39.                    Temp = a[loc];  
40.                    a[loc] = a[left];  
41.                    a[left] = temp;  
42.                    Loc = left;  
43.                }  
44.            }  
45.        }  
46.        Return loc;  
47.    }  
48.    Static void quickSort(int[] a, int beg, int end)  
49.    {  
50.          
51.        Int loc;  
52.        If(beg<end)  
53.        {  
54.            Loc = partition(a, beg, end);  
55.            QuickSort(a, beg, loc-1);  
56.            QuickSort(a, loc+1, end);  
57.        }  
58.    }  
59. }  

Output:

The sorted array is:

23

23

23

34

45

65

67

89

90

101

Merge sort

Merge sort is the algorithm which follows divide and conquer approach. Consider an array A of n number of elements. The algorithm processes the elements in 3 steps.

1. If A Contains 0 or 1 elements then it is already sorted, otherwise, Divide A into two sub-array of equal number of elements.
2. Conquer means sort the two sub-arrays recursively using the merge sort.
3. Combine the sub-arrays to form a single final sorted array maintaining the ordering of the array.

The main idea behind merge sort is that, the short list takes less time to be sorted.

Complexity

Example :

Consider the following array of 7 elements. Sort the array by using merge sort.

1. A = {10, 5, 2, 23, 45, 21, 7}  

Algorithm

• Step 1: [INITIALIZE] SET I = BEG, J = MID + 1, INDEX = 0
• Step 2: Repeat while (I <= MID) AND (J<=END)
  IF ARR[I] < ARR[J]
  SET TEMP[INDEX] = ARR[I]
  SET I = I + 1
  ELSE
  SET TEMP[INDEX] = ARR[J]
  SET J = J + 1
  [END OF IF]
  SET INDEX = INDEX + 1
  [END OF LOOP]
  Step 3: [Copy the remaining
  elements of right sub-array, if
  any]
  IF I > MID
  Repeat while J <= END
  SET TEMP[INDEX] = ARR[J]
  SET INDEX = INDEX + 1, SET J = J + 1
  [END OF LOOP]
  [Copy the remaining elements of
  left sub-array, if any]
  ELSE
  Repeat while I <= MID
  SET TEMP[INDEX] = ARR[I]
  SET INDEX = INDEX + 1, SET I = I + 1
  [END OF LOOP]
  [END OF IF]
• Step 4: [Copy the contents of TEMP back to ARR] SET K = 0
• Step 5: Repeat while K < INDEX
  SET ARR[K] = TEMP[K]
  SET K = K + 1
  [END OF LOOP]
• Step 6: Exit

MERGE_SORT(ARR, BEG, END)

• Step 1: IF BEG < END
  SET MID = (BEG + END)/2
  CALL MERGE_SORT (ARR, BEG, MID)
  CALL MERGE_SORT (ARR, MID + 1, END)
  MERGE (ARR, BEG, MID, END)
  [END OF IF]
• Step 2: END

C Program

1. #include<stdio.h>  
2. Void mergeSort(int[],int,int);  
3. Void merge(int[],int,int,int);  
4. Void main ()  
5. {  
6.    Int a[10]= {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
7.    Int i;  
8.    MergeSort(a,0,9);  
9.    Printf("printing the sorted elements");  
10.    For(i=0;i<10;i++)  
11.    {  
12.        Printf("\n%d\n",a[i]);  
13.    }  
14.      
15. }  
16. Void mergeSort(int a[], int beg, int end)  
17. {  
18.    Int mid;  
19.    If(beg<end)  
20.    {  
21.        Mid = (beg+end)/2;  
22.        MergeSort(a,beg,mid);  
23.        MergeSort(a,mid+1,end);  
24.        Merge(a,beg,mid,end);  
25.    }  
26. }  
27. Void merge(int a[], int beg, int mid, int end)  
28. {  
29.    Int i=beg,j=mid+1,k,index = beg;  
30.    Int temp[10];  
31.    While(i<=mid && j<=end)  
32.    {  
33.        If(a[i]<a[j])  
34.        {  
35.            Temp[index] = a[i];  
36.            i = i+1;  
37.        }  
38.        Else   
39.        {  
40.            Temp[index] = a[j];  
41.            j = j+1;   
42.        }  
43.        Index++;  
44.    }  
45.    If(i>mid)  
46.    {  
47.        While(j<=end)  
48.        {  
49.            Temp[index] = a[j];  
50.            Index++;  
51.            j++;  
52.        }  
53.    }  
54.    Else   
55.    {  
56.        While(i<=mid)  
57.        {  
58.            Temp[index] = a[i];  
59.            Index++;  
60.            i++;  
61.        }  
62.    }  
63.    k = beg;  
64.    While(k<index)  
65.    {  
66.        a[k]=temp[k];  
67.        k++;  
68.    }  
69. }  

Output:

Printing the sorted elements

7

9

10

12

23

23

34

44

78

101

Java Program

1. Public class MyMergeSort  
2. {  
3. Void merge(int arr[], int beg, int mid, int end)  
4. {  
5.  
6. Int l = mid - beg + 1;  
7. Int r = end - mid;  
8.  
9. IntLeftArray[] = new int [l];  
10. IntRightArray[] = new int [r];  
11.  
12. For (int i=0; i<l; ++i)  
13. LeftArray[i] = arr[beg + i];  
14.  
15. For (int j=0; j<r; ++j)  
16. RightArray[j] = arr[mid + 1+ j];  
17.  
18.  
19. Int i = 0, j = 0;  
20. Int k = beg;  
21. While (i<l&&j<r)  
22. {  
23. If (LeftArray[i] <= RightArray[j])  
24. {  
25. Arr[k] = LeftArray[i];  
26. i++;  
27. }  
28. Else  
29. {  
30. Arr[k] = RightArray[j];  
31. j++;  
32. }  
33. k++;  
34. }  
35. While (i<l)  
36. {  
37. Arr[k] = LeftArray[i];  
38. i++;  
39. k++;  
40. }  
41.  
42. While (j<r)  
43. {  
44. Arr[k] = RightArray[j];  
45. j++;  
46. k++;  
47. }  
48. }  
49.  
50. Void sort(int arr[], int beg, int end)  
51. {  
52. If (beg<end)  
53. {  
54. Int mid = (beg+end)/2;  
55. Sort(arr, beg, mid);  
56. Sort(arr , mid+1, end);  
57. Merge(arr, beg, mid, end);  
58. }  
59. }  
60. Public static void main(String args[])  
61. {  
62. Intarr[] = {90,23,101,45,65,23,67,89,34,23};  
63. MyMergeSort ob = new MyMergeSort();  
64. Ob.sort(arr, 0, arr.length-1);  
65.  
66. System.out.println("\nSorted array");  
67. For(int i =0; i<arr.length;i++)  
68. {  
69.    System.out.println(arr[i]+"");  
70. }  
71. }  
72. }  

Output:

Sorted array

23

23

23

34

45

65

67

89

90

101

C# Program

1. Using System;  
2. Public class MyMergeSort  
3. {  
4. Void merge(int[] arr, int beg, int mid, int end)  
5. {  
6.  
7. Int l = mid - beg + 1;  
8. Int r = end - mid;  
9.        Int i,j;  
10.  
11. Int[] LeftArray = new int [l];  
12. Int[] RightArray = new int [r];  
13.  
14. For (i=0; i<l; ++i)  
15. LeftArray[i] = arr[beg + i];  
16.  
17. For (j=0; j<r; ++j)  
18. RightArray[j] = arr[mid + 1+ j];  
19.  
20.  
21. i = 0; j = 0;  
22. Int k = beg;  
23. While (i < l && j < r)  
24. {  
25. If (LeftArray[i] <= RightArray[j])  
26. {  
27. Arr[k] = LeftArray[i];  
28. i++;  
29. }  
30. Else  
31. {  
32. Arr[k] = RightArray[j];  
33. j++;  
34. }  
35. k++;  
36. }  
37. While (i < l)  
38. {  
39. Arr[k] = LeftArray[i];  
40. i++;  
41. k++;  
42. }  
43.  
44. While (j < r)  
45. {  
46. Arr[k] = RightArray[j];  
47. j++;  
48. k++;  
49. }  
50. }  
51.  
52. Void sort(int[] arr, int beg, int end)  
53. {  
54. If (beg < end)  
55. {  
56. Int mid = (beg+end)/2;  
57. Sort(arr, beg, mid);  
58. Sort(arr , mid+1, end);  
59. Merge(arr, beg, mid, end);  
60. }  
61. }  
62. Public static void Main()  
63. {  
64. Int[] arr = {90,23,101,45,65,23,67,89,34,23};  
65. MyMergeSort ob = new MyMergeSort();  
66. Ob.sort(arr, 0, 9);  
67.  
68. Console.WriteLine("\nSorted array");  
69. For(int i =0; i<10;i++)  
70. {  
71.    Console.WriteLine(arr[i]+"");  
72. }  
73. }  
74. }