Write a function in c plus plus to delete an element from a sorted array so that its sorted order remains as it is?

Answer 1

To delete an element form an array you simply move everything one place to the left, starting with the element to the right of the element you wish to remove, and then delete the final element by resizing the array. The following code demonstrates this:

#include <iostream>

void DeleteElement(unsigned int** pp,unsigned int& size,unsigned int index)

{

if(size)

{

unsigned int* p=*pp+index;

unsigned int* c=p+1;

std::cout<<"Deleting element index "<<index<<" with value "<<*p<<" from an array of size "<<size<<std::endl;

--size;

while(index++<size)

*p++=*c++;

*pp=(unsigned int*)realloc(*pp,size*sizeof(unsigned int));

}

}

void PrintArray(unsigned int* a,const unsigned int size)

{

std::cout<<"Array: size="<<size<<" { ";

unsigned int i=0;

while(i<size)

std::cout<<a[i++]<<" ";

std::cout<<"} "<<std::endl;

}

int main()

{

// Allocate a dynamic array of size 5:

unsigned int size=5;

unsigned int* a=(unsigned int*)malloc(size*sizeof(unsigned int));

// Initialise array with sorted values (ascending order):

for(unsigned int i=0;i<size;++i)

a[i]=(i+1)*2;

// Print current array:

PrintArray(a,size);

// Delete element 1 (value 2)

DeleteElement(&a,size,1);

// Print current array:

PrintArray(a,size);

// Delete element 2 (value 4)

DeleteElement(&a,size,2);

// Print current array:

PrintArray(a,size);

// Release allocation.

delete[]a, a=NULL;

return(0);

}

Note that static arrays cannot be resized, so to remove an element you need to maintain a count of the active elements, and move inactive elements to the end of the array. The process is similar to the above, except you need to copy the inactive element's value before shifting everything to the left, and then replace the final element's value with the one you saved.

In C++, operations such as this are greatly simplified by using a vector rather than an array. Vectors are effectively the same as dynamic arrays, but are implemented as self-contained objects with member methods to manipulate the contents, thus greatly simplifying your code. Deleting an element is a simple as calling the vector's built-in delete method. Memory management is largely transparent and, because a vector knows its internal size, passing vectors to functions is made that much easier -- you simply pass them by reference.