Code:
void delete_ith(element_type* array, int* array_length, int i) {
array[i] = array[*array_length-1];
*array_length = *array_length-1;
}
Shortens the "length" of the array by one, deleting the ith element.
The actual memory allocated to the array might be the same, but 1 less element is used, and the ith element has been deleted/overwritten.
Quote:
|
b. Delete the ith element of a sorted array (the remaining array has to stay sorted, of course.)
|
In levels of increasing incorrectness:
1> it can't be done.
2> use markers for "unused value".
3> Implement a hash table instead of an array. Takes practical constant time, theoretical (when you pay attention to the dots on the i's) lg n time.
4> Implement a skip list instead of an array. Takes probabalistic-average lg n time.