सॉर्टिंग एल्गोरिदम

Question

की तुलना करें मैंने विभिन्न प्रकार के सॉर्टिंग (बबल, सम्मिलन, चयन) को लागू किया। जानता हूँ कि मैं प्रत्येक प्रकार के लिए निम्नलिखित (यहाँ बुलबुला प्रकार के साथ एक उदाहरण है) की तरह उनके कार्यान्वयन की तुलना करना चाहते:

private static int[] bubbleSort(int[] tabToSort) { 
    int [] tab = tabToSort.clone(); 
    boolean tabSort = false; 
    while(!tabSort){ 
     tabSort = true; 
     for(int i = 0; i < tab.length -1; i++){ 
      if(tab[i]> tab[i+1]){ 
       int temp = tab[i+1]; 
       tab[i+1] = tab[i]; 
       tab[i] = temp; 
       tabSort = false; 
      } 
     } 
    } 
    return tab; 
} 

मैंने शुरू किया:

उदाहरण के लिए, यहाँ मेरी बुलबुला तरह का जीयूआई और मैं इसे पर 1000 यादृच्छिक अंक और रेखा y=x रखा:

@Override 
    public void paintComponent (Graphics g){ 
     super.paintComponent(g); 
     Graphics2D g2d = (Graphics2D) g; 
     g2d.setColor(Color.BLACK); 
     Dimension size = getSize(); 
     Insets insets= getInsets(); 
     int w = size.width - insets.left - insets.right; 
     int h = size.height - insets.top - insets.bottom; 

     g2d.drawLine(size.width ,0, 0, size.height); 
     Random r = new Random(); 

     for (int i =0; i < 1000; i++) { 
      int x = Math.abs(r.nextInt()) % w; 
      int y = Math.abs(r.nextInt()) % h; 
      Point p = new Point(x, y); 
      g2d.drawLine(p.x, p.y, p.x, p.y); 
     } 
    } 

यहाँ मैं क्या किया है:

अब मैं अटक कर रहा हूँ, मैं कैसे शुरू करने के लिए के बारे में पता नहीं है। क्या कोई मुझे लागू करने के लिए अनुसरण करने के लिए चरणों/संकेतों को इंगित कर सकता है?

धन्यवाद :)

Answer 1

आपको परिभाषित करना होगा कि अंक क्या हैं। एनीमेशन को देखते हुए, ऐसा लगता है कि वाई अक्ष value का प्रतिनिधित्व करता है, जबकि एक्स अक्ष उस मान की सरणी में position का प्रतिनिधित्व करती है।

आपके paint विधि में, फिर आप वस्तुओं की सूची में जायेंगे और एक बिंदु पेंट करेंगे, एक्स-पॉइंट सरणी में स्थिति होगी और y-point y-axis पर स्थिति होगी। मूल्य मानना ​​एक ज्ञात सीमा के भीतर हैं।

यह भी याद रखें कि ग्राफिक्स में वाई-अक्ष शीर्ष पर 0 से शुरू होता है, इसलिए आपको समन्वय के लिए मूल्यों का कुछ अनुवाद करना पड़ सकता है (इस पर निर्भर करता है कि आप इसे कैसे देखना चाहते हैं)।

Answer 2

सबसे आसान तरीका है बजाय यादृच्छिक अंक की एक पैरामीटर के रूप में अंक की एक पूर्वनिर्धारित List का उपयोग करता है एक में अपने पेंट विधि परिवर्तित करने के लिए किया जाएगा। अपनी सॉर्ट विधि के प्रत्येक पुनरावृत्ति पर क्रमबद्ध सरणी को पेंट विधि में पास करें और बिंदुओं को दोबारा डालें।

Answer 3

आप की जरूरत करने के लिए

1. एक सदस्य चर के रूप में यादृच्छिक मूल्यों के साथ एक int[] सरणी पैदा हो जाएगी। आइए data सरणी को कॉल करें। आप शायद एक निश्चित सरणी आकार और 100 की सीमा के साथ शुरू करना चाहते हैं। जब एक साधारण संस्करण काम कर रहा है, तो आप बाद में विंडो आकार में मान समायोजित कर सकते हैं। एक निश्चित आकार और सीमा तक टिकना और paintComponent में उपलब्ध स्थान पर बस स्केल करना बेहतर हो सकता है, जिससे व्यवहार विंडो के आकार से स्वतंत्र हो जाता है।
2. paintComponentdata पर लूप के लिए बदलें। लूप इंडेक्स आपका एक्स मान है और data[x] वाई मान निर्धारित करता है।
3. परीक्षण करें कि कोड अभी भी प्रारंभिक यादृच्छिक सरणी खींचता है। परवाह नहीं है कि यह केवल अप्पर बाएं कोने में है, तो आप इसे ठीक कर सकते हैं जब एनीमेशन काम कर रहा है।
4. आपको किसी प्रकार का sleep() अपनी सॉर्ट विधि के सबसे निचले भाग में कॉल करने की आवश्यकता होगी, इसलिए आपको चरणों का पालन करने का मौका मिलता है। अन्यथा, यहां तक ​​कि बुलबुले भी निरीक्षण करने के लिए बहुत तेज होगा। मैं एक सेकंड (पैरामीटर मान 1000) से शुरू करने की सलाह दूंगा। जब सब कुछ काम करता है तो इसे तेज़ी से बनाएं।
5. bubbleSort विधि को नए थ्रेड में प्रारंभ करें और सुनिश्चित करें कि आपका घटक प्रत्येक चरण से पुनर्निर्मित हो जाए। यह सबसे मुश्किल हिस्सा हो सकता है। शायद bublleSort विधि (या bubbleSort घटक की एक गैर स्थैतिक विधि) को घटक में हाथ दें और प्रत्येक चरण में repaint() का अनुरोध करें (सौभाग्य से, यह स्विंग में कुछ थ्रेड सुरक्षित विधियों में से एक है)।
6. अपने कोड को ठीक-ठीक करें: उपलब्ध स्थान के साथ गुणा करके और फिर सरणी आकार या मान सीमा से विभाजित करके x और y निर्देशांक स्केल करें। आवश्यकतानुसार नींद के समय को समायोजित करें। विभिन्न सॉर्टिंग एल्गोरिदम के लिए समर्थन जोड़ें ....

यदि कोई भी कदम अस्पष्ट है, तो एक टिप्पणी जोड़ें।

Answer 4

मैं अपने bachelorthesis के लिए ऐसा कर लेंगे, मैं इसे इस तरह से किया था (यह सही नहीं है, लेकिन यह आप मदद कर सकता है):।

(मैं नीचे दिए गए कोड से कुछ महत्वहीन तरीकों/कार्य हटाया यह मुख्य रूप से यह वर्णन करने के लिए कि मैंने इसे कैसे देखा। आप उदाहरण के लिए एक सरल java.awt.Point द्वारा GRectangle क्लास को प्रतिस्थापित कर सकते हैं।)

प्रारंभिक विधि आपको एक उदाहरण देता है कि आप डेटा का अधिकतम और न्यूनतम मूल्य कैसे प्राप्त कर सकते हैं तो आप जानते हैं कि अपने डेटावैल => निर्देशांक को कैसे बदला जाए।

public class DotVisualisation extends Visualisation { 

    private ArrayList<GRectangle> m_points; 

    private Comparable[] m_data; 

    private Comparable m_maxValue; 
    private Comparable m_minValue; 

    private int MAX_HEIGHT; // max height in pixels of visualization 

    /** 
    * Creates a new DotVisualisation.<br> 
    * <br> 
    * This class is a runnable JComponent that will visualize data as a function. 
    * The visualisation will plot the data with X and Y coordinates on the window. 
    * The X coordinate of the point is index of the dataelement. 
    * The Y coordinate of the point is relative to the value of the dataelement.<br> 
    * <br> 
    * This visualisation should be used for medium and large arrays. 
    * 
    * @author David Nysten 
    */ 
    public DotVisualisation() 
    { 
     m_points = new ArrayList<GRectangle>(); 
     MAX_HEIGHT = 150; 
    } 

    /** 
    * Returns the maximum supported dimension by this visualisation. 
    * 
    * @return The supported dimension. 
    */ 
    public static int getSupportedDimension() 
    { 
     return 1; 
    } 

    @Override 
    public Dimension getMaximumSize() 
    { 
     return getPreferredSize(); 
    } 

    @Override 
    public Dimension getPreferredSize() 
    { 
     return new Dimension(m_points.size() + 2, MAX_HEIGHT + 6); 
    } 

    @Override 
    public Dimension getMinimumSize() 
    { 
     return getPreferredSize(); 
    } 

    @Override 
    public void paintComponent(Graphics g) 
    { 
     for(int i = 0; i < m_points.size(); ++i) 
      m_points.get(i).paintComponent(g); 
    } 

    private void swap(int index, int index2) { // See below } 

    private void initialise() 
    { 
     findMinimum(); 
     findMaximum(); 
     m_points.clear(); 
     double multiplier; 
     int x = 0, y = 0, h; 
     for(int i = 0; i < m_data.length; ++i) 
     { 
      if(m_data[i].compareTo(-1) <= 0) 
       h = 0; 
      else 
      { 
       Integer value = (Integer) m_data[i]; 
       Integer min = (Integer) m_minValue; 
       Integer diff = (Integer) m_maxValue - min; 
       multiplier = MAX_HEIGHT/diff.doubleValue(); 
       h = (int) ((value - min) * multiplier); 
      } 
      y = (int) (MAX_HEIGHT - h); 
      GRectangle r = new GRectangle(x, y, 1, 1); // 1, 1 = width and height 
      r.setColor(Color.BLACK); 
      m_points.add(r); 
      ++x; 
     } 
    } 

    private void findMaximum() 
    { 
     Comparable max = null; 
     if(m_data.length > 0) 
     { 
      max = m_data[0]; 
      for(int i = 1; i < m_data.length; ++i) 
       if(m_data[i].compareTo(max) > 0) 
        max = m_data[i]; 
     } 
     m_maxValue = max; 
    } 

    private void findMinimum() 
    { 
     Comparable min = null; 
     if(m_data.length > 0) 
     { 
      min = m_data[0]; 
      for(int i = 1; i < m_data.length; ++i) 
       if(m_data[i].compareTo(min) < 0) 
        min = m_data[i]; 
     } 
     m_minValue = min; 
    } 
} 

खाते में यह लो: 150 पिक्सेल की ऊंचाई पर 0 और 150 के बीच विज्युअलाइजिंग पूर्णांकों सरल है। 150 की ऊंचाई पर 565 और 3544545 के बीच पूर्णांक के एक सेट को विज़ुअलाइज़ करना थोड़ा सा है।

पीएस: कोड एक्स-समन्वय के रूप में इनपुटएरे में तत्व की अनुक्रमणिका का उपयोग करता है।
पीएस: कक्षा इनपुटएरे (m_data चर) का संदर्भ रखती है लेकिन यह आवश्यक नहीं है, आपको केवल अपने अंक आरंभ करने की आवश्यकता है।
पीएस: मेरी "विजुअलाइजेशन" कक्षा जो सभी विज़ुअलाइजेशन द्वारा विस्तारित है, मूल रूप से एक जेपीनल है।
पीएस: उपरोक्त कोड सकारात्मक पूर्णांक के लिए लिखा गया है, इसलिए शायद नकारात्मक पूर्णांक को संभालने के लिए कुछ अतिरिक्त कोडिंग की आवश्यकता होगी;)।

फिर एल्गोरिदम के कार्यों को देखने के लिए, मैंने पर्यवेक्षक पैटर्न का उपयोग किया। एल्गोरिथ्म, उदाहरण के bubblesort के लिए, इस तरह देखा:

for(int i = 0; i < size(); ++i) 
     for(int j = 1; j < size(); ++j) 
      if(greaterThan(j - 1, j)) 
       swap(j - 1, j); 

कहाँ समारोह स्वैप के रूप में (सरलीकृत संस्करण फिर से) इस प्रकार परिभाषित किया गया था:

protected void swap(int index1, int index2) 
{ 
    if(index1 != index2) 
    { 
     incrementSwap(); // counting swaps and visualizing counter 

     m_command.clear(); 
     m_command.setAction(Action.SWAP); 
     m_command.addParameter(index1); 
     m_command.addParameter(index2); 
     setChanged(); 
     notifyObservers(m_command); 

     E temp = m_data[index1]; 
     m_data[index1] = m_data[index2]; 
     m_data[index2] = temp; 
    } 
} 

कहाँ मैं एक स्वैप कि मेरे पर्यवेक्षकों (दृश्यावलोकन) अधिसूचित इंडेक्स 1 और इंडेक्स 2 पर हुआ। M_command चर कमांड-क्लास का एक उदाहरण है (इसे स्वयं लिखा है) जो विज़ुअलाइज़ेशन द्वारा आवश्यक जानकारी के लिए सिर्फ एक रैपर है। जो है: जो कार्रवाई हुई और प्रासंगिक जानकारी (उदाहरण के लिए स्वैप-एक्शन के लिए सूचकांक)।

तो विज़ुअलाइज़ेशन में मैंने उन इंडेक्स पर जीईक्टेंगल को और उनके एक्स-निर्देशांक के रूप में बदल दिया;

private void swap(int index, int index2) 
{ 
    if(index == index2) 
     return; 
    GRectangle r1 = m_points.get(index); 
    GRectangle r2 = m_points.get(index2); 

    int tempX = r1.getX(); 
    r1.setLocation(r2.getX(), r1.getY()); 
    r2.setLocation(tempX, r2.getY()); 

    m_points.set(index, r2); 
    m_points.set(index2, r1); 
} 

आप इस तरह लाइनों जोड़ सकते हैं:

 try { 
      Thread.sleep(100); 
     } catch(InterruptedException ignore) {} 

continueing से पहले एक धागा नींद 100ms जाने के लिए।यह आसान हो सकता है अगर यह बहुत तेजी से कल्पना हो रही है।

तो यादृच्छिक पूर्णांकों के साथ एक सरणी के लिए यह इस प्रकार दिखाई देंगे:

और छँटाई के बाद: (बेशक यह एक सीधी रेखा नहीं है क्योंकि inputarray में मानों इस में यादृच्छिक पर उत्पन्न किया गया मामले)

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

और फिर आप तुलना के लिए ऐसा कुछ बना सकते हैं;

http://i445.photobucket.com/albums/qq179/ultddave/DotVisualizationMany_zps63269d2a.png http://i445.photobucket.com/albums/qq179/ultddave/DotVisualizationMany2_zps65e96fa9.png

गुड लक!