I don’t know if you still need this problem solved, but http://www.ics.uci.edu/~eppstein/161/960130.html has an algorithm:
select(L,k) { if (L has 10 or fewer elements) { sort L return the element in the kth position } partition L into subsets S[i] of five elements each (there will be n/5 subsets total). for (i = 1 to n/5) do x[i] = select(S[i],3) M = select({x[i]}, n/10) partition L into L1<M, L2=M, L3>M if (k <= length(L1)) return select(L1,k) else if (k > length(L1)+length(L2)) return select(L3,k-length(L1)-length(L2)) else return M }
Good luck!
Related Posts:
- Quicksort with Python
- how to implement quick sort algorithm in C++
- What is stability in sorting algorithms and why is it important?
- Quick Sort Vs Merge Sort
- Insertion Sort vs. Selection Sort
- Trying to understand max heapify
- Shortest possible depth of a leaf in decision tree (comparison sorting algorithm)
- Quicksort vs heapsort
- Exactly how many comparisons does merge sort make?
- Shuffle a deck of cards in Java
- Is there an O(n) integer sorting algorithm?
- An example of Best Case Scenario for Quick Sort (Need someone to check if my answer is correct)
- Finding the median of an unsorted array
- What is the difference between bucket sort and radix sort?
- Sorting an array in C?
- About bubble sort vs merge sort
- In a triangulated isometric grid, what triangle is a given point in?
- What is a loop invariant?
- How to use Collections.sort() in Java?
- What is a loop invariant?
- What does O(log n) mean exactly?
- how to calculate binary search complexity
- When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]
- What does O(log n) mean exactly?
- What is Sliding Window Algorithm? Examples?
- How to sort an ArrayList?
- What is the difference between tree depth and height?
- Python: maximum recursion depth exceeded while calling a Python object
- Why is the time complexity of both DFS and BFS O( V + E )
- Finding median of list in Python
- Time complexity of a Priority Queue in C++
- Breadth First Search time complexity analysis
- Counting the sum of every nodes’ neighbors’ degrees?
- Time Complexity of the Kruskal Algorithm?
- Why is there no SortedList in Java?
- java Arrays.sort 2d array
- Polynomial time and exponential time
- Why does cache use Most Recently Used (MRU) algorithm as evict policy?
- Difference and advantages between dijkstra & A star
- Example of O(n!)?
- Best Case for Bubble Sort
- How to find the kth smallest element in the union of two sorted arrays?
- When will the worst case of Merge Sort occur?
- Big O, how do you calculate/approximate it?
- Sorting HashMap by values
- Finding the max/min value in an array of primitives using Java
- Will Arrays.sort() increase time complexity and space time complexity?
- Performing Breadth First Search recursively
- Is Quicksort in-place or not?
- Find how many connected groups of nodes in a given adjacency matrix
- Sort a single String in Java
- longest increasing subsequence(O(nlogn))
- O(n log n) vs O(n) — practical differences in time complexity
- When should I use Kruskal as opposed to Prim (and vice versa)?
- Python Weighted Random [duplicate]
- What is the meaning of “exclusive” and “inclusive” when describing number ranges?
- What’s a good algorithm to generate a maze?
- Intuition for perceptron weight update rule
- Easy: Solve T(n)=T(n-1)+n by Iteration Method
- Good Java graph algorithm library?
- What is tail call optimization?
- Generating all permutations of a given string
- PacMan: what kinds of heuristics are mainly used?
- Sort a Map
by values - Big-oh vs big-theta
- How to sort an array of objects in Java?
- How to sort an array of objects in Java?
- Efficient swapping of elements of an array in Java
- Best case time complexity for selection sort
- Looking for algorithm finding euler path
- Trie complexity and searching
- What does this definition of contiguous subsequences mean?
- Is log(n!) = Θ(n·log(n))?
- Is complexity O(log(n)) equivalent to O(sqrt(n))?
- java sort using anonymous class
- Java, Shifting Elements in an Array
- Creating a maze solving algorithm in Java
- How to find maximum spanning tree?
- How to use Comparator in Java to sort
- Algorithm to return all combinations of k elements from n
- How to calculate big-theta
- What is the time complexity of while loops?
- Merge sort time and space complexity
- Intuitive explanation for why QuickSort is n log n?
- Calculate distance between two latitude-longitude points? (Haversine formula)
- When should we use Radix sort?
- Java Array Sort descending?
- How to calculate time complexity of backtracking algorithm?
- What is a loop invariant?
- What is the difference between an Abstract Data Type(ADT) and a Data Structure?
- Hash table runtime complexity (insert, search and delete)
- Which is better: O(n log n) or O(n^2)
- What is O(log* N)?
- Quickselect time complexity explained
- Sort ArrayList of custom Objects by property
- What is the proper equivalent of “while(true)” in plain C?
- Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?
- How to sort a HashSet?
- Asymptotic Notation – does n (log n) (log n) simplify?
- Big Oh for (n log n)