I can't tell if this sort I made would still be concidered an insertion sort or some weird bubble sort. What would you guys call it?
Code:for(i = 1; i < size; ++i) { temp = array[i]; for(j = i - 1; (j >= 0) && (array[j] > temp); j--) { swap(&(array[j]), &(array[j+1])); } printArray(array, size); }
Last edited by dharh; 03-16-2002 at 04:38 PM.
You're doing an insertion sort with extra swapping.
I'd do this:
for(i = 1; i < size; ++i) {
temp = array[i];
for(j = i; temp > array[j-1] && j > 0; j--) array[j] = array[j-1];
array[j] = temp;
}
I don't see the swap difference between your sort and mine, though I will note that yours sorts in reverse order, you need to switch the temp > array[j-1] to temp < array[j-1].
like:
Code:for(i = 1; i < size; ++i) { temp = array[i]; for(j = i; temp < array[j-1] && j > 0; j--) array[j] = array[j-1]; array[j] = temp; }
"I don't see the swap difference between your sort and mine, though I will note that yours sorts in reverse order, you need to switch the temp > array[j-1] to temp < array[j-1]."
Yes, switch the ">"
In your algorithm, whenever the element which needs to be inserted has to be compared more than once, you do unnecessary swapping. The algorithm I suggested only swaps at the end.
With big lists, this will be noticable. Try 10,000 random integers.
(not saying that this is an optimal sort, just relatively speaking, but good for small lists)
Dave
I think I understand now, your not realy ever swaping in an insertion sort. Your just coping elements over eachother. Which only requires temping the to be inserted element, while swaping requires all the elements to be temped during the swap.
