Thread: how to delete duplicated numbers in quick sort ?

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    7

    Exclamation how to delete duplicated numbers in quick sort ?

    hallo everybody, in fact, i wrote those codes but i encountered a difficulty in how to delete the duplication for example, i intered 3 4 6 6 7 3 the output comes like that
    3 3 4 6 6 7. The questions is what are the codes that i have to add to make it like that
    3 4 6 7 and where should i add them.thanks in advance




    Code:
     #include <stdio.h>
    #include <conio.h>
    #define max6
    void quicksort (int a[] , int low , int high);
    int partition ( int a[] , int low , int high);
    void main()
    {
    int arr[max], i;
    clrscr();
    printf("enter the elements for array \n");
    for(i= 0 ; i< max; i++)
    scanf("%d", &arr[i]);
    quicksort(arr , 0 , max-1);
    printf("\n the sorted array is \n");
    for( i= 0 ; i< max ; i++)
    printf("%d" , arr[i]);
    }
    void quicksort ( int a[] , int low , int high)
    {
    int pivot;
    if(low < high)
    {
    pivot = partition ( a , low , high);
    quicksort ( a ,low , pivot - 1);
    quicksort (a , pivot + 1 , high);
    }
    }
    int partition ( int a[] , int low , int high)
    {
    int i , j , x , temp;
    x = a[high];
     i = low - 1;
    for ( j = low ; j < high; j++)
    {
    if ( a [j] <= x)
    {
    i = i+1;
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    }
    }
    temp = a [i+1];
    a[i+1] = a[high];
    a[high] = temp;
    return (i+1);
    }
    Last edited by strawberry88; 03-12-2010 at 02:31 PM.

  2. #2
    Registered User
    Join Date
    Mar 2010
    Posts
    7
    it seems that my question is difficult and nobody will help me. i have exam tomorrow in that question :-S

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Well, it is good that you posted code in code tags, but you should indent your code too.

    As for your problem: are you required to remove duplicates in-place in linear time, or may you create a temporary array or use a less efficient algorithm?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Mar 2010
    Posts
    7
    i don't know how to remove the duplicated number. i think, i have to use deletion code to remove them but i don't have any idea about.Could you help me or give any tutorial, please ?

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >it seems that my question is difficult
    Why does everyone assume that an unanswered question is difficult?

    >and nobody will help me
    It's been one hour. Be patient.

    >i wrote those codes but i encountered a difficulty in how to delete the duplication
    Quicksort is an extremely brittle algorithm. Even the most innocent changes can break it in subtle and/or severe ways. I seriously doubt the requirements are to eliminate duplicates while sorting. More likely the requirements are to sort using quicksort, then eliminate duplicates with one of the trivial and well known algorithms for removing duplicates from a sorted range.
    My best code is written with the delete key.

  6. #6
    Registered User
    Join Date
    Mar 2010
    Posts
    7
    ok, could you help me with the codes or give a hint so that i could utilize in solving my problem ?

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Do it in two steps ie first sort then create a target array and fill it with unique elements.
    This of course means that the storage requirements have just doubled, at the very least.

  8. #8
    Registered User
    Join Date
    Mar 2010
    Posts
    7
    how to do it ?
    i am beginner in C.
    if there any site or tutorial which may clarify what you have said, it will be better

  9. #9
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    The algorithm (itCbitC stated) is fairly easy:

    Duplicate the memory for the second array.
    make two counters array1_cnt, array2_cnt. zero.
    into array2 put the first element of array1.
    for array1_cnt = 1 through array1_cnt = <last>
    increment array2_cnt and put the data from array1(_cnt) into array2(_cnt + 1) iff array1(_cnt) != array2(_cnt)

    Another way to do this is to shift each element up in the array if array(this) == array(next) -- AND, you can even do this smart where you say while array(this) == array(that) then start the move after you find where this != that.

    Guys, did I give too much information?

  10. #10
    Registered User
    Join Date
    Mar 2010
    Posts
    7
    i don't understand anything because it is too late here and my mind is closed.
    with codes will be more easier to understand, give my the method that i have to add in my codes to avoid duplication of numbers :-S

  11. #11
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Sorry, I ate lunch out today, so I don't have a spoon with me.

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Code:
    int now, next, i, j, arraySize;         //arraySize is max elements in array
    
      for(i = 0; i < arraySize; i++) {         //check all values in array
        if(array[i] == array[i+1])  {          //if adjacent values are equal
          for(j = i +1; j < arraySize; j++)    //move all higher index values down by one
            array[j] = array[j+1];             
          arraySize--;                         //and decrement arraySize by one
          --i;
        }
      }
    }
    This is the idea of removing duplicates, without using another array. It wouldn't be efficient if you had a bunch of huge arrays with lots of duplicates in them. For small arrays (under 10,000) or so, it's OK, but not the best for sure.

    I gotta give him props for posting Quicksort! AND using code tags. << thumbs up! >>
    Last edited by Adak; 03-12-2010 at 05:59 PM.

  13. #13
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by strawberry88 View Post
    The questions is what are the codes that i have to add to make it like that
    3 4 6 7 and where should i add them.thanks in advance
    No offence buddy but it sounds to me like: "Please do this homework/assignment for me and let me know exactly what the code will look like. I can be reached in the living room watching TV".

  14. #14
    Registered User
    Join Date
    Mar 2010
    Posts
    7
    i didn't mean that i want someone to do my homework, actually, it is not homework.tried to solve it and read many books but i couldn't reach the proper codes.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. bubble sort not sorting numbers in order.
    By rushhour in forum C++ Programming
    Replies: 21
    Last Post: 02-19-2009, 01:40 PM
  3. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 11:15 AM
  4. Problem need help
    By Srpurdy in forum C++ Programming
    Replies: 1
    Last Post: 07-24-2002, 12:45 PM
  5. memory management...
    By master5001 in forum Game Programming
    Replies: 24
    Last Post: 01-07-2002, 05:50 PM