Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Sorting Algorithm (1) Quick Sort C ++ implementation     - Java static internal class (Programming)

- Oracle 12C truncate table cascade (Database)

- Kernel compile under Debian (Linux)

- MySQL dual master configuration (Database)

- Struts2 form of non-use component tags (Programming)

- Linux operating system log system (Linux)

- Use Ansible installation NGINX and NGINX Plus (Server)

- Hunk / Hadoop: Performance Best Practices (Server)

- iOS in the event delivery and the responder chain (Programming)

- CentOS modify yum update source (Linux)

- Computer security perimeter recommendations (Linux)

- To achieve Linux Security (Linux)

- Redhat 7 modify the default run level method --RHEL7 use systemd to create a symbolic link to the default runlevel (Linux)

- Iptables command in detail (Linux)

- Xmanager Remote Desktop connection CentOS (Linux)

- Java Concurrency - multiple threads of HelloWorld (Programming)

- MySQL service failed to start thinking of settlement under CentOS7 (Database)

- Compile and install LNMP under CentOS 6.5 (Server)

- Linux centralized log server rsyslog (Server)

- Let your PHP 7 faster (GCC PGO) (Linux)

 
         
  Sorting Algorithm (1) Quick Sort C ++ implementation
     
  Add Date : 2018-11-21      
         
         
         
  Quick Sort Basic Features

Time complexity: O (n * lgn)
The worst: O (n ^ 2)
Space complexity: best case: O (lgn), worst case: O (n), average case: O (lgn)
Unstable.

Fast sorting Since each recursion takes up one space to return to the median position, the space complexity of one recursion is O (1).

The recursion depth for the best case and the average case is O (lgn), and the corresponding spatial complexity is O (lgn)

The worst-case recursion depth is O (n), and the space complexity is O (n).

algorithm

QUICKSORT (A, p, r)
    If p < r
       Then q PARTITION (A, p, r) // key
            QUICKSORT (A, p, q - 1)
            QUICKSORT (A, q + 1, r)
 
PARTITION (A, p, r)
      X <-- A [r]
      I <-- p - 1
      For j <-- p to r - 1
           Do if A [j] < x
                 Then i <-- i + 1
                     Exchange A [i] < -> A [j]
      Exchange A [i + 1] < -> A [r]
      Return i + 1

Source code

Class declaration

Class BaseSort {
Public:
    BaseSort () {}
    Virtual void sort () = 0;
};
 
Class QuickSort: public BaseSort {
Public:
    QuickSort (int Array [], int len): BaseSort () {
        This-> Array = Array;
        This-> len = len;
    }}
    Void sort ();
Private:
    Int partition (int Array [], int start, int end);
    Void quicksort (int Array [], int start, int end);
Private:
    Int * Array;
    Int len;
};
 

The relevant member functions are implemented

Void QuickSort :: sort () {
    Quicksort (Array, 0, len-1);
}}
Void QuickSort :: quicksort (int Array [], int start, int end) {
    If (start < end) {
        Int mid = this-> partition (Array, start, end);
        If (start < mid - 1)
            Quicksort (Array, start, mid-1);
        If (mid + 1 < end)
            Quicksort (Array, mid + 1, end);
    }}
}}
Int QuickSort :: partition (int Array [], int start, int end) {
    Int i, j, x, tmp;
    X = Array [end];
    I = start -1;
    
    For (j = start; j < end; j ++) {
        If (Array [j] < = x) {
            I ++;
            Tmp = Array [j];
            Array [j] = Array [i];
            Array [i] = tmp;
        }}
    }}
    
    Tmp = Array [end];
    Array [end] = Array [i + 1];
    Array [i + 1] = tmp;
    If (DEBUG) {
        PrintArray (Array, len, "MidResult");
    }}
    Return i + 1;
}}
test:

Int a [10] = {7,3,2,9,8,5,1,10,4,6};
Int len = 10;
 
QuickSort * quicksort = new QuickSort (a, len);
Quicksort-> sort ();
PrintArray (a, len, "QuickSort");
     
         
         
         
  More:      
 
- GRUB2 boot Ubuntu Manual (Linux)
- Docker: installation under Ubuntu (Server)
- Hazelcast integration with MongoDB (Database)
- Linux delete duplicate files Artifact: dupeGuru (Linux)
- Use eCryptFS encrypt files and directories on Linux (Linux)
- CentOS 6.5 Telnet SecureCRT use management tools (Linux)
- Cobbler automatic mass deployment of CentOS 6 and CentOS 7 (Linux)
- Oracle JDK installation under Ubuntu Linux (Linux)
- CentOS yum install LNMP PHP5.4 version (Server)
- Applications in Objective-C runtime mechanism (Programming)
- Enterprise Hadoop cluster architecture - DNS installation (Server)
- Running the open-source Swift under Linux platform (Linux)
- How to clean up your Ubuntu 14.10 / 14.04 / 13.10 system (Linux)
- Linux, MySQL / MariaDB Galera Cluster Setup Process (Database)
- Developing a Web server yourself (Server)
- WebLogic 12c Configuration Node Manager Managed Server (Database)
- xCAT install and update software (Linux)
- Alien Magic: RPM and DEB Mutual Convert (Linux)
- Linux (Debian) install software, missing dynamic link libraries .so (Linux)
- Use Ansible to bulk manage remote servers (Server)
     
           
     
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.