Does this sorting algorithm exist? (implemented in Swift)

Question

This might be a bad question but I am curious.

I was following some data structures and algorithms courses online, and I came across algorithms such as selection sort, insertion sort, bubble sort, merge sort, quick sort, heap sort.. They almost never get close to O(n) when the array is reverse-sorted.

I was wondering one thing: why are we not using space in return of time?

When I organise something I pick up one, and put it where it belongs to. So I thought if we have an array of items, we could just put each value to the index with that value.

Here is my implementation in Swift 4:

let simpleArray = [5,8,3,2,1,9,4,7,0] let maxSpace = 20 func spaceSort(array: [Int]) -> [Int] { guard array.count > 1 else { return array } var realResult = [Int]() var result = Array<Int>(repeating: -1, count: maxSpace) for i in 0..<array.count{ if(result[array[i]] != array[i]){ result[array[i]] = array[i] } } for i in 0..<result.count{ if(result[i] != -1){ realResult.append(i) } } return realResult } var spaceSorted = [Int]() var execTime = BenchTimer.measureBlock { spaceSorted = spaceSort(array: simpleArray) } print("Average execution time for simple array: \(execTime)") print(spaceSorted)

Results I get:

Does this sorting algorithm exist already?

Is this a bad idea because it only takes unique values and loses the duplicates? Or could there be uses for it?

And why can't I use Int.max for the maxSpace?

Edit: I get the error below

error: Execution was interrupted.

when I use let maxSpace = Int.max

MyPlayground(6961,0x7000024af000) malloc: Heap corruption detected, free list is damaged at 0x600003b7ebc0 * Incorrect guard value: 0 MyPlayground(6961,0x7000024af000) malloc: * set a breakpoint in malloc_error_break to debug

Thanks for the answers

Think about the amount of memory that needs to be allocated for an array of size 2^63. A quick google gives me 74 million terabytes... — Sweeper
– Sweeper, Commented Oct 26, 2019 at 16:30
@Sweeper you are right, just thought that what I used wasn't the max index an Array can have but an Int can have. — tiw
– tiw, Commented Oct 26, 2019 at 16:31

trincot · Accepted Answer · 2019-10-26 18:57:07Z

This is an extreme version of radix sort. Quoted from Wikipedia:

radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort.

In this case you choose your radix as maxSpace, and so you don't have any "elements with more than one significant digit" (from quote above).

Now, if you would use a Hash Set data structure instead of an array, you would actually not need to really allocate the space for the whole range. You would still keep all the loop iterations though (from 0 to maxSpace), and it would check whether the hash set contains the value of i (the loop variable), and if so, output it.

This can only be an efficient algorithm if maxSpace has the same order of magnitude as the number of elements in your input array. Other sorting algorithms can sort with O(nlogn) time complexity, so for cases where maxSpace is much greater than nlogn, the algorithm is not that compelling.

Collectives™ on Stack Overflow

Does this sorting algorithm exist? (implemented in Swift)

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related