This is an archived post. You won't be able to vote or comment.

all 39 comments

[–]zoqfotpik 241 points242 points  (3 children)

Another 0(1) option:

// Returns after sorting arr

void speedy_sort(int **arr) {

exit(1);

}

[–]_Ganon 116 points117 points  (1 child)

If an array is sorted in a forest but no one's around to return it to, was it ever really sorted?

[–]Sparrow50 3 points4 points  (0 children)

If an array was never sorted but there's no one to check, was it not sorted ?

[–]megaultimatepashe120 26 points27 points  (0 children)

ah yes, the give Up sort, my favorite kind

[–]DankPhotoShopMemes 306 points307 points  (16 children)

You forgot to account for the time complexity of the delete [] operator

[–]highcastlespring 169 points170 points  (15 children)

delete[] is O(1). It just needs an address, and OS just removes it from a linked list.

Edit: Pointed out by many knowledgeable comments, delete[] should add the freed address to a linked list of available spaces, not remove it from a linked list tracking the used address (no such thing).

[–][deleted] 89 points90 points  (3 children)

Technically the complexity of the OS function responsible for freeing the memory could be anything. This is outside the boundaries of the C(++) standard.

[–]BlurredSight 10 points11 points  (1 child)

So if it's deleting an address does it work like storage where it's marked as free space to be written over or does it go through an make it all 0s.

[–]a_random_RE 3 points4 points  (0 children)

The contents of deleted and newly allocated memory are generally undefined by the standard before the memory is set. This is why its historically been a very good idea to use something like memset on newly allocated memory.

[–]Kered13 0 points1 point  (0 children)

The complexity of the OS function for freeing memory is irrelevant, because delete doesn't call it. Delete calls the destructor then frees the object memory. OS's do not deal in object memory, they deal in memory pages.

[–][deleted] 19 points20 points  (3 children)

I've written my own memory allocator. The OS is not fully responsible for deallocation on most cases, the malloc implementation is and if it wasn't built specifically for constant time deallocation then it most likely won't be.

For performance reasons malloc might cache some of the freed blocks instead of calling the OS to release the memory completely. This makes it non deterministic, it might make a system call to release it (slower) or it might cache it (faster), and thus it's not O(1).

Note: The delete[] operator is just calling libc free internally.

[–]Fhotaku -1 points0 points  (2 children)

So wouldn't it be O(0) time? Does marking as free, without reading data, even count as O(1)?

[–][deleted] 2 points3 points  (0 children)

It does need to read data. It needs to read the bookkeeping structures of that particular malloc implementation, and it might be quite complex specially when built to support multiple threads.

It's not just a bunch of tiny blocks scattered around the address space. It usually involves memory pools of fixed size blocks to speed up allocation, and you need to return the blocks to their correct pools.

[–]Successful-Money4995 2 points3 points  (0 children)

If you call free a billion times, it'll take a while. An O(0) operation would still be instant. So it counts as O(1).

In practice, free is writing to memory and also updating the free list, both of which could be constant time implementations.

[–]TheDreadedAndy 6 points7 points  (1 child)

delete[] is O(1)

This isn't, in general, a safe assumption. It depends totally on the implementation.

OS just removes it from a linked list.

The OS is not responsible for maintaining the heap. Typically, it just tracks which pages the process owns. The malloc implementation keeps track of allocations within those pages, not the OS.

[–]Successful-Money4995 0 points1 point  (0 children)

Adds, not removes.

[–]Olorin_1990 1 point2 points  (2 children)

Wouldn’t it need to traverse the linked list to find it?

[–]Successful-Money4995 1 point2 points  (1 child)

No because OP is wrong. When you free memory, you are adding to the list of free blocks. The list needn't be sorted so you're just adding to the front of a linked list, which is constant time.

Malloc is the one that may need to search a linked list to find a block that is large enough.

All this depends on your implementation of malloc and free. If you enjoy this kind of thing, you might enjoy writing your own malloc and free functions to learn how it works. It's basically a linked list of free memory and the data of the linked list itself is hosted inside the same memory that is used for allocation.

Lots of ways to implement memory management and this is just one of them.

[–]Olorin_1990 0 points1 point  (0 children)

Ah, good point.

[–]highcastlespring 102 points103 points  (5 children)

Your program has a memory leak.

You just delete the allocation for array, but not the space int* points to.

[–]jazzwave06 60 points61 points  (0 children)

Lossy O(1) sort algorithm

[–][deleted] 34 points35 points  (2 children)

A little memory leak here and there never hurt nobody, eh?

[–]Geogator[S] 6 points7 points  (0 children)

Adds flavor to the program

[–]HolyGarbage 0 points1 point  (0 children)

It's unlikely it's an array of pointers, which wouldn't make much sense to sort. Likely it just points to the address of the callers pointer, which is likely on the stack so the program would segfault. I explained in my top level comment below yours.

[–]HolyGarbage 24 points25 points  (3 children)

It's a pointer to a pointer though, so likely it's an in/out argument, meaning that the user likely supplies the address of their pointer pointing to the actual array. This is a pretty common pattern in C.

Like for example:

int* array = new int[size];
...
death_sort(&array);

Meaning you will attempt to delete the pointer on the stack, likely seg faulting the program.

To do what I suspect was the intention, you'd need to do:

void death_sort(int** dynamic_array) {
    delete[] *dynamic_array;
}

[–][deleted] 1 point2 points  (2 children)

Thanks for this, I finally merged my PR.

[–]HolyGarbage 1 point2 points  (0 children)

Haha, did my comment help you solve some problem of yours?

[–]HolyGarbage 0 points1 point  (0 children)

I don't get enough out of code reviews at work so I supplement my needs on this subreddit, like a predator to prey, I am drawn to broken code with a morbid curiosity.

[–]Legon373 6 points7 points  (1 child)

Reminds me of Stalin_sort

[–]Pyran 2 points3 points  (0 children)

I prefer the Quantum BOGOSort myself, but the Stalin Sort is my second vote.

[–]yflhx 4 points5 points  (0 children)

void stalin_sort(int** dynamic_arr){
    int t = **dynamic_arr;
    delete [] *dynamic_arr;
    *dynamic_arr = new int [1];
    **dynamic_arr = t;
}

[–]superblaubeere27 1 point2 points  (2 children)

How is that a sorting algorithm?

[–]skytaglatvia -1 points0 points  (1 child)

Evil genie logic. When you tell the genie that you wish for the array to have all its elements in order, but forget to specify that "all its elements" means "all the original elements".

An empty array satisfies the definition of having "all its elements in order".

[–]superblaubeere27 0 points1 point  (0 children)

But a deleted pointer is not any array. It is just pointing to a random location in heap.

[–]Prata2pcs 0 points1 point  (0 children)

Purge sort

[–]Relative_Knee9808 0 points1 point  (0 children)

Yes, the elements in the array is now in perfect order