1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sorting Array

  1. Dec 2, 2009 #1
    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.

    Code (Text):

    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.
     
  2. jcsd
  3. Dec 4, 2009 #2
    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!)
     
  4. Dec 4, 2009 #3
    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...
     

    Attached Files:

  5. Dec 4, 2009 #4
    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.
     
  6. Dec 4, 2009 #5
    Oh, that screenshot is from the next question down. :p

    I managed to get the sorting problem with your help.
     
  7. Dec 9, 2009 #6
    Good!
    Did you get it working with strings, now?
     
  8. Dec 9, 2009 #7
    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 gonna debug it later today.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook