सबसे तेज़ सुरक्षित सॉर्टिंग एल्गोरिदम कार्यान्वयन

Question

मैं सी # में एक quicksort एल्गोरिदम लागू करने में कुछ समय बिताता हूं। परिष्करण के बाद मैंने अपने कार्यान्वयन की गति और सी # के ऐरे सॉर्ट-विधि की तुलना की।

मैं बस यादृच्छिक int arrays पर काम करने की गति की तुलना करता हूं।

यहाँ मेरी कार्यान्वयन है:

static void QuickSort(int[] data, int left, int right) 
{ 
    int i = left - 1, 
     j = right; 

    while (true) 
    { 
     int d = data[left]; 
     do i++; while (data[i] < d); 
     do j--; while (data[j] > d); 

     if (i < j) 
     { 
      int tmp = data[i]; 
      data[i] = data[j]; 
      data[j] = tmp; 
     } 
     else 
     { 
      if (left < j) QuickSort(data, left, j); 
      if (++j < right) QuickSort(data, j, right); 
      return; 
     } 
    } 
} 

प्रदर्शन (जब एक यादृच्छिक पूर्णांक छँटाई [] 100000000 की लंबाई के साथ):
      - मेरे एल्गोरिथ्म: 14.21 सेकंड
      - नेट सरणी <int> .Sort: 14.84 सेकंड

क्या कोई जानता है कि मेरा एक तरीका कैसे कार्यान्वित किया जाए लिगोरिदम भी तेज?
या कोई भी तेजी से कार्यान्वयन प्रदान कर सकता है (एक quicksort नहीं होना चाहिए!) जो मेरे रन तेजी से?

नोट:
      - कोई एल्गोरिदम, जो कई कोर का उपयोग/प्रोसेसर सुधार करने के लिए कृपया perrformance
      - वैध सी # स्रोत कोड

मैं एक के भीतर प्रदान एल्गोरिदम के प्रदर्शन का परीक्षण होगा अगर मैं ऑनलाइन हूं तो कुछ मिनट।

संपादित करें:
क्या आपको लगता है कि 8 से कम मूल्य वाले भागों के लिए आदर्श सॉर्टिंग नेटवर्क का उपयोग प्रदर्शन में सुधार होगा?

Answer 1

क्या कोई जानता है कि मेरे एल्गोरिदम को और भी तेज़ी से कैसे कार्यान्वित किया जाए?

मैं पॉइंटर्स का उपयोग करने के लिए अपने कोड को परिवर्तित करके निष्पादन समय से 10% दाढ़ी करने में सक्षम था।

public unsafe static void UnsafeQuickSort(int[] data) 
    { 
     fixed (int* pdata = data) 
     { 
      UnsafeQuickSortRecursive(pdata, 0, data.Length - 1); 
     } 
    } 

    private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right) 
    { 
     int i = left - 1; 
     int j = right; 

     while (true) 
     { 
      int d = data[left]; 
      do i++; while (data[i] < d); 
      do j--; while (data[j] > d); 

      if (i < j) 
      { 
       int tmp = data[i]; 
       data[i] = data[j]; 
       data[j] = tmp; 
      } 
      else 
      { 
       if (left < j) UnsafeQuickSortRecursive(data, left, j); 
       if (++j < right) UnsafeQuickSortRecursive(data, j, right); 
       return; 
      } 
     } 
    } 

Answer 2

बाइनरी सम्मिलन क्रम लगभग हमेशा कम रन (~ 10 आइटम) के लिए जीतता है। सरलीकृत शाखा संरचना के कारण यह आदर्श सॉर्टिंग नेटवर्क से अक्सर बेहतर होता है।

Dual pivot quicksort quicksort से तेज़ है। लिंक्ड पेपर में जावा कार्यान्वयन होता है जिसे आप संभवतः अनुकूलित कर सकते हैं।

यदि आप केवल पूर्णांक को सॉर्ट कर रहे हैं, तो radix sort लंबे सरणी पर अभी भी तेज होगा।

Answer 3

शीयर सॉर्ट और ओड-इवेंट ट्रांसपोजिशन सॉर्ट पर एक नज़र डालें: http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html और http://home.westman.wave.ca/~rhenry/sort/।

शीयर का सी # कार्यान्वयन यहां क्रमबद्ध करें: http://www.codeproject.com/KB/recipes/cssorters.aspx।

उदाहरण जावा में हैं लेकिन यह सी # के बहुत करीब है। वे समानांतर हैं क्योंकि वे कई कोरों पर तेजी से दौड़ते हैं लेकिन फिर भी बहुत तेज़ होना चाहिए।

Answer 4

यह पहला (और शायद दूसरा वाला) त्वरित सॉर्ट एल्गोरिदम डुप्लिकेट आइटम के साथ सरणी सॉर्ट करते समय टूटता है। मैंने this एक का उपयोग किया, जो ठीक काम करता है।