hi,
i am new to C
i would like to know the seraching and sorting algorithm codes in c and how does it works.
hi,
i am new to C
i would like to know the seraching and sorting algorithm codes in c and how does it works.
What can we offer you that a google search on searching and sorting won't give you?
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
The Art of Computer Programming, Volume 3 is a good resource.
There are many sorting algorithms. The most popular one's are:
Quicksort: fastest general purpose sorter. Can be extensively optimized.
Merge Sort: Very close to Quicksort's speed, easily adapted to sorting slower sequential input (tape drives), etc.
Insertion Sort: fastest sorter for very small quantities of data, and data that is already in nearly sorted order. Stable - meaning you can sort data that is "on-line", without going off line. Bogs down with more than 75 items, in my PC. Commonly used to optimize Quicksort, where it handles small sub-arrays.
Radix Sort: Unlike all the above, no comparisons need to be made for this sort. Two varieties: most (MSB) and least (LSB) significant bit. Can be combined with Quicksort to make a REALLY fast string sorter (MSB).
Heap Sort: Also quick, but it's sterling quality is that it absolutely will sort the number of items in the same amount of time, regardless of any characteristics of the input data.
For searching, the most common, and generally best, is the binary search. After a mid-point is arithmetically found, a guess at that mid point is made. Since the data being searched MUST be in sorted order, the comparison made to that mid-point, will either be the item being searched for, OR the item being searched for will be found to be lower or higher than the mid-point guess.
If it's higher, the floor of the search space is raised to one above the mid-point. If it's lower, the ceiling of the search space is lowered to one below the current mid-point. That effectively cuts the search space in half, with every pass (guess) it makes as it loops through the search space. If the floor and ceiling cross each other, (the floor in now greater than the ceiling index in the array), then the item is not in the array, and the search ends with a return indicating not found.
I've been a fan of an indexed search for years, but in my latest test, it could not make any significant improvement over a binary search - unlike it had in previous years. The difference was in an upgrade of the PC's hardware to 64 bit and larger cache memory on both the cpu and hard drive buffer.
There is a lot more info on Wikipedia.