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?
- 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
- Why does cache use Most Recently Used (MRU) algorithm as evict policy?
- Example of O(n!)?
- Best Case for Bubble Sort
- When will the worst case of Merge Sort occur?
- 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?
- Is Quicksort in-place or not?
- Find how many connected groups of nodes in a given adjacency matrix
- Sort a single String in Java
- O(n log n) vs O(n) — practical differences in time complexity
- Python Weighted Random [duplicate]
- What’s a good algorithm to generate a maze?
- Easy: Solve T(n)=T(n-1)+n by Iteration Method
- 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?
- Best case time complexity for selection sort
- Trie complexity and searching
- What does this definition of contiguous subsequences mean?
- Is log(n!) = Θ(n·log(n))?
- java sort using anonymous class
- How to find maximum spanning tree?
- 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
- 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?
- Difference between Big-O and Little-O Notation
- What is the big-O of the function (log n)^k
- How to calculate an angle from three points?
- Why is O(n) better than O( nlog(n) )?
- How to solve: T(n) = T(n/2) + T(n/4) + T(n/8) + (n)
- How to implement a most-recently-used cache
- how to write a recurrence relation for a given piece of code
- How to sort in-place using the merge sort algorithm?
- Why is merge sort worst case run time O (n log n)?
- Using insertion sort for descending order?
- What is the time and space complexity of a breadth first and depth first tree traversal?
- Create your own MD5 collisions
- A tool for calculating the big-O time complexity of Java code? [closed]
- Difference between Big-Theta and Big O notation in simple language
- How are the following functions O(N^3)?
- Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
- Finding all possible combinations of numbers to reach a given sum
- Is Dijkstra’s algorithm for directed or undirected graphs?
- Modular multiplicative inverse function in Python
- Minesweeper solving algorithm
- Best way to randomize an array with .NET