Thread: Question 39: Quicksort vs Linear Search

  1. #1
    UT2004 Addict Kleid-0's Avatar
    Join Date
    Dec 2004
    Posts
    656

    Question 39: Quicksort vs Linear Search

    Would you rather wait for the results of a quicksort, a linear search, or a bubble sort on a 200000 element array?

    Quicksort
    Linear Search
    Bubble Sort
    The answer is linear search but I believe this question is hard to answer because I don't know if the results are coming from a sorting algorithm or a search. If we're talking about a sort the answer would be quicksort, and if we're searching it would obviously be linear search, am I right?

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    A linear search is O(n). Quick sort is O(n log(n)) [in its best case]. Bubble sort is O(n^2).

    Which is the shortest of those three? O(n)

    Whether your searching or sorting is irrelevant. The point of the question is to see which algorithm runs in the fastest time.

  3. #3
    It's full of stars adrianxw's Avatar
    Join Date
    Aug 2001
    Posts
    4,829
    <pedant>Without a statement that says the dataset is not in order, the question is meaningless.</pedant>
    Wave upon wave of demented avengers march cheerfully out of obscurity unto the dream.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  2. Search Engines :: Winsock
    By kuphryn in forum Windows Programming
    Replies: 3
    Last Post: 06-18-2002, 12:31 PM
  3. Again Character Count, Word Count and String Search
    By client in forum C Programming
    Replies: 2
    Last Post: 05-09-2002, 11:40 AM
  4. Linear search and 2d arrays?
    By sven in forum C Programming
    Replies: 0
    Last Post: 02-08-2002, 05:26 AM
  5. Linear Search: the recursive way.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 01-15-2002, 03:15 AM