Results 1 to 7 of 7

Math Help - insertion and quicksort check

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    69

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member yeKciM's Avatar
    Joined
    Jul 2010
    Posts
    456
    Quote Originally Posted by dunsta View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    69

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member yeKciM's Avatar
    Joined
    Jul 2010
    Posts
    456
    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 )

    \begin{matrix}<br />
(6) & (4) & (1) & (8) & (7) & (5) & (3) & (2)\\ <br />
6 & (4) & 1 & 8 & 7 & 5 & 3 & 2\\<br />
4 & 6 & (1) & 8 & 7 & 5 & 3 & 2\\ <br />
1 & 4 & 6 & (8) & 7 & 5 & 3 & 2\\ <br />
1 & 4 & 6 & 8 & (7) & 5 & 3 & 2 \\ <br />
1 & 4 & 6 & 7 & 8 & (5) & 3 & 2\\ <br />
1 & 4 & 5 & 6 & 7 & 8 & (3) & 2\\ <br />
1 & 3 & 4 & 5 & 6 & 7 & 8 & (2)\\<br />
(1) & (2) & (3) & (4) & (5) & (6) & (7) & (8)<br />
\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


    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    thanks for taking the time to help me Mickey
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member yeKciM's Avatar
    Joined
    Jul 2010
    Posts
    456
    you're welcome
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: March 12th 2011, 04:05 AM
  2. Please check that
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: April 13th 2009, 01:12 AM
  3. check :)
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 6th 2008, 04:26 PM
  4. Different Sorts (Bubble, Insertion...)
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: October 21st 2006, 11:55 PM

Search Tags


/mathhelpforum @mathhelpforum