Selection Sort of a Array of random strings

Question

I am trying to create a selection sort algorithm that takes in an array of random strings and sorts it. I have looked online and in my book to try and model my code off of it and this is what I came up with. I am not sure where I went wrong, any help would be appreciated.

Here is how you load the array with the random strings:
string Sorter::randomString() {
    string s = "";
    for (int i = 0; i < MAX_CHARS; i++) {
        char randomChar = char(rand() % 26 + 97);
    s += randomChar;
    }
    return s;
}

void Sorter::load() {
    for (int i = 0; i < MAX_STRINGS; i++)
        workspace[i] = randomString();

Here is my selection sort: 

void Sorter::selectionSort() {
    for (int pass = 0; pass < MAX_STRINGS - 1; pass++) {
        string smallest = workspace[pass];
    for (int pos = pass + 1; pos < MAX_STRINGS - pass - 1; pos++) {
            if (workspace[pos] > smallest) {
                smallest = workspace[pos];
            }
            swap(workspace[pos], workspace[pass]);
        }
    }
}

I expected the array workspace to be sorted, but it is not :(

jignatius · Accepted Answer · 2019-10-27 21:44:54Z

1

There was a bit of a flaw in your logic in that you weren't setting the minimum element in the list properly. You should use a minimum index for this.

void selectionSort() {
    //Initialise minimum index
    int min_id = 0;
    //Loop through unsorted subarray 
    for (int pass = 0; pass < MAX_STRINGS - 1; pass++) {
        //Find the minimum element in rest of array
        min_id = pass;
        for (int pos = pass + 1; pos < MAX_STRINGS; pos++) {
            if (workspace[pos] < workspace[min_id]) {
                min_id = pos;
            }
        }
        //Swap the minimum element with current element in array
        swap(workspace[min_id], workspace[pass]);
    }
}

answered Oct 27, 2019 at 21:44

jignatius

6,5442 gold badges19 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jeaninez - MSFT · Accepted Answer · 2019-10-28 07:23:09Z

You couldn't find the smallest element in an unsorted array correctly. Here is my code:

void selectionSort(char arr[][MAX_STRINGS], int n)
{
    int i, j, min_idx;

    // One by one move boundary of unsorted subarray  
    char minStr[MAX_STRINGS];
    for (i = 0; i < n - 1; i++)
    {
        // Find the minimum element in unsorted array  
        int min_idx = i;
        strcpy_s(minStr, arr[i]);
        for (j = i + 1; j < n; j++)
        {
            // If min is greater than arr[j]  
            if (strcmp(minStr, arr[j]) > 0)
            {
                // Make arr[j] as minStr and update min_idx  
                strcpy_s(minStr, arr[j]);
                min_idx = j;
            }
        }

        // Swap the found minimum element with the first element  
        if (min_idx != i)
        {
            char temp[MAX_STRINGS];
            strcpy_s(temp, arr[i]); //swap item[pos] and item[i]  
            strcpy_s(arr[i], arr[min_idx]);
            strcpy_s(arr[min_idx], temp);
        }
    }

Collectives™ on Stack Overflow

Selection Sort of a Array of random strings

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related