Sorting

Bodhak sorting using c tutorial in this chapter we will discuss Sorting of  Data Structures. The concepts are explained with programs.

We encounter several applications that require an ordered list. So it is required to order the elements of a given list either in ascending/increasing order or descending/decreasing order, as per the requirement. This process is called sorting.

 

sorting using c

There are many techniques available for sorting an array-based list. These techniques differ in their time and space complexities. Some of the important sorting techniques are discussed here.

Selection Sort:

The list is divided into two sublists, sorted and unsorted,  which are divided by an imaginary wall.

We find the smallest element from the unsorted sublist and swap it with the element at the beginning of the unsorted data.

After each selection and swapping, the imaginary wall between the two sub-lists moves one element ahead, increasing the number of sorted elements and decreasing the number of unsorted ones.

Each time we move one element from the unsorted sub list to the sorted sublist, we say that we have completed a sort pass.

A list of n elements requires n-1 passes to completely rearrange the data

Quick Sort:

The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:

Choose a pivot value. We take the value of the middle element as pivot value, but it can be any value, which is in a range of sorted values, even if it doesn’t present in the array.

Partition. Rearrange elements in such a way, that all elements which are lesser than the pivot goes to the left part of the array and all elements greater than the pivot, go to the right part of the array. Values equal to the pivot can stay in any part of the array. Notice, that array may be divided into non-equal parts.

Sort both parts. Apply quick sort algorithm recursively to the left and the right parts.