Thread: how to delete duplicated numbers in quick sort ?

1. 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);
}```

2. it seems that my question is difficult and nobody will help me. i have exam tomorrow in that question :-S

3. 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?

4. 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. >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.

6. ok, could you help me with the codes or give a hint so that i could utilize in solving my problem ?

7. 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. 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. 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. 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. Sorry, I ate lunch out today, so I don't have a spoon with me.

12. 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! >>

13. Originally Posted by strawberry88
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. 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.