Thread: c program for serach and sort techniques

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    1

    c program for serach and sort techniques

    hi,
    i am new to C
    i would like to know the seraching and sorting algorithm codes in c and how does it works.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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"

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    200
    The Art of Computer Programming, Volume 3 is a good resource.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. serach for a little help
    By roelof in forum C Programming
    Replies: 35
    Last Post: 05-13-2011, 03:38 PM
  2. techniques for optimising a for loop..
    By underthesun in forum C Programming
    Replies: 3
    Last Post: 01-26-2010, 11:40 PM
  3. How to empty a Binary Serach Tree???
    By ripper079 in forum C++ Programming
    Replies: 6
    Last Post: 01-29-2003, 09:28 AM
  4. Best techniques to learn C
    By swiftfire in forum C Programming
    Replies: 1
    Last Post: 12-04-2002, 12:16 PM
  5. Relaxation techniques
    By RobS in forum A Brief History of Cprogramming.com
    Replies: 9
    Last Post: 05-10-2002, 10:35 PM