Which sorting algorithm is this?



  • for (int index=0; index<items.length; index++) {
    for (int subIndex=index; subIndex<items.length; subIndex++) {
    if (items[subIndex] < items[index]) {
    int temp = items[index];
    items[index] = items[subIndex];
    items[subIndex] = temp;
    }
    }
    }


    It's supposed to be a "selection sort", but I suspect it's something more of a bubble sort.


  • Discourse touched me in a no-no place

    @shill said:

    It's supposed to be a "selection sort", but I suspect it's something more of a bubble sort.
    Selection sort goes through the list looking for the lowest number, putting it in slot[0].

    Then it goes through the remainder of the list looking the the next lowest number and puts that in slot[1].

    Sorting stops when you reach slot[max-1] as the lower bound.

    Bubble sort just goes through the list compares adjacent neighbours and swaps them if they're out of order. The list is gone through until no more swaps happen.

    The difference between them is the best case time - selection sort goes through the list the same number of times regardless, the bubble sort could complete after one pass.

    Wikipedia for more indepth explanations.

     

    You have a selection sort there. With extra swaps thrown in for good measure.



  • Yeah, looks like conceptually speaking it's a selection sort, however it definitely isn't the standard one nor an efficient one.

    If you read the inner loop you'll see that while it shuffles the remaining elements in some semi-random manner when it ends the element at "index" is set to the lowest number of all those from index to items.length. The shuffling of the items at the end of the loop is essentially irrelevant.

    Most implementations wouldn't swap the values around until it had decided precisely which element is the smallest, but once you realize that what it's doing to the rest of the array is irrelevant it's definitely closer to a selection sort than bubble-sort (Though whether it qualifies as a selection sort depends on how literally you interpret definitions).



  •  Alright, thanks guys. I'm working from a sketchy textbook that doesn't actually explain what it's doing all too well, and I've found horrible errors in it. Luckily it's for a high school class, not college. Anyway, I found a more sensible selection sort on Google so I'm gonna use that instead.


  • Discourse touched me in a no-no place

    @shill said:

    Anyway, I found a more sensible selection sort on Google so I'm gonna use that instead.
    Care to name it? Or, perhaps even, give the URL of the one you'll be copying?



  • @shill said:

     Alright, thanks guys. I'm working from a sketchy textbook that doesn't actually explain what it's doing all too well, and I've found horrible errors in it. Luckily it's for a high school class, not college. Anyway, I found a more sensible selection sort on Google so I'm gonna use that instead.

    Actually, if it's for a high school class, then that's possibly the best possible 'completely obvious and intuitive sort algorithm'.  It's the first sort algorithm I was shown in high school, for what it's worth.

    The next step would be to show how it has some obvious areas for improvement - most specifically, the alteration to make it a more standard version as noted above... Err, as I'm thinking about it, the next step had been for the teacher to give us an assignment: 'think about this over the weekend, and try to come up with an improved version.'



  • @tgape said:

    Actually, if it's for a high school class, then that's possibly the best possible 'completely obvious and intuitive sort algorithm'.  It's the first sort algorithm I was shown in high school, for what it's worth.

    The next step would be to show how it has some obvious areas for improvement - most specifically, the alteration to make it a more standard version as noted above... Err, as I'm thinking about it, the next step had been for the teacher to give us an assignment: 'think about this over the weekend, and try to come up with an improved version.'

    Really? First I saw was more of a standard bubble-sort then moved to insertion then selection.

    We did get the "implement your own sorting algorithm" one though. There was some rather scary results. One guy actually wrote a random-sort. It randomly picked 2 elements in the array and swapped them if they were wrong, and if it managed to go 1000 iterations over that without swapping anything it assumed the array was sorted (In his defense the WTF was intentional and the assignment wasn't graded :P)



  • Wow, all I got to do in computer class in middle and highschool was play Oregon trail.



  • @amischiefr said:

    Wow, all I got to do in computer class in middle and highschool was play Oregon trail.

    And you're probably a better developer because of it.

Log in to reply