KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
I wrote a simple program that sorts in O(n). It is highly memory inefficient, but that's not the point. It uses the principle behind a HashMap for sorting: public class NLogNBreak { public static class LinkedListBack { public LinkedListBack(int val){ first = new Node(); first.val = val; } public Node first = null; public void insert(int i){ Node n = new Node(); n.val = i; n.next = first; first = n; } } private static class Node { public Node next = null; public int val; } //max > in[i] > 0 public static LinkedListBack[] sorted(int[] in, int max){ LinkedListBack[] ar = new LinkedListBack[max + 1]; for (int i = 0; i < in.length; i++) { int val = in[i]; if(ar[val] == null){ ar[val] = new LinkedListBack(val); } else { ar[val].insert(val); } } return ar; } } So does this count as a sort of O(n), even though it returns the result in a funky format?
Tags (comma-separated)
Save Edits
Cancel