sorting in c
Sorting in general refers to various methods of arranging or ordering things based on criterias (numerical, chronological, alphabetical, heirarchial etc.). In Computer Science, due to obvious reasons, Sorting (of data) is of immense importance and is one of the most extensively researched subjects. It is one of the most fundamental algorithmic problems. So much so that it is also fundmental to many other fundamental algorithmic problems such as search algorithms, merge algorithms etc. It is estimated that around 25% of all CPU cycles are used to sort data. There are many approaches to sorting data and each has its own merits and demerits. This article discusses some of the common sorting algorithms.
Bubble Sort
Bubble Sort is probably one of the oldest, most easiest, straight-forward, inefficient sorting algorithms. It is the algorithm introduced as a sorting routine in most introductory courses on Algorithms. Bubble Sort works by comparing each element of the list with the element next to it and swapping them if required. With each pass, the largest of the list is “bubbled” to the end of the list whereas the smaller values sink to the bottom. It is similar to selection sort although not as straight forward. Instead of “selecting” maximum values, they are bubbled to a part of the list.
Selection Sort
The idea of Selection Sort is rather simple. It basically determines the minimum (or maximum) of the list and swaps it with the element at the index where its supposed to be. The process is repeated such that the nth minimum (or maximum) element is swapped with the element at the n-1th index of the list. The below is an implementation of the algorithm in C.
Insertion Sort
The Insertion Sort algorithm is a commonly used algorithm. Even if you haven’t been a programmer or a student of computer science, you may have used this algorithm. Try recalling how you sort a deck of cards. You start from the begining, traverse through the cards and as you find cards misplaced by precedence you remove them and insert them back into the right position. Eventually what you have is a sorted deck of cards. The same idea is applied in the Insertion Sort algorithm
Heap Sort
Heap sort algorithm, as the name suggests, is based on the concept of heaps. It begins by constructing a special type of binary tree, called heap, out of the set of data which is to be sorted. Note:
- A Heap by definition is a special type of binary tree in which each node is greater than any of its descendants. It is a complete binary tree.
- A semi-heap is a binary tree in which all the nodes except the root possess the heap property.
- If N be the number of a node, then its left child is 2*N and the right child 2*N+1.
The root node of a Heap, by definition, is the maximum of all the elements in the set of data, constituting the binary tree. Hence the sorting process basically consists of extracting the root node and reheaping the remaining set of elements to obtain the next largest element till there are no more elements left to heap. Elemetary implementations usually employ two arrays, one for the heap and the other to store the sorted data. But it is possible to use the same array to heap the unordered list and compile the sorted list. This is usually done by swapping the root of the heap with the end of the array and then excluding that element from any subsequent reheaping.
Significance of a semi-heap – A Semi-Heap as mentioned above is a Heap except that the root does not possess the property of a heap node. This type of a heap is significant in the discussion of Heap Sorting, since after each “Heaping” of the set of data, the root is extracted and replaced by an element from the list. This leaves us with a Semi-Heap. Reheaping a Semi-Heap is particularily easy since all other nodes have already been heaped and only the root node has to be shifted downwards to its right position
shell sort
An inventor called DL Shell came up with a very interesting sort which he called shell sort. This sorting algorithm is almost similar to the bubble sort algorithm. The shell sort compares elements that are a certain distance away (d positions away) from each other and it compares these elements repeatedly (bubble sort only compares adjacent elements.) It uses the equation d = (n + 1) / 2.
The comparison model makes the sorting process of the shell sort very efficient.
Quick sort
Make a list of items that need to be sorted, lets apply in an array.Choose any element as pivot element from the array list.(Complexity largely depends on choosing the pivot element).Rearrange the array list so that all the elements with value less than the pivot will come before the pivot and the element with value greater will come after the pivot with in the same array, which make pivot element in the sorted position.(If the reverse the order we are reversing the sorting order that is descending). Apply recursively the 3rd step to the sub array of the element with smaller values and separate the sub array of the elements with the greater values.
Merge Sort
Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merg() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following C implementation for details.
related links….