जावास्क्रिप्ट में आंशिक प्रकार

Question

क्या कोई अंतर्निहित जावास्क्रिप्ट फ़ंक्शन partial sort करने के लिए है? यदि नहीं, तो इसे लागू करने का एक अच्छा तरीका क्या है?

एन तत्वों की एक अवर्गीकृत सरणी देखते हुए, मैं कश्मीर तत्वों है कि कुछ भार समारोह के संबंध में कम से कम कर रहे हैं करना चाहते हैं। केएन से बहुत छोटा है, इसलिए यह पूरे सरणी को सॉर्ट करने और पहले के तत्वों को लेने में अक्षम होगा।

मैं कुछ भी गैर-मानक, ब्राउज़र-निर्भर होने पर भी खुश रहूंगा। मैं अभी भी कस्टम जावास्क्रिप्ट कार्यान्वयन में फॉलबैक कर सकता था।

पुनश्च: यह (खाते में एक भार समारोह लेने के लिए, बस के रूप में वे सादगी के लिए कर रहे हैं तत्वों छँटाई के बिना) मेरे वर्तमान कस्टम दिया गया है: एक ही समय दिया सरणी के माध्यम से

function bisect(items, x, lo, hi) { 
    var mid; 
    if (typeof(lo) == 'undefined') lo = 0; 
    if (typeof(hi) == 'undefined') hi = items.length; 
    while (lo < hi) { 
    mid = Math.floor((lo + hi)/2); 
    if (x < items[mid]) hi = mid; 
    else lo = mid + 1; 
    } 
    return lo; 
} 

function insort(items, x) { 
    items.splice(bisect(items, x), 0, x); 
} 

function partialSort(items, k) { 
    var smallest = []; 
    for (var i = 0, len = items.length; i < len; ++i) { 
    var item = items[i]; 
    if (smallest.length < k || item < smallest[smallest.length - 1]) { 
     insort(smallest, item); 
     if (smallest.length > k) 
     smallest.splice(k, 1); 
    } 
    } 
    return smallest; 
} 

console.log(partialSort([5, 4, 3, 2, 1, 6, 7, 8, 1, 9], 3)); 

एल्गोरिथ्म चलता है, नए तत्वों को सम्मिलित करने के लिए बाइनरी खोज का उपयोग करके के अब तक की सबसे छोटी वस्तुओं की क्रमबद्ध सूची का ट्रैक रखना।

यदि आप सोचते हैं कि वे तेज़ या अधिक सुरुचिपूर्ण हो सकते हैं तो कृपया वैकल्पिक समाधान पोस्ट करें। समय बहुत स्वागत है।

Answer 1

नहीं। केवल full array sort है, इसलिए आपको अपने स्वयं के कार्यान्वयन का उपयोग करने की आवश्यकता होगी।

अपने कोड पर

लिटिल सुधार (मैं बिल्कुल वैसा ही एल्गोरिथ्म :-) के बारे में सोचा था):

Answer 2

कोई देशी है (max चर कैशिंग करने के लिए यहां तक ​​कि seems to be a little faster, मैं वजह से लगता है)

function partialSort(items, k) { 
    var smallest = items.slice(0, k).sort(), 
     max = smallest[k-1]; 
    for (var i = k, len = items.length; i < len; ++i) { 
     var item = items[i]; 
     if (item < max) { 
      insort(smallest, item); 
      smallest.length = k; 
      max = smallest[k-1]; 
     } 
    } 
    return smallest; 
} 

आंशिक क्रम समारोह। आप जो चाहते हैं उसकी निकटतम चीज़ Array.filter है।

function isSmallEnough(element, index, array) { 
    return (element <= 10); 
} 
var filtered = [12, 5, 8, 130, 44].filter(isSmallEnough); 
// filtered is [5, 8] 

उदाहरण उपरोक्त लिंक से उधार लिया गया था (और थोड़ा संशोधित)।