Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Simple and fast sorting     - Zabbix monitoring different versions of RAID installation and monitoring and MySQL master-slave monitor (Server)

- VMware virtual machine to install CentOS 7 (Linux)

- OpenSSL to generate public and private key (Linux)

- Recover accidentally deleted Nginx logs (Server)

- Detailed Linux network security policies and protection measures (Linux)

- How to install CentOS 7.x in OpenERP (Odoo) (Linux)

- Understanding and Memcached MongoDB arbitration node, Zookeeper, Redis Recovery Programme Thoughts (Database)

- Chkconfig set boot start under Linux (Linux)

- Let CentOS6 yum upgrade to support more source rpm package (Linux)

- QEMU code analysis: BIOS loading process (Linux)

- Oracle Character Set Summary (Database)

- Ubuntu 14.04 How to set up an SSH without password (Linux)

- How to Install terminator 0.98 on Ubuntu and Linux Mint (Linux)

- MultiWriter: while the ISO image concurrent writes 20 USB Startup Disk (Linux)

- Java reflection technology explain (Programming)

- Installation and Configuration Tomcat environment CentOS 6.6 (Server)

- The method of Linux into the rescue mode (Linux)

- Android LayoutInflater source parsing (Programming)

- Linux system with a firewall to prevent the DOS attack (Linux)

- Ubuntu 15.04 installed JDK and configured as the default JDK (Linux)

 
         
  Simple and fast sorting
     
  Add Date : 2017-08-31      
         
         
         
  This algorithm is one of my weaknesses. Take this simple quick sort algorithm, sophomore after completion, there is no review before. Because there are C qsort () interface, and the C ++ also has sort () interface. Not long ago wanted to consolidate the basics, we recalled the famous algorithm.

Because the university school, so I know it's generally a process - that is, a recursion. Given a set sequence arr [0 ... N], first by arr [0] will arr [0 ... N] into two (I'm lazy, do not draw, we will see Ha), as follows :

__ First half, Features: This half elements in a sequence = arr [0] _ (1)

Where the pilot (the pilot is not called? I forget)

Next, it is the recursive sort the top and second halves, recursion termination condition is to be ordered sequence length <= 1. This process is not very simple? That how to find arr [0] location, in other words, how the original sequence into two, to meet (1) the given conditions? Actually, the question I would like to start a long time, the results of the first edition of the code written to run or not, after the commissioning last run correctly.

Here it is bound to sequence traversal, and traversal process to maintain certain requirements - the so-called loop invariant ( "Introduction to Algorithms" start introducing the concept of). We are here to meet the requirements (or academic point called loop invariant) can be so described: traversal, assuming now loop variable value i, we must ensure that:

arr '[0] ... arr' [pilot-1]
Here we use the symbol arr '(apostrophe), where arr' [pilot] is stored in arr [0], the use of different symbols to represent the original sequence is different.

Question: how during traversal, holding (2) the establishment? ? ?

In fact, I think it is not difficult, you may want to invest a little thought. First, the arr [0] preserved, placed in the variable pilot_value, the initial situation is as follows:

____ Arr [1] arr [2] ... arr [N]


Because arr [0] preserved, so the location can be considered within the meaning of pilot does not make sense, so I drew a line - indicates that this can be seen as empty. Iterate from i = 1 start, the purpose is to traverse all values less than pilot_value into the left pilot position within the meaning of (as above: when the initial, pilot left no elements). Now we assume that the loop variable to i + 1, indicating that the front of the i-th element satisfies (2) requirements, and is now moving arr [i + 1] to the appropriate location, as follows:

arr '[0] ... arr' [pilot-1] <___ <= arr '[pilot + 1] ... arr' [i] arr [i + 1] (3)


It is simply compare pilot_value and arr [i + 1], two cases slightly:

(1) If pilot_value <= arr [i + 1], do not need to do anything;

(2) If pilot_value> arr [i + 1], at this time: will be placed directly on the pilot position arr [i] do? Try it, if you do, there will be the following:

arr '[0] ... arr' [pilot-1] arr [i] arr '[pilot + 1] ... arr' [i] _____ (4)

In this case, pilot should be +1, that the arrow points to the location. We know that pilot point to the location after the traversal is complete, it is to be stored arr [0] (ie: pilot_value), and the pilot at this point is a meaningful position. Note (4) in the last position is stored in arr [i + 1], this value is stored in this position now still make sense to you? Apparently it did not make sense! Then just put arr '[pilot + 1] underscores the value and location of where a change enough so that the new location pointed to pilot can see no sense - can be seen as a blank. Finally, results are as follows:

arr '[0] ... arr' [pilot-1] arr [i] _____ arr '[pilot + 2] ... arr' [i] arr '[pilot + 1] (5)

In fact, when the value of arr new pilot pointed to the location to the [i]. (5) will obviously be maintained (2) required. Complete traversal sequences to yield the final pilot, then pilot_value into this position, it can. Finally Find pilot and collating sequence to meet (2) required to achieve the following functions (using the template):

template < typename Type >
int find_pilot (Type arr [], int iLen) {
    int my_pilot = 0;
    int pilot_value = arr [0];

    for (int i = 1; i = iLen;! ++ i) {
        if (pilot_value> arr [i]) {
            // Put arr [i] pilot positions
            arr [my_pilot] = arr [i];

            // Pilot increment
            my_pilot ++;

            // Pilot and arr [i] exchange, in order to ensure that pilot point value is meaningless.
            std :: swap (arr [i], arr [my_pilot]);
        }
    }

    arr [my_pilot] = pilot_value;
    return my_pilot;
}

Quicksort is the first by the above-described function of the original sequence is divided into two by the pilot sequence, then the recursive call for the two sequences, respectively, as follows:

template < typename Type >
void quick_sort (Type arr [], int iLen) {
    if (iLen <= 1) {
        return;
    }

    int pilot = find_pilot (arr, iLen);
    quick_sort (arr, pilot);
    quick_sort (arr + pilot + 1, iLen - pilot - 1);
}

Finally, we tested the following code:

int main () {
    std :: cout << "= = = = = Quicksort Algorithm = = = = =" << std :: endl;
    std :: cout << "pre-sorted array:";

    int iTestArray [10] = {0};
    srand ((unsigned int) time (NULL));
    for (int i = 0; i = 10;! ++ i) {
        iTestArray [i] = rand ()% 100;
        std :: cout << iTestArray [i] << "";
    }
    std :: cout << std :: endl;

    quick_sort (iTestArray, 10);

    std :: cout << "sorted array:";
    for (int i = 0; i = 10;! ++ i) {
        std :: cout << iTestArray [i] << "";
    }
    std :: cout << std :: endl;

    return 0;
}
     
         
         
         
  More:      
 
- PHP security Programming Advice (Programming)
- Upgrading Oracle 11.2.0.1.0 to 11.2.0.3.0 (Database)
- Windows environment Android Studio v1.0 Installation Guide (Linux)
- After Pydev installation, Eclipse does not display solutions (Linux)
- Let Linux boot methods to enter characters interface and set FrameBuffer resolution methods (Linux)
- Spring-depth understanding of the various annotations (Programming)
- How to identify memory leaks in Java (Programming)
- Java Concurrency - processes and threads (Programming)
- GitLab remote backup of Linux Shell Scripting (Linux)
- How common Linux automation tasks (Server)
- Oracle RAC 10.2.0.5 upgrade to 11.2.0.4 problems encountered (Database)
- Redhat 7 can only be read after installation Samba service catalog approach could not be written (Server)
- Oracle 12C RAC on temporary table space Enlighten (Database)
- Hadoop 1 and 2.x installation notes (Server)
- Ubuntu 14.04 VirtualBox can not start solution (Linux)
- A detailed introduction to the Hadoop ecosystem (Server)
- How to restart after a crash Cinnamon (Linux)
- Android Dynamic efficiency articles: a brilliant Loading Analysis and Implementation (Programming)
- Compression software on a simple comparison of zip and gz (Linux)
- CentOS 6.5 install Firefox (Linux)
     
           
     
  CopyRight 2002-2020 newfreesoft.com, All Rights Reserved.