Thread: Ordering without sorting algorithm

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    3

    Ordering without sorting algorithm

    Hello guys, I've got a question related to my data structures class.

    I have file in which data is unordered. Say:

    hello program
    red apple
    blue sky
    new phone
    old number

    I have to search a string using Binary Search. But since we cannot apply Binary Search to unordered list, we should make an ordered list using some sorting algorithms.

    However, main point of my assignment is making an ordered list without using any sorting algorithms and then apply Binary Search.

    Any ideas how to do that?

    Any help will be highly appreciated!

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by fedya View Post
    However, main point of my assignment is making an ordered list without using any sorting algorithms and then apply Binary Search.
    If you take an unordered list and give it order in a computer program, you have used a sorting algorithm, whether it's one learn or one you just make up. Actually, going by the dictionary definition of "algorithm" (a step-by-step problem-solving procedure), this is true whether or not you do it with a computer program: if you solve problem in a sequence of steps (which you would have to do to reorder a list), that sequence of steps can be described as an algorithm.
    Last edited by MK27; 11-27-2009 at 10:57 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I believe your teacher wants you to NOT sort the items, but yet make an ordered list.

    You can do that, by sorting an index which is associated with the items. The items themselves are not sorted in any way - they stay in their original positions.

    After sorting through an index, you can use the index to conduct your binary search, with no problem at all.

    It will stretch your brain a bit, but that's the fun of programming anyway.

    The first step is quite simple, you make an int array, the same size as the number of items you have in your list, and give each element of the array, an initial value:

    Code:
    int i;
    int a[numItems];  //numItems might be 10, 50, or whatever
    
    for(i = 0; i < numItems; i++)
       a[i] = i;
    so that was ez squeezy.

    I've got a tree trimmer working a chain saw right outside my window, so I have to take a break. I'll be back when he's done giving me an earache.

    Now the indexes are set, and we're ready to sort - but with this twist - we compare the original strings to each other, THROUGH THE INDEX array. We *MOVE* only the index.

    This is a simple sort, which moves the original items:
    Code:
    for(i = 0; i < numItems - 1; i++) {
      for(j = i+1; j < numItems; j++) {
        if(a[i] > a[j] {
          temp = a[i];
          a[i] = a[j];
          a[j] = temp;
        }
      }
    }
    
    //here's the same sort, but leaving the original items alone, and moving the index, instead:
    for(i = 0; i < numItems - 1; i++) {
      for(j = i+1; j < numItems; j++) {
        if(a[index[i]] > a[index[j]] {  //comparisons are made through the index array
          temp = index[i];
          index[i] = index[j];
          index[j] = temp;
        }
      }
    }
    Does this sound like what you need?
    Last edited by Adak; 11-27-2009 at 01:13 PM.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    This part is a logical contradiction:
    making an ordered list without using any sorting algorithms
    However I believe that what you want is a non in-place sort. I.e. one that doesn't move any of the original data but produces a sorted copy, or in this case a sorted index list of the data as Adak describes.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. *Help*in sorting and searching algorithm
    By yuentong in forum C++ Programming
    Replies: 1
    Last Post: 03-07-2009, 10:43 AM
  2. Efficient Sorting Algorithm
    By GCNDoug in forum C++ Programming
    Replies: 10
    Last Post: 11-13-2008, 09:06 AM
  3. Sorting Algorithm Help
    By cjwenigma in forum C++ Programming
    Replies: 8
    Last Post: 11-02-2007, 02:04 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. which sorting algorithm for GBs of data?
    By Sargnagel in forum C Programming
    Replies: 4
    Last Post: 06-05-2003, 08:43 AM