Thread: insertion and quicksort check

Hi
For the following list

5,3,1,4,2,6

I have the results
insertion sort ---> 10 comparisions
quicksort ---> 10 comparisons

(Ofcoarse I have the working out in my notebook, but I am wandering if I have the correct results, if not I'll try again and post my work through to get some help)
TY

Originally Posted by dunsta

Hi
For the following list

5,3,1,4,2,6

I have the results
insertion sort ---> 10 comparisions
quicksort ---> 10 comparisons

(Ofcoarse I have the working out in my notebook, but I am wandering if I have the correct results, if not I'll try again and post my work through to get some help)
TY

those are two simple algorithms for sorting sequences so it's not much work to write it here what have you done so it can be checked

(* sorry buts it's difficult to get all the colums to line up)

insertion sort

L1 L2 L3 L4 L5 L6
5 3 1 1 1 1
3 5 3 3 2 2
1 1 5 4 3 3
4 4 4 5 4 4
2 2 2 2 5 5
6 6 6 6 6 6



Comparisons
L1 L2 L3 L4 L5 L6
0 1 2 2 4 1

Total Comp. = 10

quick sort
( *=final place .=pivot)

List 1 List 2 List 3 List 4
5. 3. 1. 1*
3 1 2 2*
1 4 3* 3*
4 2 4. 4*
2 5 * 5* 5*
6 6. 6* 6*

Comparisons
5 4 1 0


Total Comp. = 10

well let's see

insertion sort should be something like this:

Code:

void InsertionSort (int A[ ], int N) {
int i,j,pom;
for (i=1; i<N ; i++ ) { 
pom=A[i];
for(j=i; j>=1 && A[j-1]>pom ; j-- ) 
A[j]=A[j-1]
A[j]=pom;
}
}

so if for example we have sequence 6,4,1,8,7,5,3,2 so using insertion sort would look like this (if you need to see what have been done in every step )



that's the way that should be done insertion sort... that what you wrote that you have done... hm... don't know what to say


there can be misunderstanding of some kind : so we'll first this clarify than we'll continue to that sorting algorithm (quick sort)

Edit: ah sorry ... lol i just now realize that L1, L2,... are line 1, line 2 ... it's ok you are correct

thanks for taking the time to help me Mickey

you're welcome