1

Pset 3: find is a program that finds a number among an array of numbers. We are required to implement a sort and search function that were called on by another file in order to accomplish this. We had to use binary search and therefore it needs to be sorted first before the search function could work. I decided to use selection sort in order to sort the array into ascending order. I had thought my implementation of the search and sort functions would work but unfortunately when I tested the program by trying to find for a number that I knew was in the array but it didn't work. I therefore created two other files - one to test my search function implementation (using a sorted array I made) and one for the sort function to sort this same array. My search function was fine but my sort function gave a strange result. The array I used to test it was 6 numbers long so I just changed my limits of the i loop from n-1 (which would work for any length of array) to '4'. I then changed the limits for the j loop to '5' (instead of n-1). The 'sorted' result I got when I ran this test of my sort code was '10, 10, 10, 10, 10, 3' and for the life of me I can't figure out why it gave back the first number 5 times and then the last number. It is probably something obvious to you experienced coders but as a beginner I'm having trouble debugging this. Any help would be much appreciated!

#include <cs50.h>
#include <stdio.h>


int main() 

{

int arr[] = {10, 9, 4, 2, 5, 3};

int smallest;
int indexofsmallest;
int temp;

//for i = 0 to n-2 
for(int i = 0; i < 4; i++)
{
    smallest = arr[i];
    indexofsmallest = i;
   //find the smallest element from i+1 to n-1 
    for (int j=i+1; j < 5; j++)
    {
        if(arr[j]<smallest)
        {
            arr[j]=smallest;
            indexofsmallest = j;
        }

    }
    //exchange smallest element with element at i
   temp = arr[i];
   arr[i] = arr[indexofsmallest];
   arr[indexofsmallest] = temp;
}  

//print the sorted array
for(int k = 0; k < 6; k++)
{
printf("%i ", arr[k]);
}

printf("\n");  
}
1
arr[j]=smallest;

In the above line you are assigning the value stored in variable smallest to the jth element in your array. So in the first iteration of the for loop the variable smallest is set equal to the first element i.e. 10 which is saved in the array in your subsequent for loop. Thus the bizarre output. According to your logic the assignment should be other way around i.e.

smallest = arr[j];

such that the variable smallest has the least value at all times.

Also, your implementation of the Selection Sort algorithm is flawed. In your "outer" for loop you should be iterating over all but last element of your array and in your "inner" for loop you should be iterating over i+1th to nth elements.

| improve this answer | |
  • thank you for the first part, that makes sense! but i'm confused because the walkthrough explained it and explicitly wrote the pseudocode as 'for i = 0 to n-2: find the smallest element from i+1 to n-1 //exchange smallest element with element at i' as you will see in this video at 2:07 - youtube.com/watch?v=eXeP__gBMrM – joshkeisler95 Feb 2 '17 at 18:07
  • The line for i = 0 to n-2 in the pseudo code is intended to mean that you have to iterate over all elements except the last one and since indexing of an array starts with a zero thus for an n element array i must be taken from 0 to n - 2(i.e the index of the second last element). – N. Tiwari Feb 2 '17 at 18:14
  • Your for loop will stop when i = n - 2 because of i < n - 2your condition in the loop, thus you are not taking all the required elements into consideration for the sorting process. – N. Tiwari Feb 2 '17 at 18:18
  • ah yes that makes perfect sense, thanks very much :) – joshkeisler95 Feb 2 '17 at 18:19
  • @joshkeisler95 don't forget SE protocol :) – DinoCoderSaurus Feb 2 '17 at 20:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .