# insertion and quicksort check

• Aug 26th 2010, 11:26 PM
dunsta
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
• Aug 27th 2010, 07:09 AM
yeKciM
Quote:

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 :D so it's not much work to write it here what have you done :D so it can be checked :D:D:D
• Aug 27th 2010, 05:04 PM
dunsta
a1 b2 c3 d4 e5 f6
(* 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
• Aug 27th 2010, 05:08 PM
dunsta
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
• Aug 28th 2010, 02:47 AM
yeKciM
well let's see :D

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 :D (if you need to see what have been done in every step )

$\begin{matrix}
(6) & (4) & (1) & (8) & (7) & (5) & (3) & (2)\\
6 & (4) & 1 & 8 & 7 & 5 & 3 & 2\\
4 & 6 & (1) & 8 & 7 & 5 & 3 & 2\\
1 & 4 & 6 & (8) & 7 & 5 & 3 & 2\\
1 & 4 & 6 & 8 & (7) & 5 & 3 & 2 \\
1 & 4 & 6 & 7 & 8 & (5) & 3 & 2\\
1 & 4 & 5 & 6 & 7 & 8 & (3) & 2\\
1 & 3 & 4 & 5 & 6 & 7 & 8 & (2)\\
(1) & (2) & (3) & (4) & (5) & (6) & (7) & (8)
\end{matrix}$

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 :D:D:D:D:D

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

Edit: ah sorry ... lol i just now realize that L1, L2,... are line 1, line 2 ... :D:D:D:D:D it's ok :D:D:D you are correct :D
• Aug 28th 2010, 04:33 AM
dunsta
thanks for taking the time to help me Mickey
• Aug 28th 2010, 04:41 AM
yeKciM
you're welcome :D:D