Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ The three-way division of the sorting algorithm Quicksort     - Linux Mint 17.2 64 bit installation Docker and management software seagull (Linux)

- C ++ pointer two third memory model (Programming)

- CentOS 7 source code to compile and install Nginx process record (Server)

- Several reasons MySQL garbled (Database)

- The REVERSE function of DB2 (Database)

- Laravel 4.2 Laravel5 comprehensive upgrade Raiders (Server)

- Use 3G wireless network card under Linux (Linux)

- Java reflection Introduction (Programming)

- The default permissions for files and directories under Linux computing (Linux)

- Oracle Linux 7.1 install Oracle 12C RAC (Database)

- PostgreSQL Stream Configuration (Database)

- Install the latest ATI / Nvidia graphics driver on Ubuntu (Linux)

- Oracle data files deleted recover after physical (Database)

- WebLogic 12c Configuration Node Manager Managed Server (Database)

- Ubuntu Backup and Recovery (Linux)

- Deploy Mono 4 and Jexus 5.6 on CentOS7 (Server)

- Redhat 5 prohibit IPv6 (Linux)

- Java and Python use make way dictionary word search script (Programming)

- Java transient keyword (Programming)

- RedHat Redis Linux installation (Database)

 
         
  The three-way division of the sorting algorithm Quicksort
     
  Add Date : 2017-01-08      
         
         
         
  When the sequence of elements to be sorted in a large number of repeat ordering code, the efficiency of fast simple sorting algorithm will be reduced to very low. The idea is a direct sort column will be divided into three sequences: one is smaller than the reference element ordering code ordering code; part of the reference element ordering code equivalent; part is larger than the reference element ordering code

Quicksort three-way division

But if we direct accordingly thought to write algorithm, then we will face great difficulties. Element reference elements equivalent in the end how much? As well as how best to quickly and efficiently determine the division of the border? So, to complete this three-way division is very difficult, even more complex than the two-way division process.
We can achieve three-way division based on the following idea: the division process, you will encounter when scanning left sub-sequence with the reference element ordering code equivalent elements into the leftmost sequence will encounter the right sequence Sort the elements of the reference element and the equivalent code sequence into the far right.

Three-way division of implementation

When scanning two pointers meet, the exact location of the sort code equal elements will know. Then we just sort of all the elements and the reference element equivalent code scanning pointer elements sequentially exchange, we can get the results of a three-way division.
This method not only effectively deal with the elements of the sequence to be sorted duplicate values issues, and in the absence of duplicate values it can maintain the performance of the original algorithm. Its advantages are:

First, if there is no sequence of elements duplicate values, this method can maintain the efficiency of the algorithm, because there is no extra work to do;

Second, in each division of the words in the process, it can be sorted with a reference element code element equal split out all elements have the same sort code division multiple values will not participate.

Code
private void quickSort (int [] a, int left, int right) {
    if (right < = left)
        return;

    / *
    * Work pointer
    * P is equal to the position of pivot point to the left of the sequence of elements
    * Q points to the right of the equal position of Pivot sequence elements
    * Element i pointing from left to right when the sweep plane
    Point element j from right to left when scanning *
    * /
    int p, q, i, j;
    int pivot; // anchor
    i = p = left;
    j = q = right - 1;
    / *
    * Always take each element of a sequence rightmost anchor
    * /
    pivot = a [right];
    while (true) {
        / *
        * Pointer i work from right to left constantly scanning, looking less than or equal to the anchor element elements
        * /
        while (i < right && a [i] < = pivot) {
            / *
            * Locate the anchor element element equal to its exchange position indicated by p
            * /
            if (a [i] == pivot) {
                swap (a, i, p);
                p ++;
            }
            i ++;
        }
        / *
        * Work pointer j constantly scan from left to right, looking for an anchor element greater than or equal elements
        * /
        while (left < = j && a [j]> = pivot) {
            / *
            * Locate the anchor element element equal to its exchange position indicated by q
            * /
            if (a [j] == pivot) {
                swap (a, j, q);
                q--;
            }
            j--;
        }
        / *
        * If you work two pointers i j meet the end of a trip traversal
        * /
        if (i> = j)
            break;

        / *
        * The left and the right side is greater than the pivot element is less than the pivot element exchange
        * /
        swap (a, i, j);
        i ++;
        j--;
    }
    / *
    * Because i work pointer points to the next element to deal with the current element
    * Therefore need to return to the actual position of the current element, then the exchange will be equal to the sequence of intermediate pivot element
    * /
    i--;
    p--;
    while (p> = left) {
        swap (a, i, p);
        i--;
        p--;
    }
    / *
    * Because the work pointer j points to a need to deal with the elements of the current element
    * Therefore need to return to the actual position of the current element, then the exchange will be equal to the sequence of intermediate pivot element
    * /
    j ++;
    q ++;
    while (q < = right) {
        swap (a, j, q);
        j ++;
        q ++;
    }

    / *
    * Recursive traversal sequences around
    * /
    quickSort (a, left, i);
    quickSort (a, j, right);
}

private void quick (int [] a) {
    if (a.length> 0) {
        quickSort (a, 0, a.length - 1);
    }
}

private void swap (int [] arr, int a, int b) {
    int temp = arr [a];
    arr [a] = arr [b];
    arr [b] = temp;
}
     
         
         
         
  More:      
 
- Nginx high concurrency optimization ideas (Server)
- Linux system security Comments (Linux)
- Ubuntu install Liferea news subscription software (Linux)
- Nginx Installation and Configuration (Server)
- Install Xshell on Mac OS X (Linux)
- Java Annotation Comments (Programming)
- 5 steps to help you become a good Docker contributors (Linux)
- Linux configuration startup mount: fstab file (Linux)
- Oracle Character Set Summary (Database)
- Via Twitter how open source library to be used anywhere Emoji emoticons (Linux)
- Open remote MySQL database connection managed under CentOS (Database)
- Using DBMS_STAT function closes mission (Database)
- SHELL script to use anti SSH brute force and vsftpd (Linux)
- Hadoop 2.7.1 installation configuration based on availability QJM (Server)
- To install JDK1.7 and compiler Hadoop-2.7.1 under CentOS7 (Server)
- To explore the caching mechanism for Android ListView (Programming)
- CentOS 6.5 x86_64 system customized automated deployment (Linux)
- JavaScript basic types and type conversion (Programming)
- C ++ inline functions (Programming)
- Linux Nginx installation and configuration instructions (Server)
     
           
     
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.