Computer Fundamentals with C and Unix
(Searching, Sorting)
Lecture 06: Jan. 05, 2023 Prof. K.R. Chowdhary : Professor of CS

Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications. They may be distributed outside this class only with the permission of the Instructor.

6.1 Linear Search through many arrays

Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set. It is the easiest searching algorithm.

Below is the implementation of the above approach

Follow the given steps to solve the problem:

• Start from the leftmost element of arr[] and one by one compare x with each element of arr[]

• If x matches with an element, return the index.

• If x does not match with any of the elements, return -1.

6.2 Sorting of an array

The process of Sorting can be explained as a technique of rearranging the elements in any particular order, which can be set ready for further processing by the program logic. In C programming language, there are multiple sorting algorithms available, which can be incorporated inside the code. The various types of sorting methods possible in the C language are Bubble sort, Selection sort, Quick sort, Merge sort, Heap sort and Insertion sort.

Sorting is a process of ordering individual elements of a list according to their proper rank, either in ascending or descending order. A programming logic with few steps which can sort a bunch of elements are called sorting algorithms. Different types of sorting algorithms have different logics and steps. C programming language is the best to start understanding sorting algorithms. However, sorting algorithms are not limited to C programming language. These can be implemented by any programming languages like C++, C#, JAVA, Python, Javascript, Objective C etc. We can easily sort a list of elements by means of iterations and condition check statements. We require one outer loop and one inner loop and one swap function to do the purpose. Let us implement below steps to understand a simple sorting logic.

The Bubble sort is the most common type of sort, using this we can order the elements in ascending order or descending order. It is the simplest sorting technique which is also called as an exchange sort.

Procedure:

1. Compare the first element with the remaining elements in the list and exchange(swap) them if they are not in order.

2. Repeat the same for other elements in the list until all the elements gets sorted.

The program in Fig. 6.3 sorts an array of integers in ascending order.

The Fig. 6.4 shows the original array, and next the array after it is sorted using bubble sort.

In Fig. 6.5 we have two arrays, one is employee number (empno) and other is employee names. These are related, in the sense each row belong to one employee. So, if we want to sort the employee in ascending order, then the rows are to be sorted. In other words, for each row the employee number (empno) is key.

The Fig 6.6 shows the running of program shown in Fig. 6.5.

6.2.1 Sorting with name as keyword

In program shown in Fig. 6.7 row elements of two arrays in the same row are treated as joint, as they are together called record. Since we will treat employee name as a key, we shall compare this key for two rows and order the rows such that alphabetically lower name appears in the previous row, and higher in the next row.

The Fig. 6.8 shows the run results of program in Fig. 6.7.