रैखिक समय और जगह में छंटनी

Question

मान लीजिए कि एन रिकॉर्ड्स में 1 से के बीच की रेंज है।

• हे में जगह में रिकॉर्ड सॉर्ट करने के लिए (एन + k) समय एक एल्गोरिथ्म लिखें।
• आप इनपुट सरणी के बाहर ओ (के) स्टोरेज का उपयोग कर सकते हैं।
• क्या आपका एल्गोरिदम स्थिर है?

अगर हम गिनती प्रकार का उपयोग करते हैं तो हम इसे ओ (एन + के) समय में कर सकते हैं और स्थिर है लेकिन इसकी जगह नहीं है।
यदि k = 2 इसे जगह में किया जा सकता है लेकिन यह स्थिर नहीं है (के = 0 और के = 1 के लिए सरणी में इंडेक्स को बनाए रखने के लिए दो चर का उपयोग करके)
लेकिन के> 2 के लिए मैं किसी भी अच्छे अहंकार के बारे में नहीं सोच सकता

Answer 1

सबसे पहले, के मिश्रित कैसे गिनती तरह काम करता है:

• गणना कितनी बार हर कुंजी सरणी में मौजूद क्रमबद्ध करना। ये गणना k आकार की सरणी में लिखी गई हैं।
• कुंजी गणनाओं के आंशिक रकम की गणना करें। यह क्रमबद्ध सरणी में बराबर कुंजियों के प्रत्येक बिन के लिए प्रारंभिक स्थिति देता है।
• आइटम को प्रत्येक आइटम के लिए संबंधित बिन की प्रारंभिक स्थिति में वृद्धि करने के लिए सरणी में अपनी अंतिम स्थिति में ले जाएं।

अब सवाल यह है कि अंतिम चरण में जगह कैसे करें। इन-प्लेस क्रमपरिवर्तन के लिए मानक दृष्टिकोण पहला तत्व चुनना है और इसे उस तत्व के साथ स्वैप करना है जो इसकी सही स्थिति लेता है। इस चरण को स्वैप तत्व के साथ दोहराया जाता है जब तक कि हम पहले तत्व में मौजूद तत्व को हिट नहीं करते (एक चक्र पूरा हो गया है)। फिर पूरी प्रक्रिया को दूसरी, तीसरी, आदि स्थिति के तत्वों के लिए दोहराया जाता है जब तक कि संपूर्ण सरणी संसाधित नहीं हो जाती।

गिनती के साथ समस्या यह है कि अंतिम स्थिति आसानी से उपलब्ध नहीं है लेकिन अंतिम लूप में प्रत्येक बिन की प्रारंभिक स्थिति में वृद्धि करके गणना की जाती है। किसी तत्व के लिए प्रारंभिक स्थिति को दो बार बढ़ाने के लिए, हमें यह निर्धारित करने का कोई तरीका नहीं है कि किसी निश्चित स्थिति पर कोई तत्व पहले से ही स्थानांतरित हो गया है या नहीं। यह प्रत्येक बिन के लिए मूल प्रारंभिक स्थिति का ट्रैक रखकर किया जा सकता है। यदि कोई तत्व मूल प्रारंभिक स्थिति और बिन के अगले तत्व की स्थिति के बीच स्थित है, तो यह पहले ही स्पर्श हो चुका है।

यहां सी 99 में एक कार्यान्वयन है जो O(n+k) में चलता है और अतिरिक्त संग्रहण के रूप में आकार के केवल दो एरे k की आवश्यकता होती है। अंतिम क्रमपरिवर्तन चरण स्थिर नहीं है।

#include <stdlib.h> 

void in_place_counting_sort(int *a, int n, int k) 
{ 
    int *start = (int *)calloc(k + 1, sizeof(int)); 
    int *end = (int *)malloc(k * sizeof(int)); 

    // Count. 
    for (int i = 0; i < n; ++i) { 
     ++start[a[i]]; 
    } 

    // Compute partial sums. 
    for (int bin = 0, sum = 0; bin < k; ++bin) { 
     int tmp = start[bin]; 
     start[bin] = sum; 
     end[bin] = sum; 
     sum += tmp; 
    } 
    start[k] = n; 

    // Move elements. 
    for (int i = 0, cur_bin = 0; i < n; ++i) { 
     while (i >= start[cur_bin+1]) { ++cur_bin; } 
     if (i < end[cur_bin]) { 
      // Element has already been processed. 
      continue; 
     } 

     int bin = a[i]; 
     while (bin != cur_bin) { 
      int j = end[bin]++; 
      // Swap bin and a[j] 
      int tmp = a[j]; 
      a[j] = bin; 
      bin = tmp; 
     } 
     a[i] = bin; 
     ++end[cur_bin]; 
    } 

    free(start); 
    free(end); 
} 

संपादित करें: यहाँ केवल आकार k मोहित भूरा के दृष्टिकोण के आधार पर की एक सारिणी का उपयोग करते हुए एक और संस्करण है।

#include <stdlib.h> 

void in_place_counting_sort(int *a, int n, int k) 
{ 
    int *counts = (int *)calloc(k, sizeof(int)); 

    // Count. 
    for (int i = 0; i < n; ++i) { 
     ++counts[a[i]]; 
    } 

    // Compute partial sums. 
    for (int val = 0, sum = 0; val < k; ++val) { 
     int tmp = counts[val]; 
     counts[val] = sum; 
     sum += tmp; 
    } 

    // Move elements. 
    for (int i = n - 1; i >= 0; --i) { 
     int val = a[i]; 
     int j = counts[val]; 

     if (j < i) { 
      // Process a fresh cycle. Since the index 'i' moves 
      // downward and the counts move upward, it is 
      // guaranteed that a value is never moved twice. 

      do { 
       ++counts[val]; 

       // Swap val and a[j]. 
       int tmp = val; 
       val = a[j]; 
       a[j] = tmp; 

       j = counts[val]; 
      } while (j < i); 

      // Move final value into place. 
      a[i] = val; 
     } 
    } 

    free(counts); 
} 

Answer 2

यहाँ मेरी कोड है कि (एन + k) समय हे में चलता है और आकार कश्मीर (आकार n का मुख्य सरणी से अलग)

#include <stdio.h> 
#include <string.h> 

#include <stdlib.h> 


int main(int argc, char const *argv[]) 
{ 
int n = atoi(argv[1]); 
int k = atoi(argv[2]); 

printf("%d\t%d",n,k); 

int *a,*c; 
int num,index,tmp,i; 
a = (int*)malloc(n*sizeof(int)); 
c = (int*)calloc(k,sizeof(int)); 

srand(time(NULL)); 

for(i=0;i<n;i++) 
{ 
    num = (rand() % (k)); 
    a[i] = num; 
    c[num]++; 
} 

printf("\n\nArray is : \n"); 
for(i=0;i<n;i++) 
{ 
    printf("\t%d",a[i]); 
    if(i%8==7) 
     printf("\n"); 
} 

printf("\n\nCount Array is : \n"); 
for(i=0;i<k;i++) 
{ 
    printf("\t%d(%d)",c[i],i); 
    if(i%8==7) 
     printf("\n"); 
} 

//Indexing count Array 
c[0]--; 
for(i=1;i<k;i++) 
{ 
    c[i] = c[i-1] + c[i];  
} 

printf("\n\nCount Array After Indexing is : \n"); 
for(i=0;i<k;i++) 
{ 
    printf("\t%d(%d)",c[i],i); 
    if(i%8==7) 
     printf("\n"); 
} 

// Swapping Elements in Array 
for(i=0;i<n;i++) 
{ 
    index = c[a[i]]; 
    //printf("\na[%d] = %d, going to position %d",i,a[i],index); 
    c[a[i]]--; 
    if(index > i) 
    { 
     tmp = a[i]; 
     a[i] = a[index]; 
     a[index] = tmp; 
     i--; 
    } 
} 

printf("\n\n\tFinal Sorted Array is : \n\n"); 
for(i=0;i<n;i++) 
{ 
    printf("\t%d",a[i]); 
    if(i%8==7) 
     printf("\n"); 
} 

printf("\n\n"); 

return 0; 
} 

यहां तक ​​कि इस algo का केवल 1 अतिरिक्त सरणी का उपयोग करता है स्थिर नहीं है सभी तत्व उनके विपरीत क्रम में हैं।

पी.एस: कुंजी (k-1)

Answer 3

मान पूर्णांक दृश्यों के लिए एक उदाहरण के लिए रेंज 0 में हैं। क्रम अस्थिर है। हालांकि यह मोहित द्वारा प्रदान की जवाब के रूप में के रूप में संक्षिप्त नहीं है, यह मामूली तेजी उनके सही डिब्बे में पहले से ही तत्व लंघन द्वारा (समय asymptotically एक ही है) (सामान्य मामले में जहां कश्मीर < < n के लिए) है। प्रैक्टिस में मैं मोहित के अपने कड़े, सरल लूप के लिए पसंद करता हूं।

def sort_inplace(seq): 
    min_ = min(seq) 
    max_ = max(seq) 
    k = max_ - min_ + 1 
    stop = [0] * k 
    for i in seq: 
     stop[i - min_] += 1 
    for j in range(1, k): 
     stop[j] += stop[j - 1] 
    insert = [0] + stop[:k - 1] 
    for j in range(k): 
     while insert[j] < stop[j] and seq[insert[j]] == j + min_: 
      insert[j] += 1 
    tmp = None 
    for j in range(k): 
     while insert[j] < stop[j]: 
      tmp, seq[insert[j]] = seq[insert[j]], tmp 
      while tmp is not None: 
       bin_ = tmp - min_ 
       tmp, seq[insert[bin_]] = seq[insert[bin_]], tmp 
       while insert[bin_] < stop[bin_] and seq[insert[bin_]] == bin_ + min_: 
        insert[bin_] += 1 

एक तंग पाश के साथ

लेकिन अभी भी लंघन पहले से ही दूसरी जगह तत्वों:

def dave_sort(seq): 
    min_ = min(seq) 
    max_ = max(seq) 
    k = max_ - min_ + 1 
    stop = [0] * k 

    for i in seq: 
     stop[i - min_] += 1 

    for i in range(1, k): 
     stop[i] += stop[i-1] 
    insert = [0] + stop[:k - 1] 

    for meh in range(0, k - 1): 
     i = insert[meh] 
     while i < stop[meh]: 
      bin_ = seq[i] - min_ 
      if insert[bin_] > i: 
       tmp = seq[insert[bin_]] 
       seq[insert[bin_]] = seq[i] 
       seq[i] = tmp 
       insert[bin_] += 1 
      else: 
       i += 1 

संपादित करें: अतिरिक्त बिट के साथ अजगर में मोहित के दृष्टिकोण तरह की स्थिरता पर प्रभाव सत्यापित करने के लिए।

from collections import namedtuple 
from random import randrange 

KV = namedtuple("KV", "k v") 

def mohit_sort(seq, key): 
    f = lambda v: getattr(v, key) 
    keys = map(f, seq) 
    min_ = min(keys) 
    max_ = max(keys) 
    k = max_ - min_ + 1 
    insert = [0] * k 

    for i in keys: 
     insert[i - min_] += 1 

    insert[0] -= 1 
    for i in range(1, k): 
     insert[i] += insert[i-1] 

    i = 0 
    n = len(seq) 
    while i < n: 
     bin_ = f(seq[i]) 
     if insert[bin_] > i: 
      seq[i], seq[insert[bin_]] = seq[insert[bin_]], seq[i] 
      i -= 1 
     insert[bin_] -= 1 
     i += 1 


def test(n, k): 
    seq = [] 
    vals = [0] * k 
    for _ in range(n): 
     key = randrange(k) 
     seq.append(KV(key, vals[key])) 
     vals[key] += 1 
    print(seq) 
    mohit_sort(seq, "k") 
    print(seq) 


if __name__ == "__main__": 
    test(20, 3)