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!

Quote:

---

Originally Posted by fedya

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.

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?

This part is a logical contradiction:

Quote:

---

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.