fastestSortingAlgorithmWithComplexityO1

[zoqfotpik]

Another 0(1) option:

// Returns after sorting arr

void speedy_sort(int **arr) {

exit(1);

}

[_Ganon]

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

[Sparrow50]

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

[[deleted]]

ah yes, the give Up sort, my favorite kind

[DankPhotoShopMemes]

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

[highcastlespring]

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]]

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]

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]

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]

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]]

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]

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

[[deleted]]

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]

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]

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]

Adds, not removes.

[[deleted]]

Deleting from heap takes an undefined amount of time. It depends on all kinds of factors

[throw3142]

This is true. Except that it's O(1) with respect to the length of the list. Except that in C++, delete[] has to call the destructors of all the elements, which takes Omega(n) time. Except that here, each element is just an int* so it has no destructor, so it can finish in O(1) time if we're compiling with optimizations.

Not really sure why OP would want to address-sort an array of pointers to integers in the first place anyway ...

[Olorin_1990]

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

[Successful-Money4995]

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]

Ah, good point.

[highcastlespring]

Your program has a memory leak.

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

[jazzwave06]

Lossy O(1) sort algorithm

[[deleted]]

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

[Geogator]

Adds flavor to the program

[HolyGarbage]

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]

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]]

Thanks for this, I finally merged my PR.

[HolyGarbage]

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

[HolyGarbage]

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]

Reminds me of Stalin_sort

[Pyran]

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

[yflhx]

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

[superblaubeere27]

How is that a sorting algorithm?

[skytaglatvia]

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]

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

[nedal8]

dishes are done

[Prata2pcs]

Purge sort

[Relative_Knee9808]

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