Sorting Strings with int Sort: Explained + Tips

[Lancelot59]

Hi there PF. For this problem I need to take the following code which apparently sorts an array with integers, and sort strings instead. However I DO NOT understand how this works for integers, much less how I could make it work for strings. Could someone please explain it to me? A few tips to get me started on the string sorting would be appreciated too.

void selectionSort(int array[], int size)
 {
    int startScan, minIndex, minValue;
 
    for (startScan = 0; startScan < (size - 1); startScan++)
    {
       minIndex = startScan;
       minValue = array[startScan];
       for(int index = startScan + 1; index < size; index++)
      {
          if (array[index] < minValue)
        {
             minValue = array[index];
             minIndex = index;
        }
     }
       array[minIndex] = array[startScan];
       array[startScan] = minValue;
    }
 }

There are some similar problems I might be popping in with later on, but I figure this is the best place to start.

 

[Robbert]

SelectionSort is a sorting technique which runs in O(n²) time, meaning that it's inefficient for large lists.

That aside, it works like this:
1. Find the lowest value in the unsorted list
2. Place it at the end of the sorted list
3. Repeat for remainder of the unsorted list

Your outer loop is basically a way to keep track of where the ordered part of the array ends. The variable startScan tells the second loop where to start scanning for the lowest value in the unordered list, and thus is the start of the unordered part of your array.

The second loop finds the smallest value in the unordered part of the array. Once found, which it will never know until it reaches the end, th algorithm swaps with the first unsorted element, which is at the index that startScan contains. If our previous list had n sorted elements, it now has n+1 sorted elements.

Then counter is incremented and the process is repeated.

You can do this with any data type, as long as it's comparable (and strings are comparable in most OO languages!)

 

[Lancelot59]

Alright, it makes a bit more sense now.

This screenshot attached is for a question further down the assignment. Due to a datatype mismatch instead of printing an array it beeped three times and printed this...

 

[Robbert]

If you don't get the algorithm, draw it out on paper. That usually does it.

Here is a drawn out version which explains it pretty well if you follow what I posted.

It seems like it just printed some byte values, but I can't discern much more without some more details.

 

[Lancelot59]

Oh, that screenshot is from the next question down. :p

I managed to get the sorting problem with your help.

 

[Robbert]

Good!
Did you get it working with strings, now?

 

[Lancelot59]

Yup, it went perfectly. I'm currently working on my final project. An inventory/sales system for a book store :/

The thing is freaking massive. I just finished coding the inventory section and I'm going to debug it later today.